从具有相关值的函数中删除显式递归

Question

我有以下Haskell函数,它使用显式递归:

f :: [a] -> [a]
f (a:b:xs) = g a b : f (g a b : xs)
  where
    g :: a -> a -> a
f (_:[])   = []
f []       = []

请注意,递归调用取决于之前(by g)步骤中计算的值.

有没有办法删除显式递归,如果是,如何？

Answer 1

您的函数恰好是一个发出中间值的折叠.在Haskell中,这称为扫描.具体来说,scanl1相当于你f的第一个元素.

f = drop 1 . scanl1 g