我一直在处理涉及基于列表中先前元素生成列表的问题（例如五边形数字）。我似乎找不到我想要的表单的内置函数。本质上，我正在寻找以下形式的功能：
([a] -> a) -> [a] -> [a]
([a] -> a)到目前为止，Where获取列表并产生应该在列表中的下一个元素，a或者[a]是初始列表。我尝试使用 iterate 来实现这一点，但这会产生一个列表列表，每个连续的列表都有一个元素（所以要获得第 3000 个元素，我必须(list !! 3000) !! 3000)代替list !! 3000.
如果递归取决于恒定数量的先前项，那么您可以使用标准 corecursion 定义系列，就像斐波那契数列一样：
-- fibs(0) = 1
-- fibs(1) = 1
-- fibs(n+2) = fibs(n) + fibs(n+1)
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
-- foos(0) = -1
-- foos(1) = 0
-- foos(2) = 1
-- foos(n+3) = foos(n) - 2*foos(n+1) + foos(n+2)
foos = -1 : 0 : 1 : zipWith (+) foos
(zipWith (+)
(map (negate 2 *) (tail foos))
(tail $ tail foos))
虽然你可以引入一些自定义函数来使语法更好一点
(#) = flip drop
infixl 7 #
zipMinus = zipWith (-)
zipPlus = zipWith (+)
-- foos(1) = 0
-- foos(2) = 1
-- foos(n+3) = foos(n) - 2*foos(n+1) + foos(n+2)
foos = -1 : 0 : 1 : ( ( foos # 0 `zipMinus` ((2*) <$> foos # 1) )
`zipPlus` foos # 2 )
但是，如果术语的数量不同，那么您将需要一种不同的方法。
例如，考虑 p(n)，即给定正整数可以表示为正整数之和的方式数。
p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + p(n-12) + p(n-15) - ...
我们可以更简单地将其定义为
p(n) = ∑ k ∈ [1,n) q(k) p(nk)
在哪里
-- q( i ) | i == (3k^2+5k)/2 = (-1) ^ k
-- | i == (3k^2+7k+2)/2 = (-1) ^ k
-- | otherwise = 0
q = go id 1
where go zs c = zs . zs . (c:) . zs . (c:) $ go ((0:) . zs) (negate c)
ghci> take 15 $ zip [1..] q
[(1,1),(2,1),(3,0),(4,0),(5,-1),(6,0),(7,-1),(8,0),(9,0),(10,0),(11,0),(12,1),
(13,0),(14,0),(15,1)]
然后我们可以使用iterate来定义p：
p = map head $ iterate next [1]
where next xs = sum (zipWith (*) q xs) : xs
请注意如何iterate next创建一系列反向前缀 ofp以便q于计算 的下一个元素p。然后，我们将每个反向前缀的头元素用于查找p。
ghci> next [1]
[1,1]
ghci> next it
[2,1,1]
ghci> next it
[3,2,1,1]
ghci> next it
[5,3,2,1,1]
ghci> next it
[7,5,3,2,1,1]
ghci> next it
[11,7,5,3,2,1,1]
ghci> next it
[15,11,7,5,3,2,1,1]
ghci> next it
[22,15,11,7,5,3,2,1,1]
将其抽象为模式，我们可以获得您正在寻找的功能：
construct :: ([a] -> a) -> [a] -> [a]
construct f = map head . iterate (\as -> f as : as)
p = construct (sum . zipWith (*) q) [1]
或者，如果我们定义一个辅助函数来生成列表的反转前缀，我们可以在标准的核心递归样式中执行此操作：
rInits :: [a] -> [[a]]
rInits = scanl (flip (:)) []
p = 1 : map (sum . zipWith (*) q) (tail $ rInits p)