Каталонские номера в функциональных языках

Question

Каталонских числа удовлетворяют рекуррентный

Конечно Каталонский номер имеет замкнутую форму выражения с участием биномиальных коэффициентов. Также мы можем выразить C_n только через C_ ​​{n-1}. Мне интересно, как можно реализовать такой сверток в функциональных языках, таких как 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]] 

Я знаю, что я почти решил проблему, но есть еще каталанская магия ;-) вам нужно делать самостоятельно.

Но прежде, чем я остановлюсь несколько предостережений

• этого вариант расчета каталонских чисел далеко от оптимального или эффективного
• случае отрицательных значений входных не заботятся.