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案例的结果应该是一个反向列表(不是复制的),因为foldlfoldr.

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