How does Haskell process a list?

Question

A few of us at work have been reading some on Haskell and we were talking about some of the concepts yesterday. The question came up with Haskell being a lazy language, how does it handle retrieving the nth element of a list?

For example, if we had

 [2,4..10000000] !! 200

Would it actually populate the list up to 200 elements? Or does it compile it down into an equation similar to

n*step + firstValue

and then return that calculation? The reason this came up was someone was trying to come up with an example where a program would easily run out of memory, and the thought of traversing down a (sufficiently large) list was the first candidate that came up.

Answer 1

Yes, it will produce the first 201 elements of the list before returning. However, since this list is not accessible from anywhere else in your program, the initial bits will be eligible for garbage collection as it goes along, so it will run in constant space (but linear time) with a naive implementation.

Of course, an optimizing compiler might be able to do a lot better. Since your expression is a constant, it might even evaluate it at compile time.

Answer 2

Would it actually populate the list up to 200 elements?

In a naive implementation, yes.

Or does it compile it down into an equation similar to n*step + firstValue?

An optimizing Haskell compiler might do that, though I wouldn't expect an actual implementation to perform this optimization.

The point is that Haskell is so strictly formalized that it's possible to prove these two options equivalent in terms of their return value on an idealized machine, so it's up to the compiler to choose either one. The language standard (the Haskell Report) just describes what value should be returned, not how it should be computed.

Answer 3

The term "laziness" has a precise mathematical meaning which you can learn from books on call by need lambda calculus. The layman definition "nothing is evaluated until the result is needed elsewhere" is just a metaphor for newbies. It's a simplification so in complex situations like this one understanding of the full theory is required to explain what's going on.

The precise semantic requires the compiler not to evaluate list elements until a pattern match on them are performed. It's not a matter of optimization - it always must be the case. So if you calculate a !! 3, the very minimum you get (it depends on definition of a) is the following:

_ : _ : _ : 5 : _

here by _ I mean "not evaluated". You can learn to understand what is evaluated and what is not by learning lambda calculus. Until then, you can use GHCi debugger to see:

Prelude> let l = [1..10]
Prelude> let x = l !! 5
Prelude> :set -fprint-evld-with-show
Prelude> :print x
x = (_t1::Integer)
Prelude> :print l
l = (_t2::[Integer])
Prelude> x
6
Prelude> :print l
l = 1 : 2 : 3 : 4 : 5 : 6 : (_t3::[Integer])

Note that l is not evaluated at all until you print x. Print invokes show, and show performs a series of pattern matching. In this particular case the first elements of list get evaluated because of pattern matching inside implementation of [1..10] (actually it gets translated into a usual application enumFromTo 1 10). However, if we add m = map (+1) l, we note that more elements of m are unevaluated, because map has less pattern matching than [1..10]:

Prelude> let m = map (+1) l
Prelude> :print m
m = (_t4::[Integer])
Prelude> m !! 5
7
Prelude> :print m
m = (_t5::Integer) : (_t6::Integer) : (_t7::Integer) :
    (_t8::Integer) : (_t9::Integer) : 7 : (_t10::[Integer])

I repeat, it is possible to recognize easily what gets evaluated and what is not, and in what exact order evaluation is performed, but you need to learn the precise semantics - just learning a metaphor doesn't let you understand the details. The final example is

> Prelude> let ll = zipWith (+) l (tail l) Prelude> ll !! 5 13 Prelude>
> :print l l = [1,2,3,4,5,6,7,8,9,10]

So depending on (statically known!) structure of your program, many situations are possible. At the very minimum when you evaluate list !! 3, you get _ : _ : _ : 5 : _. At the very maximum you get full list evaluated : 1 : 2 : 3 : 4 : 5 : 6 : 7 : 8 : 9 : 10 : [].

I could easily construct all these 4 sample situations - so you can learn too, but it requires some math background.

Answer 4

As larsmans said it is up to the compiler, to decide what to do. But I would expect GHC to populate the list up till the 201st element. But it would not evaluate those elements.

Assuming there is a factorial function:

factorial n = product [1..n]

The following code will print the factorial of 200, it will create the first 201 cells of the list, but it will evaluate only one factorial.

print $ [ factorial n | n <- [0,1..] ] !! 201