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

Question

我有一个使用显式递归的Haskell函数，代码如下：

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

请注意，递归调用取决于之前步骤中计算出的值（由g计算得出）。

是否有一种方法可以消除显式递归？如果有，该如何实现？

- Sven Koschnicke

---

什么是基本情况？ - GS - Apologise to Monica

请看我的编辑。我想我已经添加了它们。 - Sven Koschnicke

Answer 1

你的函数实际上就是一个发射中间值的折叠函数，在Haskell语言中，这被称为扫描（scan）。具体来说，scanl1与你的 f 函数相同，只是第一个元素不同。

f = drop 1 . scanl1 g

- Emil Vikström

---

我需要 tail，否则它就会变成 f (a:b:xs) = a : g a b : f (g a b : xs)，对吗？ - Sven Koschnicke

Sven，大概就是这样。scanl1输出第一个元素而不应用g，而你的f跳过了它。Ganesh，我会修复它。忘记了tail不能在空列表上工作。 - Emil Vikström

Answer 2

使用尾递归，ghc可以进行优化

f (a:b:xs) acc = f (g a b : xs) (g a b : acc)
f _ acc = reverse acc

并调用如此

f myList []

- user3177338