Haskell: Lazy and impatient evaluation for insert sorting

Question

I am now stuck in a question from chapter 7 of the IFPH.

This is 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 impatient and lazy recovery sequences for evaluating the expression sort [3,4,2,1] , explaining where they differ

Now I began with the first sequence of pricing reduction, which I believe is the innermost reduction.

It gives me ...

 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] 

What is a sorted list.

Now, for a lazy assessment, the only reduction sequence that I can think of is exactly the same as for the expected assessment. Of course, Haskell makes the leftmost outermost evaluation for a lazy evaluation: but I don't think it can work on most lists until the internal calculations are complete.

Is this reasoning correct? Intuition tells me no.

If someone can point out how to carry out the lazy sequence of pricing cuts, that would be great.

thanks

Answer 1

In a line containing

 insert 3 (1 : insert 4 [2]) 

You have calculated enough of the second argument for the external insert , which you can start the calculation by specifying the following line

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

and now you can run the if statement by specifying the following calculation as

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

Instead of what you have with an eager assessment:

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

Using a lazy rating, you figure out that the first element of result 1 , before sorting the rest of the list, contrast with the impatient rating, which sorts almost the entire tail of the list before it finds out that the first element.