为什么尽管尾部递归,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不应该使用:

这对测试很方便,但我们绝不会在实践中使用foldl.

...因为应用程序的thunking 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:: (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

那么,Haskell非严格评估似乎使得尾递归不那么重要.然而,我有这种感觉,对于计算列表中的项目,严格foldl应该比任何项目都要好foldr,因为我们无法从中提取任何东西Integer.

这是正确的,和尾通话是更有效的.但是,创造大型雷的成本可能超过这种好处,情况就是如此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'.