Haskell: ленивый против энергичного вычисления для вставки рода

Question

я в настоящее время застрял на вопрос IFPH главе 7.

Это Упражнение 7.1.2, который гласит:

«Одно из определений sort является принять sort = foldr insert [] где

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

Дает, в деталях, рвется и ленивая последовательность сокращения оценки для экспрессии sort [3,4,2,1], объясняющая, где они отличаются»

Теперь я начал с первой последовательности сокращения оценки, которая, как я полагаю, внутренняя сокращение.

Для меня это дает ...

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] 

Какой отсортированный список.

Теперь для ленивой оценки единственная редукционная последовательность, о которой я могу думать, точно такая же, как и для надежной оценки. Конечно, Haskell делает самую левую самую внешнюю оценку для ленивой оценки: но я не думаю, что она может работать в большинстве списков до тех пор, пока внутренние вычисления не будут завершены.

Правильно ли это рассуждение? Интуиция говорит мне нет.

Если кто-то может указать, как выполнить ленивую последовательность оценки оценки, это было бы здорово.

Благодаря

Answer 1

На линии, содержащей

insert 3 (1 : insert 4 [2]) 

Вы вычислили достаточно второго аргумента внешней insert, что вы можете запустить вычисление, давая следующую строку

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

и теперь вы можете запустить оператор if, давая следующее вычисление как

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

Вместо того, что вы с жадной оценкой:

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

Использования ленивых вычислений, вы вычислить, что первый элемент результата 1, прежде чем сортировать остальную часть списка - контраст с жадной оценкой, который сортирует почти весь хвост списка, прежде чем он узнает, что такое первый элемент.