Haskell: vago frente a la evaluación ávido de ordenación por inserción

Question

estoy actualmente atascado en una pregunta del capítulo 7. IFPH

Es Ejercicio 7.1.2 que dice:

"Una definición de sort es tomar sort = foldr insert [] donde

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

Give, en detalle, las secuencias de reducción de evaluación ansiosos y perezosos para la expresión sort [3,4,2,1], explicando en lo que difieren"

Ahora, comencé con la secuencia de reducción de evaluación entusiasta primero, que supongo que es más interna reducción.

Para mí esto rendimientos ...

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] 

¿Qué es la lista ordenada.

Ahora, para la evaluación perezosa, la única secuencia de reducción que puedo pensar es exactamente la misma que para la evaluación entusiasta. Claro, Haskell hace la evaluación más extrema a la izquierda para la evaluación perezosa: pero no creo que pueda operar en la mayor parte de la lista hasta que se completen los cálculos internos.

¿Este razonamiento es correcto? La intuición me dice que no.

Si alguien pudiera señalar cómo realizar la secuencia de reducción de evaluación lenta que sería genial.

Gracias

Answer 1

En la línea que contiene

insert 3 (1 : insert 4 [2]) 

Has calculado suficiente del segundo argumento al exterior insert que puede ejecutar el cálculo, dando la siguiente línea

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

y ahora puede ejecutar la instrucción if, dando el siguiente cálculo como

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

En lugar de lo que se tiene con la evaluación ansiosos:

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

El uso de la evaluación perezosa, a calcular que el primer elemento del resultado es 1 antes de ordenar el resto de la lista - contraste con la evaluación ansiosos, que ordena casi toda la cola de la lista antes de descubrir cuál es el primer elemento.