foldr&foldl Haskell解释

Question

我们已被要求回答是否foldr或者foldl是更有效的.

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

不同情况是否存在差异,或者可以说是foldr或foldl更好,因为......

有一般答案吗？

提前致谢!

Answer 1

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

通常,这是一个很好的例子,说明如何在Haskell中有效地计算函数的懒惰和严格性.在严格的语言中,尾递归定义和TCO是游戏的名称,但是对于Haskell而言,这些定义可能过于"无效"(不够懒惰)导致产生无用的thunk并且优化机会更少.

什么时候选择 foldr

如果消耗折叠结果的操作可以懒惰地操作而且你的组合函数在其正确的参数中是非严格的,那么foldr通常是正确的选择.这方面的典型例子是nonfold.首先,我们看到(:)右边是非严格的

head (1 : undefined)
1

然后这里nonfold写的使用foldr

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

发生短路是因为我们isRest在第一个分支中丢弃了if.实施的同样的事情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',它不会强制组合操作与seq喜欢foldl'做.

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

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

如果我们选择foldr或foldl在foldl'最佳位置时我们得到额外的,无用的thunk(空间泄漏),如果我们选择foldl'什么时候foldr是更好的选择,我们会得到额外的,无用的评估(时间泄漏).

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

Answer 2

在具有严格/急切评估要求的语言中，可以从左向折叠在恒定的空间中进行，而从右向折叠需要线性的空间（超过列表中的元素数）。因此，许多初次使用Haskell的人都接受了这个先入之见。

但是，由于懒惰的评估，该经验法则在Haskell中不起作用。在Haskell中，可以使用编写常量空间函数foldr。这是一个例子：

find :: (a -> Bool) -> [a] -> Maybe a
find p = foldr (\x next -> if p x then Just x else next) Nothing

让我们尝试手动评估find even [1, 3, 4]：

-- The definition of foldr, for reference:
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)

find even (1:3:4:[])
    = foldr (\x next -> if even x then Just x else next) (1:3:4:[])
    = if even 1 then Just 1 else foldr (\x next -> if even x then Just x else next) (3:4:[])
    = foldr (\x next -> if even x then Just x else next) (3:4:[])
    = if even 3 then Just 3 else foldr (\x next -> if even x then Just x else next) (4:[])
    = foldr (\x next -> if even x then Just x else next) (4:[])
    = if even 4 then Just 4 else foldr (\x next -> if even x then Just x else next) []
    = Just 4

中间步骤中表达式的大小具有恒定的上限-实际上这意味着可以在恒定的空间中执行此求值。

foldr在Haskell中可以在恒定空间中运行的另一个原因是由于GHC中的列表融合优化。在许多情况下，GHC可以优化foldr恒定空间生成器上的恒定空间循环。它通常不能左折。

尽管如此，Haskell中的左折可以编写为使用尾部递归，这可以带来性能上的好处。事实是，要使此方法真正成功，您需要非常小心惰性-由于未评估表达式的堆积，天真地尝试编写尾递归算法通常会导致线性空间执行。

外卖课程：

1. 在开始使用Haskell时，请尝试Prelude并Data.List尽可能多地使用库函数，因为它们经过精心编写以利用诸如列表融合之类的性能功能。
2. 如果您需要折叠列表，请先尝试foldr。
3. 请勿使用foldl，请使用foldl'（避免未计算表达式的版本）。
4. 如果要在Haskell中使用尾部递归，首先需要了解评估的工作原理，否则可能会使情况变得更糟。