foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f v [] = v
foldr f v (x:xs) = f x (foldr f v xs)
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f v [] = v
foldl f v (x:xs) = foldl f (f v x) xs
我正在尝试了解这两个功能。我有两个问题。一是关于功能f。一般来说，
foldr f v xs
f可以访问第一个元素xs和递归处理的尾部。这里：
foldl f v xs
f可以访问 xs 的最后一个元素和递归处理的尾部。
这是一种有用（且正确）的思考方式吗？
我的第二个问题与折叠“右”或“左”有关。在很多地方，他们说foldr“从右边开始”。例如，如果我扩展表达式
foldr (+) 0 [1,2,3]
我明白了
(+) 1 (foldr (+) 0 [2,3])
所以，我看到它是列表的“从左侧开始”。第一个元素和递归处理的尾部是函数的参数。有人可以解释这个问题吗？
f编辑：我的问题重点之一是传递给fold;的函数。链接的答案没有解决这一点。
“从右边开始”是良好的基本直觉，但它也可能会产生误导，正如您刚刚发现的那样。事实是，Haskell 中的列表是单向链接的，我们只能直接访问一侧，因此从某种意义上说， Haskell 中的每个列表操作都从左侧“开始”。但重要的是它从那里开始做什么。让我们完成foldr示例的扩展。
foldr (+) 0 [1, 2, 3]
1 + foldr 0 [2, 3]
1 + (2 + foldr 0 [3])
1 + (2 + (3 + foldr 0 []))
1 + (2 + (3 + 0))
现在同样适用于foldl.
foldl (+) 0 [1, 2, 3]
foldl (+) (0 + 1) [2, 3]
foldl (+) ((0 + 1) + 2) [3]
foldl (+) (((0 + 1) + 2) + 3) []
((0 + 1) + 2) + 3
在这种foldr情况下，我们直接进行递归调用，因此我们将头部作为累加函数的参数，然后将另一个参数作为递归调用。
在这种foldl情况下，我们通过更改累加器参数来进行递归调用。由于我们改变的是参数而不是结果，所以评估的顺序会颠倒过来。
区别在于括号“关联”的方式。在这种foldr情况下，括号与右侧关联，而在这种foldl情况下，括号与左侧关联。同样，“初始”值位于 的右侧foldr和左侧foldl。
在 Haskell 列表中使用折叠的一般建议是这样的。
foldr如果您想要尊重列表结构的惰性计算，请使用。由于foldr它的递归是在函数调用内部进行的，因此如果折叠函数恰好受到保护（即通过数据构造函数），那么我们的foldr调用就会受到保护。例如，我们可以使用foldr另一个无限列表来有效地构造一个无限列表。
对于您希望严格操作的情况，请使用foldl'（注意末尾的 ），即严格的左折叠。在继续之前强制折叠的每一步都变为弱头部正常形式，从而防止重击的产生。因此，虽然将构建整个内部表达式，然后可能在最后对其进行评估，但会按我们的方式完成工作，这可以在大型列表上节省大量内存。'foldl'foldlfoldl'
不要foldl在列表上使用。由此获得的惰性foldl几乎没有用，因为从左折叠中获得任何有用的东西的唯一方法是无论如何强制整个折叠，在内部构建重击是没有用的。
对于其他非右偏的数据结构，规则可能不同。所有这些都是在假设您Foldable是 Haskell 列表的情况下运行的。
| 归档时间： |
|
| 查看次数： |
296 次 |
| 最近记录： |