haskell - 如何在需要以不同方式处理第一个元素的递归调用中创建列表？

Question

我正在使用 Haskell 学习函数式编程。我正在尝试创建一个函数，该函数采用函数 f，并在某个输入 x、n 上执行该函数的次数。

repeat :: (a -> a) -> a -> Int -> [a]
repeat f x n

所以，输出列表是这样的:

[x, f(x), f(f(x)), ..., f^n(x)]

到目前为止，我已经能够提出一个我相信可以做到这一点的功能。它执行 n 次:

fn f a n = f a : fn f (f a) (n-1)

我现在遇到的问题是我希望列表的第一个元素只是 x。现在，它从 f(x) 开始我的列表。我试着到处玩，但我不确定如何在 Haskell 中覆盖这个“基本”案例。有人可以帮忙吗？

Answer 1

您在两个地方应用该函数:一次在“简单”的第一个元素案例中，再次在递归中。

fn f a n = f a : fn f (f a) (n-1)
           ^^^         ^^^

如果您希望第一个元素是 a ，只需删除第一个；你不需要它。

fn f a n = a : fn f (f a) (n-1)

现在我们有了一个工作函数，但它将永远运行。您还需要一个基本案例。如果我们告诉一个函数重复零次，我们应该得到空列表。

fn _ _ 0 = []
fn f a n = a : fn f (f a) (n-1)

最后，为了可读性和通常的 Haskell 编码标准，我们希望给这个东西一个类型签名。最普遍的可能类型，我们可以从 ghci 中查询是

*Main> :t fn
fn :: (Eq t1, Num t1) => (t2 -> t2) -> t2 -> t1 -> [t2]

但是我们极不可能用非 Int 来称呼这个东西。值，并且额外的类型类可能只会在稍后尝试调用推理引擎时混淆，所以我建议

fn :: (a -> a) -> a -> Int -> [a]
fn _ _ 0 = []
fn f a n = a : fn f (f a) (n-1)