Demonstrating Lazy evaluation in Haskell?

Question

This is a question from one of my homework assignments that I haven't been able to answer. It's to do with reasoning about Haskell code by demonstrating how the Haskell compiler (interpreter?) executes programs.

I'm given a few different functions...

-- built-in
take :: Int -> [a] -> [a] 
take 0 _ = [] 
take n (x:xs) = x : (take (n - 1) xs) 

-- exchanging entries
exchange :: [a] -> [a] 
exchange [x,y] = [y,x] 
exchange (x:y:xs) = (y:x:(exchange xs))

-- picking even numbered entries
evens :: [a] -> [a] 
evens [x,y] = [x] 
evens (x:_:xs) = x:(evens xs) 

-- first four numbers repeated
first_four :: [Int] 
first_four = 1:2:3:4:first_four 

Now I have to demonstrate understanding of Lazy Evaluation by "pretending to be the compiler". By breaking down how this statement would be executed...

> take 5 (evens (exchange first_four))
[2,4,2,4,2] 

I'm given the first few lines to help get started...

take 5 (evens (exchange first_four)) =
take 5 (evens (exchange (1:2:3:4:first_four))) =
take 5 (evens (2:1:(exchange (3:4:first_four)))) =
...

I'd like some help with understanding how lazy evaluation works so I can do this question.

Answer 1

Treat your definitions as re-write equations, and always (uniquely) name the interim entities as they come into play:

take 5 (evens (exchange first_four))
  -- match: take 0 .... = ....    ? FAIL
  -- match: take n (x:xs) = ....   ? SUCCESS
  n1 = 5 
  (x1:xs1) ?= evens (exchange first_four)   
    -- evens [x,y] = ....
    [x2,y2] ?= exchange first_four
      -- exchange [x,y] = ....
      [x3,y3] ?= first_four
  ......

etc. The operation is mechanical. "Laziness" here means, we proceed left-to-right, never trying to find out values of expressions too soon, only doing so when we actually need to pattern match some definition with them.

Here's what I meant by "naming" the interim entities:

take 5 (evens (exchange first_four)) =
take 5 xs   where xs = evens (exchange first_four)
       (x1:xs1) ?= xs  -- <---- THIS
                 = evens (exchange first_four)
                 = evens ys   where ys = exchange first_four
                         [x2,y2] ?= ys  -- <--- AND THIS
                         .     .  = exchange first_four
                         .     .          -- ^^ <--- already named
                         .     .       [x3,y3] ?= first_four
                         .     .               FAIL
                         .     .       (x3:y3:xs3) ?= first_four
                         .     .                    = 1:2:3:4:first_four
                         .     .               SUCCESS: x3=1
                         .     .                        y3=2
                         .     .                        xs3=3:4:first_four
                         .     .   ys = y3:x3:exchange xs3   !
                         .     .   [] ?= exchange xs3
                         .             = ...
                         .             FAIL
                         (x2:_:xs2) ?= ys
                                       SUCCESS: x2=y3
                                                xs2=...

Of course working to this fine details resolution is very tiresome and seldom needed, only perhaps to track some "timing" issues; it is easier to see what each definition does, separately, and treat them as separate producers connected in a chain.

By "timing" I mean, whether the "inner" producer is ready to produce its element when the "outer" one needs it. because if not, the whole process becomes stuck, "non-productive". Here the most inner producer is an infinite stream, directly defined, so there's no such problems.

So mentally, we could say to ourselves: "first_four is infinite repeating stream of 1 to 4; exchange swaps each pair of elements it gets; evens throws away every element in odd position; take takes n elements".

So actually, it turns out you were right all along.

Because of how the definitions are written, evens forces out of exchange its output elements in groups of four, more or less. Mainly, the culprit is the unnecessary matching for [x,y] in evens and exchange, which demands three elements from its input, to see whether the tail is empty ([]) or not.

evens demands three elements, but exchange only knows how to produce them by pairs.

But exchange too demands at least three elements from its supplier. So, coarsely:

take 5 (evens (exchange first_four))
take 5 (evens (exchange first_four))
take 5 (evens (exchange (1:2:3:(4:first_four)))
take 5 (evens (2:1:exchange (3:4:1:(2:3:4:first_four))))
take 5 (evens (2:1:4:(3:exchange (1:2:3:4:first_four))))
take 5 (2:evens (4:3:exchange (1:2:3:4:first_four)))
2:take 4 (evens (4:3:exchange (1:2:3:4:first_four)))
2:take 4 (evens (4:3:2:(1:exchange (3:4:first_four))))
2:take 4 (4:evens (2:1:exchange (3:4:first_four)))
2:4:take 3 (evens (2:1:exchange (3:4:1:(2:3:4:first_four))))
2:4:take 3 (evens (2:1:4:(3:exchange (1:2:3:4:first_four))))
2:4:take 3 (2:evens (4:3:exchange (1:2:3:4:first_four)))
........

I'm sure you can finish this now. :)

To illustrate, here's exchange looked at procedurally, as a stream transformer, which can pull an element from its input; peek whether its input has an element ready to be pulled; and push an element into its output.

exchange:
   pull(X)  ...  on_fail: ERROR
   pull(Y)  ...  on_fail: ERROR
   peek     ...  on_fail: push(Y); push(X); STOP
   push(Y); push(X)
   LOOP