尽管 foldl 是尾递归的，但为什么它似乎是有害的？

Question

我一直认为尾递归函数在以下方面更好性能优于非尾递归版本。因此，对列表中的项目进行计数 可能会 像这样实现：

count:: [a] -> Int
count [] = 0
count (x:xs) = 1 + count xs

但是这个函数不是尾递归的，所以性能不是很好。解决方法是累积计数，如下所示：

_count:: Num b => b -> [a] -> b
_count b [] = b
_count b (x:xs) = _count (b + 1) xs

count:: [a] -> Int
count = _count 0

这可以通过尾递归折叠轻松实现：

myfold:: (b -> a -> b) -> b -> [a] -> b
myfold f b [] = b
myfold f b (x:xs) = myfold f (f b x) xs

count = myfold incr 0
   where incr c _ = c + 1

但是，然后我想起了一些关于左折叠和右折叠的事情。结果是 myfold 是左折，根据 Real World Haskell 不应使用：

This is convenient for testing, but we will never use foldl in practice.

...因为 f b x.

的应用程序的 thunking

因此，我尝试将 myfold 重写为右折：

myfoldr:: (a -> b -> b) -> b -> [a] -> b
myfoldr f b [] = b
myfoldr f b (x:xs) = f x (myfoldr f b xs)

但这不是尾递归。

看来，Haskell 非严格求值使得尾递归不太重要。然而，我有这种感觉，对于 counting 列表中的项目，严格的 foldl 应该比任何 foldr 表现得更好，因为我们无法从列表中提取任何东西Integer.

总而言之，我认为这些是 map 和 count 的更好实现（使用折叠）：

map:: (a -> b) -> [a] -> [b]
map f = foldr g []
  where g x fxs = (f x):fxs

count:: [a] -> Int
count = foldl incr 0
  where incr c _ = c + 1

这是正确的吗？

Answer 1

It seems, then, that Haskell non-strict evaluation makes tail-recursiveness less important. Yet, I have this feeling that for counting items in lists a strict foldl should perform better than any foldr, because there's no way we can extract anything from an Integer.

这是正确的，尾调用更有效。但是创建大型 thunk 的成本可能会抵消这种好处，foldl.

就是这种情况。

既要吃蛋糕又要吃蛋糕的方法是确保累加器没有被敲击，而是急切地求值：

myfold:: (b -> a -> b) -> b -> [a] -> b
myfold f !b [] = b
myfold f !b (x:xs) = myfold f (f b x) xs

这当然是 foldl' 函数。

TL;DR：永远不要使用 foldl，但一定要使用 foldl'。

尽管 foldl 是尾递归的，但为什么它似乎是有害的？

Why does foldl seems to be harmful despite being tail-recursive?

recursion

haskell

fold