尾递归,我应该在Haskell中使用它

Question

我知道Haskell中的尾递归由于它的懒惰而受到一些困难.也就是说,在Haskell中使用尾递归是否合理？

Answer 1

像往常一样,这些重大问题的答案是"它取决于".

例如,当你以懒惰的方式编程时,你通常可以逃避天真的递归

 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.

所以故事的寓意,当你懒洋洋地编程和生产懒数据结构,尾递归是没有什么大不了的.但是当你严格编程并在两个参数中使用严格函数时,尾递归对于保持良好的性能非常重要.

Answer 2

尾部递归在Haskell中并不像在严格的语言中那样直接或大.通常,您应该以编写生产函数为目标.例如,foldr通常是富有成效的

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

如果组合函数f能够懒惰地产生部分结果,那么消耗结果的任何东西都foldr可以懒得地要求它们.一个典型的例子是"foldr identity"

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

这{{...}}是一个懒惰的thunk.如果这个的调用上下文foldr是,head那么我们就完成了

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

但是,如果fin foldr是严格的,那么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

同时foldl'让严格的组合功能立即运行

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

如该seq噪声力量哈斯克尔评估这样

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

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

有关详细信息,请参阅维基.