2

我不确定这两段代码之间的区别是什么（相对于x），但第一个完成：

$ foldr (\x y -> if x == 4 then x else x + y) 0 [1,2 .. ]
10

而第二个没有（至少在 GHCi 中）：

$ foldr (\x (y, n) -> if x == 4 then (x, n) else (x + y, n + 1)) (0, 0) [1,2 .. ]
.......

我做错了什么，阻止了第二个例子在它命中时完成x == 4，就像第一个例子一样？

我已经尝试在 thex和x == 4(inside a let) 中添加爆炸模式，但似乎都没有什么不同。

4

3 回答 3

4

你的第二个例子有两个相关的问题。

回想一下，它foldr产生了一个右关联嵌套，即foldr f z [a, b, c]= f a (f b (f c z))。因此，您给出的函数的第二个参数foldr表示折叠整个剩余列表的最终值。在无限列表的情况下，这只有在您生成另一个惰性无限数据结构或在某些时候完全忽略第二个参数时才有可能，就像您的第一个示例一样。

您的第二个示例始终使用输入元组中的第二项来计算结果元组的第二项，因此当应用于无限列表时，您最终会得到无限回归。指定0为“起始”值无济于事，因为foldr起始值位于列表的末尾，而无限列表显然没有 - 似乎您想将值不变地传递，但是需要有一个值来开始（或者可能是“结束”）！

这只会导致结果中的第二项是非终止的。结果的第一项是明确定义的，或者至少可以是。这里的问题是模式匹配强制评估，这会阻止在整个折叠完成之前产生任何结果。这可以通过多种方式避免，但简单地使用fstandsnd就足够简单了：\x yn -> if x == 4 then (x, snd yn) else (x + fst yn, snd yn + 1)应该给您一个包含一个元组的结果，该元组的第一项是您所期望的（但其第二项未定义，如上所述）。

于 2012-10-24T17:01:44.803 回答
3

第一个不使用“累加器”中的值（即y），而第二个使用n. 计算n需要折叠整个列表，这就是它永远不会终止的原因。再多的严格也无法解决这个问题。

事实上，你的算法并没有像你认为的那样做。您可能将foldr's 行为与foldl. 即使你能以某种方式计算n，它的价值也将是无限的。最好的思考方式foldr是用第一个函数替换列表中的每个，用第二个值(:)替换终端。[]

于 2012-10-24T16:52:23.167 回答
3

这是模式匹配/评估发生的方式。如果你让f = \x (y, n) -> ...你定义它，那么

foldr f (0, 0) [1,2 .. ] =
   f 1 (foldr f (0,0) [2..]) =
   (\x (y, n) -> ...) 1 (foldr f (0,0) [2..])

并且该(y,n)模式是严格匹配的，因此要计算任何东西，需要计算第二个参数 ( foldr .. [2..])，然后需要计算，foldr .. [3..]以此类推。

可以使用~（称为“无可辩驳的模式”）使模式匹配不严格，这会在一定程度上改变行为。

> foldr (\x ~(y,n) -> if x == 4 then (x,n) else (x+y,n+1)) (0,0) [1..]
(10,

（因为可反驳的版本甚至无法计算元组的第一个元素。）

于 2012-10-24T16:57:32.450 回答