haskell - Foldr 和 Foldl Haskell 解释

Question

我们被要求回答 foldr 或 foldl 哪个更有效。

我不确定，但这不取决于我在做什么，特别是我想通过我的功能达到什么目的？

不同情况有区别吗？或者可以说 foldr 或 foldl 更好，因为...

有通用答案吗？

提前致谢!

Answer 1

关于这个问题的一个相当规范的来源是 Foldr Foldl Foldl'在 Haskell Wiki 上。总之，根据您组合列表元素的严格程度以及折叠的结果，您可以决定选择 foldr 或 foldl'。选择 foldl 很少是正确的选择。

一般来说，这是一个很好的例子，说明了如何必须牢记函数的惰性和严格性，以便在 Haskell 中进行高效计算。在严格的语言中，尾递归定义和 TCO 是游戏的名称，但这些类型的定义对于 Haskell 来说可能太“低效”(不够懒惰)，导致产生无用的重击和更少的优化机会。

何时选择foldr

如果使用折叠结果的操作可以延迟操作，并且您的组合函数的右参数是非严格的，那么 foldr 通常是正确的选择。典型的例子是非折叠。首先我们看到 (:) 右边是非严格的

head (1 : undefined)
1

然后这是使用 foldr 编写的 nonfold

nonfoldr :: [a] -> [a]
nonfoldr = foldr (:) []

由于 (:) 延迟创建列表，因此类似于 head 的表达式。 nonfoldr 非常高效，只需要一个折叠步骤并仅强制输入列表的头部。

head (nonfoldr [1,2,3])
head (foldr (:) [] [1,2,3])
head (1 : foldr (:) [] [2,3])
1

短路

懒惰获胜的一个非常常见的地方是短路计算。例如，lookup::Eq a => a -> [a] -> Bool 通过在看到匹配项时立即返回，可以提高工作效率。

lookupr :: Eq a => a -> [a] -> Bool
lookupr x = foldr (\y inRest -> if x == y then True else inRest) False

发生短路是因为我们在 if 的第一个分支中丢弃了 isRest。在 foldl' 中实现的相同功能无法做到这一点。

lookupl :: Eq a => a -> [a] -> Bool
lookupl x = foldl' (\wasHere y -> if wasHere then wasHere else x == y) False

lookupr 1 [1,2,3,4]
foldr fn False [1,2,3,4]
if 1 == 1 then True else (foldr fn False [2,3,4])
True

lookupl 1 [1,2,3,4]
foldl' fn False [1,2,3,4]
foldl' fn True [2,3,4]
foldl' fn True [3,4]
foldl' fn True [4]
foldl' fn True []
True

何时选择foldl'

如果消费操作或组合要求在继续之前处理整个列表，那么 foldl' 通常是正确的选择。通常，针对这种情况的最佳检查是问问自己，您的组合函数是否严格——如果第一个参数严格，那么无论如何都必须强制执行整个列表。典型的例子是 sum

sum :: Num a => [a] -> a
sum = foldl' (+) 0

因为 (1 + 2) 在实际进行加法之前无法合理消耗(Haskell 不够聪明，无法知道 1 + 2 >= 1 没有首先评估 1 + 2)，那么我们就不会从使用 foldr 中获得任何好处。相反，我们将使用 foldl' 的严格组合属性来确保我们根据需要急切地评估事物

sum [1,2,3]
foldl' (+) 0 [1,2,3]
foldl' (+) 1 [2,3]
foldl' (+) 3 [3]
foldl' (+) 6 []
6

请注意，如果我们在这里选择foldl，我们不会得到完全正确的结果。虽然 foldl 与 foldl' 具有相同的关联性，但它不会像 foldl' 那样强制与 seq 进行组合操作> 是的。

sumWrong :: Num a => [a] -> a
sumWrong = foldl (+) 0

sumWrong [1,2,3]
foldl (+) 0 [1,2,3]
foldl (+) (0 + 1) [2,3]
foldl (+) ((0 + 1) + 2) [3]
foldl (+) (((0 + 1) + 2) + 3) []
(((0 + 1) + 2) + 3)
((1       + 2) + 3)
(3             + 3)
6

当我们选择错误时会发生什么？

如果我们在 foldl' 最佳位置时选择 foldr 或 foldl，我们会得到额外的、无用的重击(空间泄漏)，并且我们会得到额外的，如果我们在 foldr 是更好的选择时选择 foldl'，则无用的评估(时间泄漏)。

nonfoldl :: [a] -> [a]
nonfoldl = foldl (:) []

head (nonfoldl [1,2,3])
head (foldl (:) []  [1,2,3])
head (foldl (:) [1]   [2,3])
head (foldl (:) [1,2]   [3])  -- nonfoldr finished here, O(1)
head (foldl (:) [1,2,3]  [])
head [1,2,3]
1                             -- this is O(n)

sumR :: Num a => [a] -> a
sumR = foldr (+) 0

sumR [1,2,3]
foldr (+) 0 [1,2,3]
1 + foldr (+) 0 [2, 3]      -- thunks begin
1 + (2 + foldr (+) 0 [3])
1 + (2 + (3 + foldr (+) 0)) -- O(n) thunks hanging about
1 + (2 + (3 + 0)))
1 + (2 + 3)
1 + 5
6                           -- forced O(n) thunks