Log in

No account? Create an account

t3knomanser's Fustian Deposits

Haskell - Programming Language

How Random Babbling Becomes Corporate Policy

run the fuck away

Mad science gone horribly, horribly wrong(or right).

Haskell - Programming Language

Previous Entry Share Next Entry
run the fuck away
I've been hearing all sorts of stuff about Haskell lately. It's a programming language that has all of my favorite features: it's a functional language, it uses pattern matching on function definitions, and it's got a very sparse, simple, syntax.

While it doesn't have quite the rarefied elegance of LISP, it has one other really fantastic feature: it uses lazy evaluation all the time. In contrast, pretty much every other language uses eager evaluation most of the time.

For example, if I did this in pretty much any language:
x = 2 * 2
It would execute 2 * 2 and put the result into x. This is eager evaluation. In Haskell, on the other hand, it doesn't execute anything, it just creates what's called a "thunk" and says, "hey, if anybody ever wants to know what's in x, tell them it's 2 * 2. I won't figure out what 2 * 2 is until someone actually wants to know what's in x."

This has some weird effects. For one, you never know precisely when a line of Haskell code is going to execute. It doesn't execute code in order, only as needed. Some code will never execute, because Haskell never decides it needs the results of that expression. And because of all that, you can do something in Haskell that you can't do in most languages: create infinitely long data structures.

For example, I could define a function like this in Haskell:
makeList n = n : makeList (n + 1)

That defines a function called makeList that takes one parameter (n). After the "=", it explains what it does: take n, and construct a list (:) with the result of calling makeList on the value n + 1. If I invoked makeList 0, it would return a list like this: [0,1,2,3,4...∞].

Obviously, it's impossible to create an infinitely long list, but since Haskell doesn't actually evaluate the list, I can actually call makeList 0 and get back a thunk capable of producing an infinitely long list.

But it gets better- since the function is recursive, Haskell can execute any arbitrary number of recursions without needing to produce the entire list. So, for example, if I wanted to get all of the list after the first element, I could write this statement:
tail (makeList 0)

That returns a list containing all integers from 1 on up. And if I wanted the 1,000,000th number in that list? I could actually grab it, and Haskell would execute up to that number, and no more.

I can understand why mathematicians like this language. It's the first one that has a really good grasp of how to handle infinities.

*This is not the most elegant way to write an infinite list in Haskell. Much more easily, I could write: [1,2,..]. [1,2,..] !! 1000000 would return the 1,000,000 element of the list (the number 1,000,000 in this case).
  • That is neat and helps me understand what "lazy evaluation" is.
    • Glad it helped.

      A slightly more interesting use of lazy evaluation is the Haskell approach to the Fibonacci sequence.

      nac = 1 : 1 : [ a+b | (a,b) <- zip nac (tail nac)]

      That returns a list containing every value in the Fibonacci sequence.

      The zip nac (tail nac) takes nac (the list of all Fib numbers) and the tail of nac (all but the first element in that list) and interleaves them, (a,b) <- takes the result of zip and turns it into a pair of values- literally, it takes the first two elements out of the zip result and names them "a" and "b". So this whole phrase, [ a+b | (a,b) <- zip nac (tail nac)] says, zip up the Fibonacci sequence and all but the first element of the Fibonacci sequence, pop off each element into pairs, and add each half of the pair to produce a list.

      Crazy recursive code that works because of lazy evaluation.
Powered by LiveJournal.com