3

任何人都可以解释如何foldl工作？
我知道，例如，foldr (-) 0 [1,2,3]产生 (1 - (2 - (3 - 0)))，而foldl (-) 0 [1,2,3]产生 (((0 - 1) - 2) - 3)，但我还有一些问题：

  • 第一个示例（带有 foldr/foldl 的列表的长度）：
    foldr (\_ acc -> acc + 1) 0 [1,2,3,4,5]按预期生成 5。
    foldl (\_ acc -> acc + 1) 0 [1,2,3,4,5]产生6。：|
    foldl (\_ acc -> acc + 1) 0 [2]产生3。：|
    foldl 对这些给定的例子有何反应？

  • 第二个例子：
    foldr (:) [] [1,2,3,4]产生 [1,2,3,4] - 不用担心，但foldl (:) [] [1,2,3,4]给我一个错误：Occurs check: cannot construct the infinite type: a ~ [a]
    foldl 有什么问题？

4

1 回答 1

4

在foldr中，累加器是您要折叠的函数的第二个参数，但在 中foldl，累加器是第一个参数。如果您仔细查看问题的介绍性段落，您可以自己解决这个问题......

“第一个示例”代码具有误导性，因为acc参数（其名称暗示它应该是一个累加器）始终是 lambda 的第二个参数，而它应该是第一个 for foldl。这也令人困惑，因为示例列表元素的类型和值反映了累加器值的类型和值......正如评论所提到的，使用其他值会更好，最好使用其他类型！

对于“第二个示例”，您会收到类型错误，因为您的参数被交换（并且您不能拥有一个其元素是其自身列表的列表）。手动交换参数顺序：

foldl (\xs x -> x:xs)

或者使用flip为此设计的库函数：

foldl (flip (:))

请注意，foldl案例的结果应该是一个反向列表（不是复制的），因为foldl从foldr.

于 2016-06-06T17:42:32.143 回答