如何创建一个函数来生成整数序列的无限列表，该列表使用两个初始数字 X_0 和 X_1 递归定义

Question

假设我有以下整数序列的递归定义：a_0 = 5, a_n = 2a_0+3 -> 5,13,29,61,125...

我想使用Haskell中的iterate函数生成这个序列的无限列表。为此，我可以编写以下代码：

intSequence :: Integer -> Integer -> [Integer]
intSequence a0 m = iterate nextNum a0
  where nextNum a = 2*a + m

ghci> let an = intSequence 5 3
ghci> take 5 a
[5,13,29,61,125]

现在假设我有以下内容：

X_n = X_n-1 * m_1 + X_n-2 * m_2 + a

现在我想创建一个按以下方式调用的函数：

intSequence x0 x1 m1 m2 a

那 returns 一个遵守上述定义规则的序列的无限列表。

例如： 对于参数 X0=1, X1=2, m1=2, m2=0, a=0 我们得到 Xn=X_n-1 * 2 + X_n-2 * 0 + 0 = X_n-1 * 2 这给了我们 [1,2,4,8,16,...]

另一个例子： 对于参数 X0=0, X1=1, m1=1, m2=1, a=0 我们得到斐波那契数列 X_n = X_n-1 * 1 + X_n-2 * 1 + 0 = X_n-1 + X_n-2 它给我们 [0,1,1,2,3,5,8,...]

如何使用 iterate 实现此 intSequence 功能？

我尝试了以下方法，但效果不佳：

intSequence :: Integer -> Integer -> Integer -> Integer -> Integer -> [Integer]
intSequence x0 x1 m1 m2 a = x0:x1:iterate (nextNum x0) x1
  where
    nextNum x0' x1' = x1'*m1 + x0'*m2 + a

ghci> a = intSequence 0 1 1 1 0
ghci> take 10 a
[0,1,1,1,1,1,1,1,1,1]

这显然是不正确的，也不符合逻辑，因为我从不更改 x0 和 x1 是什么。我想我需要以某种方式使用递归，但我不知道如何使用。我应该根本不使用 iterate 吗？

Answer 1

使用递归更容易做到这一点：

-- helper function for recursion
intSequence' :: (Integral a) => (a, a) -> a -> a -> a -> [a]
-- p2 is X_n-2 and p1 is X_n-1
intSequence' (p2, p1) m1 m2 a =
    -- recurse using X_n-1 as new X_n-2 and current term as new X_n-1
    cur:intSequence' (p1, cur) m1 m2 a
    -- calculate the current term in the sequence
    where cur = p1 * m1 + p2 * m2 + a

-- set previous terms correctly and prepend them to the sequence
intSequence :: (Integral a) => a -> a -> a -> a -> a -> [a]
intSequence x0 x1 m1 m2 a = x0:x1:intSequence' (x0, x1) m1 m2 a

如何创建一个函数来生成整数序列的无限列表，该列表使用两个初始数字 X_0 和 X_1 递归定义

How to create a function that generates an infinite list of an integer-sequence that is defined recursively with two initial numbers X_0 and X_1

recursion

haskell

sequence