如何创建一个遵循特定序列的无限整数列表

Question

假设我有x0=1，x1=2和x2=4，我说xN=x_n-1+x_n-2+x_n-3。下一个数字是前三个数字的总和。如果我知道怎么做的话，我会在这里放一些代码，但我不知道。我想从一个序列中创建一个无限的数字列表，其中下一个数字是前三个数字的总和。

Answer 1

在Haskell中实现数学内容的第一步通常应该是尽可能地把它写出来：

x 0 = 1
x 1 = 2
x 2 = 4
x n = x (n-1) + x (n-2) + x (n-3)

现在，它定义的不是一个列表/序列，而是一个函数。

x :: Int -> Int

在数学中，这种区别往往是模糊的——无限列表集同构于自然数上的函数集，因此你可以将上面的转换为列表：

[ x n | n <- [0..] ]

或短

x <$> [0..]

然而，这种方法实际上效率非常低，因为对x的每次调用(带有非微小参数(都会引发三次递归调用，使整个过程具有指数级的复杂性。一种可以避免这种情况的方法是显式构建列表，将最后三个值作为状态变量携带：

xs :: [Int]
xs = go 4 2 1
where go xp xpp xppp = xppp : go (xp+xpp+xppp) xp xpp