[Haskellcafe] 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
/ \
/ \
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 !! (n1)
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
More information about the HaskellCafe
mailing list