# [Haskell-cafe] help understanding lazy evaluation

Ronald Guida ronguida at mindspring.com
Thu Aug 23 08:14:41 EDT 2007

```I'm trying to understand lazy evaluation as well.  I created an
example for myself and I'm wondering if I've got it right.

> let adder n = \x -> n + x in (map (adder 12) [1,2,3]) !! 1

So the first thing I did is draw a graph to represent my expression.

(map (adder 12) [1,2,3]) !! 1 =
|
(!!)
----/    \
/          1
map
/   \
/     \
|       |    |    | \
12       1    2    3  []

In order to proceed, I need definitions for adder, map and (!!).

adder n = \x -> n + x

map f [] = []
map f (x:xs) = (f x) : xs

(x:xs) !! 0 = x
(x:xs) !! n = xs !! (n-1)

Here is how I think the evaluation would proceed:

0 => (map (adder 12) [1,2,3]) !! 1

The top node is (!!).  In order to evaluate (!!), I need to
expand the left hand side to get at least the first node of a
list.  I'll expand "map".

1 => ( (adder 12 1) : (map (adder 12) [2,3]) ) !! 1

I evaluated "map" once to get a list with an expression for the
head and an expression for the tail.
tail: map (adder 12) [2,3]

I proceed to evaluate (!!) for one step; this time n /= 0 so I
extract the tail of the list and recursively call (!!).

2 => ( (map (adder 12) [2,3]) ) !! 0

The top node is (!!) again.  I need to expand "map" again.

3 => ( (adder 12 2) : (map (adder 12) [3]) ) !! 0

I evaluate (!!) and this time n == 0 so I match the base case for
(!!) and take the head of the list.

4 => adder 12 2
=> (adder 12) 2

In order to proceed, I need to expand (adder 12).  The adder
function take one argument, "12", and produces a closure.  I'll
express it as a "let" expressions.

Note: It is at this point (steps 4 to 7) that I'm confused about
what's supposed to happen with closures and let expressions.

5 => (let n = 12 in \x -> n + x) 2

I'll substitute "2" into the let statement.

6 => (let n = 12 in n + 2)

I'll substitute "12" for "n".

7 => 12 + 2
8 => 14

Can anyone tell me if I've got this right?

-- Ron

```