Concerns on lazy evaluation and infinite data structures

Question

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)

Now, 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 lazy 1 and 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?

Answer 1

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 be numsfrom n = n : numsfrom (n + 1)? Seems to me like your numsfrom will produce an infinite list of 1s.

Answer 2

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.