3

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

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 th有一个明确的公式，但我宁愿避免它。

4

3 回答 3

9

加泰罗尼亚数字[wiki]可以归纳定义为：

C 0 = 1和C n+1 =(4n+2)×C n /(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]
于 2019-08-30T21:21:29.400 回答
3

我猜你正在寻找一个使用基本递归关系之一的所有加泰罗尼亚数字的惰性、无限、自引用列表。毕竟，这与斐波那契数字有关。但是，如果您想回答您的特定问题，指定您所指的重复关系会有所帮助。我猜这就是你的意思：

cat :: Integer -> Integer
cat 1 = 1
cat n = sum [ cat i * cat (n - i) | i <- [1 .. n - 1] ]

如果是这样，则转换为自引用形式如下所示：

import Data.List (inits)

cats :: [Integer]
cats = 1 : [ sum (zipWith (*) pre (reverse pre)) | pre <- tail (inits cats) ]

这比斐波那契的例子要复杂得多，因为重复是指列表中所有以前的条目，而不仅仅是最近的固定小数。使用initsfromData.List是在每个位置获取前缀的最简单方法。我在tail那里使用它是因为它的第一个结果是空列表，这在这里没有帮助。其余的是对递归关系的直接重写，我没有太多要说的。除了...

它的表现会很糟糕。我的意思是，它比我的cat函数的指数递归调用要好，但是有很多列表操作正在进行，即分配然后丢弃大量内存单元。这种递归关系不太适合列表数据类型的递归结构。您可以探索很多方法来提高效率，但最终它们都会变得非常糟糕。对于这种特殊情况，如果您想要性能，则采用封闭形式的解决方案是可行的方法。

于 2019-08-31T00:32:10.890 回答
3

显然，你想要的是

> cats = 1 : unfoldr (\ fx -> let x = sum $ zipWith (*) fx cats in Just (x, x:fx)) [1]

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

这避免了前缀的重复反转（如在链接的答案中），通过将状态展开为反转的前缀，同时进入状态并产生下一个元素。

我们不必维护非反转前缀，因为使用加泰罗尼亚语列表本身压缩反转前缀会处理加泰罗尼亚语前缀的长度。

你确实说过你想避免直接公式。

于 2019-08-31T15:15:19.070 回答