haskell - 为什么 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 的应用程序的重击.

所以，我尝试重写 myfold作为正确的折叠:

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

但这不是尾递归。

那么，Haskell 非严格求值似乎产生了尾递归
不太重要。然而，我有这种感觉，对于列表中的项目计数，严格的 foldl应该比任何 foldr 表现更好，因为我们无法从 Integer 中提取任何内容.

总而言之，我认为这些是 map 和计数的更好实现(使用折叠):

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' .