How does this haskell code work?

4
votes

I'm a new student and I'm studying in Computer Sciences. We're tackling Haskell, and while I understand the idea of Haskell, I just can't seem to figure out how exactly the piece of code we're supposed to look at works:

module U1 where

double x = x + x
doubles (d:ds) = (double d):(doubles ds)
ds = doubles [1..]

I admit, it seems rather simple for someone that knows whats happening, but I can't wrap my head around it. If I write "take 5 ds", it obviously gives back [2,4,6,8,10]. What I dont get, is why.

Here's my train of thought : I call ds, which then looks for doubles. because I also submit the value [1..], doubles (d:ds) should mean that d = 1 and ds = [2..], correct? I then double the d, which returns 2 and puts it at the start of a list (array?). Then it calls upon itself, transferring ds = [2..] to d = 2 and ds = [3..], which then doubles d again and again calls upon itself and so on and so forth until it can return 5 values, [2,4,6,8,10].

So first of all, is my understanding right? Do I have any grave mistakes in my string of thought? Second of all, since it seems to save all doubled d into a list to call for later, whats the name of that list? Where did I exactly define it?

Thanks in advance, hope you can help out a student to understand this x)

2
haskell
(d:ds) means d is the head of the list, and ds is the rest of it (not just the second element). So ds = [2..] in the top-level call. – Fred Foo
Ah sorry, I've actually written that, I just wrote 2.. instead of [2..] – Joe
Yes your understanding is pretty much correct. Except the list of doubled values is not really "saved" in anything named, it is just built and immediately returned. Just like x+x is not saved anywhere, so is (double d):(doubles ds). – n. 1.8e9-where's-my-share m.
@JoeDegler:This isn't relevant particularly relevant, but where are you studying computer science that they start teaching you in Haskell? – Joshua Snider
@JoshuaSnider I am studying in Northern Germany, at University Rostock. We started in Java and Haskell, every winter semester Java and C+ are switching though. – Joe

2 Answers

5
votes

I think you are right about the recursion/loop part about how doubles goes through each element of the infinite list.

Now regarding

it seems to save all doubled d into a list to call for later, whats the name of that list? Where did I exactly define it?

This relates to a feature that's called Lazy Evaluation in Haskell. The list isn't precomputed and stored any where. Instead, you can imagine that a list is a function object in C++ that can generate elements when needed. (The normal language you may see is that expressions are evaluated on demand). So when you do

take 5 [1..]

[1..] can be viewed as a function object that generates numbers when used with head, take etc. So,

take 5 [1..] == (1 :  take 4 [2..])

Here [2..] is also a "function object" that gives you numbers. Similarly, you can have

take 5 [1..] == (1 : 2 : take 3 [3..]) == ... (1 : 2 : 3 : 4 : 5 : take 0 [6..])

Now, we don't need to care about [6..], because take 0 xs for any xs is []. Therefore, we can have 

take 5 [1..] == (1 : 2 : 3 : 4 : 5 : [])

without needing to store any of the "infinite" lists like [2..]. They may be viewed as function objects/generators if you want to get an idea of how Lazy computation can actually happen.

1
votes

Your train of thought looks correct. The only minor inaccuracy in it lies in describing the computation using expressions such has "it doubles 2 and then calls itself ...". In pure functional programming languages, such as Haskell, there actually is no fixed evaluation order. Specifically, in

double 1 : double [2..]

it is left unspecified whether doubling 1 happens before of after doubling the rest of the list. Theoretical results guarantee that order is indeed immaterial, in that -- roughly -- even if you evaluate your expression in a different order you will get the same result. I would recommend that you see this property at work using the Lambda Bubble Pop website: there you can pop bubbles in a different order to simulate any evaluation order. No matter what you do, you will get the same result.

Note that, because evaluation order does not matter, the Haskell compiler is free to choose any evaluation order it deems to be the most appropriate for your code. For instance, let ds be defined as in the final line in your code, and consider

take 5 (drop 5 ds)

this results in [12,14,16,18,20]. Note that the compiler has no need to double the first 5 numbers, since you are dropping them, so they can be dropped before they are completely computed (!!).

If you want to experiment, define yourself a function which is very expensive to compute (say, write fibonacci following the recursive definifion). 

fibonacci 0 = 0
fibonacci 1 = 1
fibonacci n = fibonacci (n-1) + fibonacci (n-2)

Then, define

const5 n = 5

and compute

fibonacci 100

and observe how long that actually takes. Then, evaluate

const5 (fibonacci 100)

and see that the result is immediately reached -- the argument was not even computed (!) since there was no need for it.