[Haskell-cafe] help understanding lazy evaluation

[Ronald Guida]

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
                       /   \
                      /     \
                   adder    (:)--(:)--(:)
                     |       |    |    | \
                    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.
        head: adder 12 1
        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