First example

I thought I would start with an exercise in RWH to get my feet wet, since I was having difficulty just getting a program to do anything. So, I worked on exercise 1 in chapter 3, which was to write a function that does the same as the length command. So, I wrote something to the effect of:

len count [] = count
len count (x:xs) = len count + 1 xs

A few notes on what is above. Function calling in Haskell is done by pattern matching, and the above code says what len should do if given inputs that match these patterns. The symbol [] is an empty list, and (x:xs) is shorthand for a nonempty list with x as its first element, and the remainder of the list as xs.

So I fire up Haskell at the my command prompt with ghci, then :load listLength.hs and try running this code on the list [1..1000000], and I got an Exception: stack overflow! How is this possible with something so simple? Well, it turns out that Haskell is lazy in that it does not evaluate an expression until it absolutely must. In this case, Haskell does not evaluate the expression count + 1, so it recursively calls this function until we get to the base case, the empty list. Since Haskell's operator stack can't handle this many recursions, it dies.

How can we get around this and still have this simple intuitive code? Haskell has an operator that tells the interpreter to evaluate an expression even if it is not necessary for program flow, which is the '$!' operator. So, by changing the above code to

len count [] = count
len count (x:xs) = len $! count + 1 xs

makes this do what length is supposed to, albeit much slower since it is recursive.