haskell-cafe@haskell.org
[Top] [All Lists]

Re: [Haskell-cafe] help understanding lazy evaluation

Subject: Re: [Haskell-cafe] help understanding lazy evaluation
From: Ronald Guida
Date: Thu, 23 Aug 2007 08:14:41 -0400
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

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@xxxxxxxxxxx
http://www.haskell.org/mailman/listinfo/haskell-cafe

<Prev in Thread] Current Thread [Next in Thread>