2

我知道 Haskell 中的尾递归由于懒惰而受到一些困难。也就是说，在 Haskell 中使用尾递归是否明智？

4

2 回答 2

7

尾递归在 Haskell 中并不像在严格语言中那样简单或重要。通常，相反，您应该以编写生产函数为目标。例如，foldr通常是富有成效的

foldr f z []     = z
foldr f z (x:xs) = x `f` foldr f z xs

如果组合函数f能够懒惰地产生部分结果，那么任何消耗结果的东西也foldr可以懒惰地要求它们。一个典型的例子是“文件夹身份”

foldr (:) [] [1,2,3]          -- "force" it once
1 : {{ foldr (:) [] [2,3] }}

这{{...}}是一个懒惰的重击。比如说，如果 this 的调用上下文foldr是，head那么我们就完成了

head (foldr (:) [] [1,2,3])
head (1 : {{ foldr (:) [] [2,3] }})
1

但是，如果finfoldr是严格的，那么foldr可以线性地创建许多调用帧

foldr (+) 0 [1,2,3]
1 + {{ foldr (+) 0 [2,3] }}           -- we know it's one more than *something*
1 + (2 + {{ foldr (+) 0 [3] }})       -- ...
1 + (2 + (3 + {{ foldr (+) 0 [] }}))
1 + (2 + (3 + 0))                     -- and now we can begin to compute
1 + (2 + 3)
1 + 5
6

whilefoldl'让严格合并函数立即运行

foldl' f z []     = z
foldl' f z (x:xs) = let z' = f z x in z' `seq` foldl' f z' xs

seq噪音迫使 Haskell 像这样评估

foldl' (+) 0 [1,2,3]
foldl' (+) (1+0) [2,3]
foldl' (+) 1 [2,3]
foldl' (+) (1+2) [3]
foldl' (+) 3 [3]
foldl' (+) (3+3) []
foldl' (+) 6 []
6

这看起来很像尾递归调用。

有关更多详细信息，请参阅wiki 。

于 2013-11-03T04:42:59.083 回答
7

与这些大问题一样，答案是“视情况而定”。

例如，当您以惰性风格进行编程时，通常可以摆脱幼稚的递归

 map f (x:xs) = f x : map f xs
 map _ []     = []

实际上是如何map在标准库中定义的。这很好，因为尾递归函数产生的结果通常不能很好地懒惰，如果你做了类似的事情，尾递归映射不会终止head . map (+1) $ [1..]。

但是，有时我们不想偷懒。典型的例子是当我们太懒惰并开始构建我们真正只想评估的thunk时，例如在对列表求和时。

sum xs = someFold (+) 0 xs

现在，由于+它的论点和关联性非常严格，因此没有理由使用它，foldr但foldl'它是完美的，它是尾递归的并且严格评估，这可以显着改善空间。重要的'是，在许多尾递归函数中，每个递归步骤都会修改一个累加器，foldl'将强制它进行评估，从而防止我们的尾递归函数过于懒惰并构建 thunk。

所以这个故事的寓意是，当你懒惰地编程并产生懒惰的数据结构时，尾递归并不是什么大问题。但是，当您严格编程并在两个参数中使用严格的函数时，尾递归对于保持良好的性能非常重要。

于 2013-11-03T04:40:19.577 回答