TaslemGuy
|
  |
| Joined: 10 Jun 2009 |
| Total Posts: 12174 |
|
|
| 28 Sep 2012 09:46 PM |
Here's some neat aspects of Haskell that make the language special, as well as their application to Lua.
(I deem this worthy of "advanced scripting discussion", but please correct me if I'm wrong).
Haskell is a purely functional language. This means functions dominate how you write code.
It also means a few more subtle things. Namely, you can't change the value of any variable.
But this is good! The "functional style" of programming is unusual but ends up being quite nice.
The typical example of functional programming is the definition of "factorial." Lua is semi-functional and thus can demonstrate both styles.
The typical definition (more or less, using while loops to emphasize clarity, not conciseness)
function factorial(n) local s = 1 local i = 1 while i <= n do s = s * i i = i + 1 end return s end
It might seem impossible, at first, to define factorial without using any changing variables, but it's actually pretty easy.
function factorial(n) if n == 0 then return 1 else return factorial(n-1) * n end end
No variables ever change here. So it's in the "functional style."
The equivalent code in Haskell is much more concise, because this is how all functions end up being defined.
factorial 0 = 1 factorial n = factorial (n-1) * n
You'll notice that functions here use concatenation to apply arguments. There's a relatively subtle reason for this which has to do with what is called "currying."
Before we delve into that, let's go for "lambda expressions." A lambda expression is essentially an anonymous function.
In Lua: (function(x) return x + 1 end)(5) --> 6
In Haskell: (\x -> x + 1) 5 --> 6
Since functions and lambda expressions are pretty important in Haskell, you can see pretty clearly that their syntax is pretty light, though maybe a bit peculiar.
Lambda expressions themselves are derived from the lambda calculus, which is a model of computation proven to be equivalent to Turing Machines (that is, it can perform any computation).
Lambda expressions in Haskell retain an interesting property: They can only take one argument.
But, then, functions are useless! You need to be able to take more than one argument! Actually, you don't!
Let's make a lambda expression that takes two arguments and returns their sum. But how? They can only take one! There's a solution!
(\x -> (\y -> x + y)) 4 5
Magic! What we have here is a function that takes a number and spits out a function that takes a number that spits out a sum.
The neat thing about this is that we have:
(\x -> (\y -> x + y)) 4 --> (\y -> 4 + y)
So you don't have to give ALL of the arguments to a function. You can give SOME of them and then pass that function along to do other stuff to it.
We can do this in Lua, too!
function sum(x) return function(y) return x + y end end
So I can say:
add_one = sum(1) add_two = sum(2)
And then do:
add_one(5) --> 6 add_one(7) --> 8 add_two(9) --> 11 add_two(-1) --> 1
If I want to do both at the same time, I'd write: sum(4)(5) --> 9
Since we don't want to be writing (\ -> (\ -> (\ -> ... over and over again, Haskell let's you just write multi-argument functions as such:
(\x y -> x + y)
Internally, it will rewrite it as
(\x -> (\y -> x + y))
This method of providing multiple arguments by returning functions from functions is called "Currying."
And it's super useful when it comes to using higher-order functions!
Let's go onto something else. Haskell is what's called "nonstrict."
Suppose you have the following code in Lua:
function forever() while true do end end
local t = { forever() , 5 } t[2] --> infinite loop
We won't get our answer, because we've got to wait for t[1] to finish computing.
Not in Haskell!
Haskell is non-strict. Usually, this means Haskell is "lazy", but the standard doesn't require it.
More or less, this means Haskell will ignore a computation until it NEEDS it, so you can do the above without any kind of difficulty.
A more USEFUL aspect of the "laziness" is that you can create "infinite data structures."
Suppose I want an infinite list of 1's. In Lua, this isn't actually really possible, since you'd need infinite memory. But what if I only want a part of it at a time? Well, that could work. Haskell has the solution!
First, let's look at lists in Haskell. Since data can't change (no variables) arrays aren't useful. Instead there are lists. Specifically a linked cons list.
Here's a list: [1,4,2,7]
4 : [1,2,3] --> [4,1,2,3]
The : is "cons" or puts something at the beginning of a list.
Here's a simple list function: "take". {take n list} gives you the first 'n' elements in 'list.'
take 3 [6,2,8,3,1] --> [6,2,8]
Let's make an infinite list!
z = 1 : z
To see how that works, swap the 'z' on the right side with the whole right side, and repeat:
z --> 1 : z --> 1 : (1 : z) --> 1 : (1 : (1 : z)) --> ...
So I end up with [1,1,1,1,1,1,1,1,... and since Haskell is lazy, it doesn't care about the 1's after it sees them. So it can keep printing forever without running out of memory by ditching everything it no longer needs.
More usefully, I can say:
take 10 z --> [1,1,1,1,1,1,1,1,1,1]
Magic!
You can do more complex things, too:
q n = (n*n) : q (n+1)
Gives you: [1,4,9,16,25,36,49,64,81,100,121,144,169...
This is one feature of Haskell that is difficult to implement in Lua, because Lua is inherently strict and eager, with one exception: the and/or operators.
function cons(head,list) local t = {} t.head = head t.tail = function() return list end end
local z = {head = 1, tail = function() return z end}
function q(n) return {head = n*n, tail = function() return q(n+1) end} end
To get the first value, do list.head; To get the rest of the list, perform list.tail();
For instance:
function k() local list = q(1) local i = 0 while i < 15 do i = i + 1 print(list.head) list = list.tail() end end
Will print 1,4,9,16,25,36,49,64,81,100,121,144,169,196,225
|
|
|
| Report Abuse |
|
|
|
| 28 Sep 2012 10:09 PM |
| This is moderately interesting. |
|
|
| Report Abuse |
|
|
8SunTzu8
|
  |
| Joined: 30 Sep 2011 |
| Total Posts: 8199 |
|
|
| 28 Sep 2012 10:31 PM |
I think I stopped a quarter of the way through...
But I do agree, it was interesting. There are some really unique types of programming languages out there...
"Contact me if you are interested in becoming a developer, innovator, or recruiter for CSA." |
|
|
| Report Abuse |
|
|
|
| 28 Sep 2012 10:37 PM |
| It is in many ways 'better' except that it does not either model a turing machine more directly or model a von neumann machine more directly than traditional imperative programming. |
|
|
| Report Abuse |
|
|
Davidii
|
  |
| Joined: 17 Jul 2008 |
| Total Posts: 1282 |
|
|
| 29 Sep 2012 07:53 AM |
Tl;dr
I'm typically apathetic to languages I don't know. |
|
|
| Report Abuse |
|
|
Quenty
|
  |
| Joined: 03 Sep 2009 |
| Total Posts: 9316 |
|
|
| 29 Sep 2012 08:06 AM |
| Besides being good for speed coding, what else is it really good at? Does it handle large datasets well? |
|
|
| Report Abuse |
|
|
SN0X
|
  |
| Joined: 24 Oct 2011 |
| Total Posts: 7277 |
|
|
| 29 Sep 2012 08:42 AM |
"I think I stopped a quarter of the way through... "
As did I.
But there were some interesting concepts there.
I think I'll try Haskell. Don't know when though; I'm pretty busy. |
|
|
| Report Abuse |
|
|
TaslemGuy
|
  |
| Joined: 10 Jun 2009 |
| Total Posts: 12174 |
|
|
| 29 Sep 2012 11:57 AM |
@Quenty
Haskell is more concise, easier to read, and much shorter than typical imperative code.
It also has a tendency when done right to be high modular and composable.
Due to the typing system, which I skipped over, it's also easier to write correct code.
It's also easy to prove correctness of Haskell programs, which makes it applicable to mathematics.
It has pretty good parsing libraries and excellent symbolic manipulation.
It has extensive and useful testing libraries and profiling.
When it's used correctly it can be fast, comparable to, say, C.
For instance, Quicksort in Haskell:
quicksort :: Ord a => [a] -> [a] quicksort [] = [] quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater) where lesser = filter (< p) xs greater = filter (>= p) xs
The type system lets you verify that it should work, and it runs really fast.
Also, Haskell supports out-of-the-box unlimited precision Integers, which is awesome.
It also teaches design strategies. For instance, tail-call recursion for improved speed (I don't think this quite works in Lua, though like the other examples I can think of ways to implement it indirectly)
fac' 0 a = a fac' x a = fac' (x-1) (a*x) fac x = fac' x 1
Which won't stackoverflow no matter how deeply it's called. When interpreted and not compiled, fac 300 runs in under a tenth of a second.
306057512216440636035370461297268629388588804173576999416776741259476533176716867465515291422477573349939147888701726368864263907759003154226842927906974559841225476930271954604008012215776252176854255965356903506788725264321896264299365204576448830388909753943489625436053225980776521270822437639449120128678675368305712293681943649956460498166450227716500185176546469340112226034729724066333258583506870150169794168850353752137554910289126407157154830282284937952636580145235233156936482233436799254594095276820608062232812387383880817049600000000000000000000000000000000000000000000000000000000000000000000000000 |
|
|
| Report Abuse |
|
|
SN0X
|
  |
| Joined: 24 Oct 2011 |
| Total Posts: 7277 |
|
|
| 29 Sep 2012 12:36 PM |
"Also, Haskell supports out-of-the-box unlimited precision Integers, which is awesome."
"which is awesome"
Agreed.
Can't wait to try it out.
Fibonacci should be exciting :D |
|
|
| Report Abuse |
|
|
TaslemGuy
|
  |
| Joined: 10 Jun 2009 |
| Total Posts: 12174 |
|
|
| 29 Sep 2012 02:13 PM |
@SN0X
Here's a hint for Fibonacci: The naive implementation is very bad.
fib 0 = 0 fib 1 = 1 fib n = fib (n-1) + fib (n-2)
It's not immediately obvious what's wrong with this. The problem is that every call with recursively call two more, giving time complexity O(2^n). This means that while you can reasonably calculate the first 10, good luck getting the 100th.
The main reason it's slow is because you're recomputing when you don't need to. Remember the solution to a previous calculation is called "memoization" and it's an important efficiency/optimization tool.
The typical way to memoize the above algorithm is to create a list of values:
fib' 0 = 0 fib' 1 = 1 fib' n = fibs !! (n-1) + fibs !! (n-2)
fibs = map fib' [0..]
fib n = fibs !! n
Which will be very, very fast.
On notation:
[0..] is the list of numbers [0,1,2,3,4,5,6,...] demonstrating both lazy lists and arbitrary precision integers.
map is a function that "maps" a function over a list. In this case, we're calling fib' for each number in the list [0..], so it ends up being [fib' 0, fib' 1,fib' 2, fib' 3,...]
Also note that using ' is permitted in variable names under certain circumstances, such as at the end.
The above implementation of fib is also not tail-recursive, which can be problematic. |
|
|
| Report Abuse |
|
|
|
| 29 Sep 2012 02:24 PM |
| Your last bit about lazy evaluation is indeed possible with Lua, but not by using normal tables. Essentially, that's what metatables are for. |
|
|
| Report Abuse |
|
|
SN0X
|
  |
| Joined: 24 Oct 2011 |
| Total Posts: 7277 |
|
|
| 30 Sep 2012 02:21 AM |
I tried Haskell out yesterday.
Heck, what is that syntax.
It confuses me. |
|
|
| Report Abuse |
|
|
|
| 30 Sep 2012 05:24 AM |
"It confuses me."
"yesterday" there is your answer |
|
|
| Report Abuse |
|
|
TheMyrco
|
  |
| Joined: 13 Aug 2011 |
| Total Posts: 15105 |
|
|
| 30 Sep 2012 09:24 AM |
| What would happen if you'd combine Lua with Haskell, lolz =D |
|
|
| Report Abuse |
|
|
SN0X
|
  |
| Joined: 24 Oct 2011 |
| Total Posts: 7277 |
|
|
| 30 Sep 2012 09:36 AM |
| a metatabled function would come out |
|
|
| Report Abuse |
|
|
TheMyrco
|
  |
| Joined: 13 Aug 2011 |
| Total Posts: 15105 |
|
| |
|
TaslemGuy
|
  |
| Joined: 10 Jun 2009 |
| Total Posts: 12174 |
|
|
| 30 Sep 2012 10:56 AM |
I don't think there's a healthy mix.
Lua is imperative with functional features while Haskell is purely functional.
|
|
|
| Report Abuse |
|
|