# Concerns on lazy evaluation and infinite data structures

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?

• Chapter 4.2 in SICP discusses implementing lazy evaluation, lazy streams, non-deterministic search and other related topics. Aug 14, 2016 at 16:02

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 `1`s.

• The side note's right thanks. But could you explain step by step what's going on when I first define `squares` (what's stored as `squares`? A thunk?), and what steps take place when `take 5 squares` is executed? Aug 14, 2016 at 16:36
• Oh wait. I think I got it. The return of `n : numsfrom (1 + n)` is `[n, thunk(numsfrom (1 + n))]`, not `[n, resultof numsfrom (1 + n)]`. This is why an infinite loop isn't started and it also explains how can it `take` a limited number of an infinite list, because `map f (x : xs)` returns `[f x, thunk(map f xs)]`, not `[f x, map f xs]`. Wonderful! Aug 14, 2016 at 17:30

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.