gpt4 book ai didi

Haskell:插入排序的惰性求值与急切求值

转载 作者:行者123 更新时间:2023-12-04 07:07:04 35 4
gpt4 key购买 nike

我目前被 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 对惰性求值进行最左外层求值:但我认为在内部计算完成之前,它不能对列表的大部分进行操作。

这个推理正确吗?直觉告诉我没有。

如果有人能指出如何执行延迟评估减少序列,那就太好了。

谢谢

最佳答案

在包含的行上

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在对列表的其余部分进行排序之前 - 与急切评估形成对比,后者在找出第一个元素是什么之前对列表的几乎整个尾部进行排序。

关于Haskell:插入排序的惰性求值与急切求值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10681507/

35 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com