haskell - Haskell 中的惰性加泰罗尼亚数字

Question

我如何才能有效地生成一个无限的加泰罗尼亚数字列表？我现在的工作相当快，但在我看来应该有更好的方法。

c 1 = 1
c n = sum (zipWith (*) xs (reverse xs)) : xs
    where xs = c (n-1)

catalan = map (head . c) [1..]

我尝试使用 fix相反，但 lambda 还不够懒惰，无法终止计算:

catalan = fix (\xs -> xs ++ [zipWith (*) xs (reverse xs)])

我意识到(++)不理想

这种更好的方法存在吗？可以使该功能足够懒惰吗？我知道第 n 个有一个明确的公式，但我宁愿避免它。

Answer 1

Catalan numbers [wiki]可以归纳定义为:

C0 = 1 且 Cn+1=(4n+2)×Cn/(n+2)。

所以我们可以将其实现为:

catalan :: Integral i => [i]
catalan = xs
    where xs = 1 : zipWith f [0..] xs
          f n cn = div ((4*n+2) * cn) (n+2)

例如:

Prelude> take 10 catalan
[1,1,2,5,14,42,132,429,1430,4862]