haskell - 折叠是左尾递归吗？

Question

我想问，函数foldl是否是尾递归？

当我查看源代码时，foldl是如何实现的:

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

它看起来像尾递归。

左折叠始终保持关联。假设我有以下表达式:

foldl (*) 1 [1..3]

然后它将评估为:

((1 * 1) * 2) * 3

然后写出步骤，我想要:

foldl (*) 1 [1..3] =
foldl (*) (1 * 1) [2,3]
foldl (*) (1 * 2) [3]
foldl (*) (2 * 3) []
6

不像((1 * 1) * 2) * 3，还是我错了？

Answer 1

当f严格时，

foldl表示尾递归。你是对的，最好有更

foldl (*) 1 [1,2,3] = 
foldl (*) 1 [2,3]   = 
foldl (*) 2 [3]     = 
foldl (*) 6 []      = 
6 

如果 f 不严格，即保留其参数表达式不变，以便稍后计算，则最终会得到像 (((1*1)*2 这样的嵌套表达式)*3)，当最终计算它们时，这甚至可能不必要地导致堆栈溢出，因为要计算此类嵌套表达式，必须使用堆栈:

(((1*1)*2)*3) 
=> x * 3 where x = ((1*1)*2)
            => x = y*2 where y = 1*1
                             y <= 1
            => x = 1*2
            <= x = 2
=> 2 * 3
<= 6

无论如何，当中间结果已经可以得到全面评估时，再多的努力都是浪费。

另请参阅:Does Haskell have tail-recursive optimization?

编辑: foldl' 必须始终用于此目的，as noted通过 user:chi在评论中。