haskell - `foldr` 和 `foldl` 的定义中使用了哪些类型的递归？

Question

foldr   ::  (a  ->  b   ->  b)  ->  b   ->  [a] ->  b
foldr   f   v   [] =    v
foldr   f   v   (x:xs)  =   f   x   (foldr  f   v   xs)

和

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

似乎使用不同类型的递归。

foldr和的定义中使用了哪些类型的递归foldl？

谢谢。

标签： haskellrecursionfold

Answer 1

foldl使用尾递归。

foldr使用受保护的递归，递归由f的惰性（如果有的话）保护。

• 另请参阅：Haskell 是否有尾递归优化？