Haskell：插入排序的延迟求值与渴望求值

Question

我现在被IFPH第7章的一个问题困住了。

练习7.1.2内容如下：

“排序的一个定义是取

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

详细给出表达式排序[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])

您已经计算了足够多的外部插入的第二个参数，可以运行计算，并给出下一行

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-与急切评估形成对比，急切评估几乎对列表的整个尾部进行排序，然后才发现第一个元素是什么。