I am trying to learn how lazy evaluation works because I’m going to
implement try to implement it in the programming language I’m developing (I know it isn’t the best thing to do (to try to implement something you don’t even understand) but it’s making for a good extensive lesson through the world of functional languages and the like), so I was reading the paper A Gentle Introduction to Haskell.
Soon I encountered the paragraph on the non-strictness of Haskell functions and the possibility of creating teorethically infinite data structures, as shown in this example:
numsfrom n = 1 : numsfrom (n + 1) squares = map (^ 2) (numsfrom 0)
take 5 squares would return
[0, 1, 4, 9, 16], right? Well, my problem is understanding how it would do it.
First things first, this is what I understood of lazy evaluation:
lazy = lambda x, y: x or y
Assuming Python was non-strict, if I passed to
5 ** 1000000 the second parameter would not get evaluated, but it would get evaluated if I passed
False as the first argument, because
or would then have requested it.
So when calling
take 5 squares,
squares has to be evaluated:
map is called with
(^ 2) and
(numsfrom 0) as the arguments; But since
map uses it’s second argument,
numsfrom 0 will be evaluated, starting an infinite loop.
I cannot understand how would
map return if it’s evaluating an infinite loop, and what it would return. Can someone please explain me it?
You have the fundamental concept absolutely correct. The problem is that you’re not applying it on a large enough scale.
In Haskell, everything (or close enough for the purposes of this question and answer) behaves the way that
or does in Python (and many, many languages). Including, say, “Get me the next element of the list”.
So when you call
numsfrom, in fact, the result of
numsfrom is not created immediately and returned. It is produced as needed on an element-by-element basis. The function
numsfrom can be partially evaluated, piece by piece, as the result is needed. Since
map doesn’t ask for an infinite number of elements, there is no infinite looping going on. This is similar to iterators I believe in Python.
As a side note, shouldn’t
numsfrom n = n : numsfrom (n + 1)? Seems to me like your
numsfrom will produce an infinite list of
The trick is that any data constructor in Haskell is lazy (unless annotated otherwise). In your case, the list constructor
(:) :: a -> [a] -> [a]
So when you evaluate
take 5 squares (remember Haskell lists are linked lists), you evaluate the first five
(:) constructors, but the rest is kept as an unevaluated thunk.