How does lazy evaluation works when the argument is a list?

2
votes

From my understanding, lazy evaluation is the arguments are not evaluated before they are passed to a function, but only when their values are actually used.

But in a haskell tutorial, I see an example.

xs = [1,2,3,4,5,6,7,8] 

doubleMe(doubleMe(doubleMe(xs)))

The author said an imperative language would probably pass through the list once and make a copy and then return it. Then it would pass through the list another two times and return the result.

But in a lazy language, it would first compute

doubleMe(doubleMe(doubleMe(1)))

This will give back a doubleMe(1), which is 2. Then 4, and finally 8.

So it only does one pass through the list and only when you really need it.

This makes me confused. Why don't lazy language take the list as a whole, but split it? I mean we can ignore what the list or the expression is before we use it. But we need to evaluate the whole thing when we use it, isn't it?

1
haskelllazy-evaluation

1 Answers

6
votes

A list like [1,2,3,4,5,6,7,8] is just syntactic sugar for this: 1:2:3:4:5:6:7:8:[].

In this case, all the values in the list are numeric constants, but we could define another, smaller list like this:

1:1+1:[]

All Haskell lists are linked lists, which means that they have a head and a tail. In the above example, the head is 1, and the tail is 1+1:[].

If you only want the head of the list, there's no reason to evaluate the rest of the list:

(h:_) = 1:1+1:[]

Here, h refers to 1. There's no reason to evaluate the rest of the list (1+1:[]) if h is all you need.

That's how lists are lazily evaluated. 1+1 remains a thunk (an unevaluated expression) until the value is required.