Haskell: lazy versus eager evaluation for insertion sort

Question

I'm presently stuck on a question from IFPH chapter 7.

It's Exercise 7.1.2 which reads:

"One definition of sort is to take sort = foldr insert [] where

insert x [] = [x]
insert x (y:ys) = if x <= y then x : y : ys else y : insert x ys

Give, in detail, the eager and lazy evaluation reduction sequences for the expression sort [3,4,2,1], explaining where they differ"

Now, I started with the eager evaluation reduction sequence first, which I assume is innermost reduction.

To me this yields...

sort [3,4,2,1] 
=> foldr insert [] [3,4,2,1]
=> insert 3 (foldr insert [] [4,2,1])
=> insert 3 (insert 4 (foldr insert [] [2,1]
=> insert 3 (insert 4 (insert 2 (foldr insert [] [1])))
=> insert 3 (insert 4 (insert 2 (insert 1 (foldr [] []))))
=> insert 3 (insert 4 (insert 2 (insert 1 [])))
=> insert 3 (insert 4 (insert 2 [1]))
=> insert 3 (insert 4 (1 : insert 2 []))
=> insert 3 (insert 4 (1 : [2]))
=> insert 3 (1 : insert 4 [2])
=> insert 3 (1 : 2 : insert 4 [])
=> insert 3 (1 : 2 : [4])
=> insert 3 [1,2,4]
=> 1 : insert 3 [2,4]
=> 1 : 2 : insert 2 : [4]
=> 1 : 2 : 3 : [4]
=> [1,2,3,4]

Which is the sorted list.

Now for lazy evaluation, the only reduction sequence I can think of is exactly the same as that for eager evaluation. Sure, Haskell does leftmost outermost evaluation for lazy evaluation: but I don't think that it can operate on most of the list until the inside computations are completed.

Is this reasoning correct? Intuition tells me no.

If someone could point out how to perform the lazy evaluation reduction sequence that would be great.

Thanks

Answer 1

On the line containing

insert 3 (1 : insert 4 [2])

You have computed enough of the second argument to the outer insert that you can run the computation, giving the next line

if 3 <= 1 then 3 : 1 : insert 4 [2] else 1 : insert 3 (insert 4 [2])

and you can now run the if statement, giving the next computation as

1 : insert 3 (insert 4 [2])     -- (LAZY)

Rather than what you have with eager evaluation:

insert 3 (1 : 2 : insert 4 [])  -- (EAGER)

Using lazy evaluation, you compute that the first element of the result is 1 before you sort the rest of the list - contrast with eager evaluation, which sorts nearly the entire tail of the list before it finds out what the first element is.