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

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)

Answer 2

我建议用两个函数来实现这一点：一个是我们构造一个无限列表，所以(a -> a) -> a -> [a]，然后我们可以构造一个Int -> [a] -> [a]接受前n项的函数。这两个函数都存在于 Haskell 的base包中。事实上，该fn函数被实现为iterate :: (a -> a) -> a -> [a]和take :: Int -> [a] -> [a]。

我们可以实现iterate为：

iterate :: (a -> a) -> a -> [a]
iterate f = go
    where go x = x : go (f x)

因此，这里x :产生x并进行递归调用，go (f x)因此递归调用将产生f(x)，然后f(f(x))，等等。

该take函数可以实现为：

take :: Int -> [a] -> [a]
take n _ | n <= 0 = []
take _ [] = []
take n (x:xs) = x : take (n-1) xs

那么你的fn函数是：

fn :: (a -> a) -> a -> Int -> [a]
fn f x n = take n (iterate f x)

现在我们有两个额外的实用函数可以使用，但它们本身并不用于我们的fn函数。