haskell - 函数式语言中的加泰罗尼亚数字

Question

加泰罗尼亚数满足递归

当然，加泰罗尼亚数具有涉及二项式系数的封闭形式表达式。我们也可以单独用 C_{n-1} 来表示 C_n。我想知道的是如何在 SML 或 Haskell 等函数式语言中实现这种卷积。

Answer 1

当然，您可以在 haskell 中实现加泰罗尼亚数字（我认为 ml-family 也足够强大）！

但我想这不是你要找的答案。所以我希望你熟悉基本的 haskell 语法，将加泰罗尼亚数字视为函数，catalan :: Int -> Int任何自然数系列都是这样的函数（对于小型索引来说很好）。Integer但是随着加泰罗尼亚数字增长得非常快，我将选择s（= 任意大整数）的类型作为我们函数的共域。

catalan :: Int -> Integer
catalan 0 = 1
catalan n = sum [ ?catalan magic? | i <- [1..n]]

我知道我几乎解决了这个问题，但仍然有加泰罗尼亚魔法;-) 你必须自己做。

但在我停止一些警告之前

• 这个计算加泰罗尼亚数字的版本远非最佳或有效
• 不处理负输入值的情况。