折叠左尾递归？

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

foldl表示f严格时表示尾递归。你是正确的，它是最好多有

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'必须始终user:chi在评论中使用该，as noted。