-
Notifications
You must be signed in to change notification settings - Fork 0
/
CatalanNumberFactorial.hs
53 lines (48 loc) · 1.54 KB
/
CatalanNumberFactorial.hs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
module CatalanNumberFactorial where
-- | Factorial function
--
-- >>> factorial 0
-- 1
-- >>> factorial 3
-- 6
factorial :: Integer -> Integer
factorial num = case num of
0 -> 1
1 -> 1
_
| num < 0 -> error "factorial: input must be a non-negative integer"
| otherwise -> num * factorial (num - 1)
-- | Catalan number by explicit sequence definition with factorial
--
-- >>> catalanNumberFactorial 0
-- 1
-- >>> catalanNumberFactorial 5
-- 42
catalanNumberFactorial :: Integer -> Integer
catalanNumberFactorial term = x `div` y
where
x = factorial (2 * term)
y = factorial (term + 1) * factorial term
-- | Catalan number by explicit sequence definition with product
--
-- >>> catalanNumberProduct 0
-- 1
-- >>> catalanNumberProduct 5
-- 42
catalanNumberProduct :: Integer -> Integer
catalanNumberProduct term
| term < 0 = error "catalanNumberProduct: input must be a non-negative integer"
| term == 0 = 1
| term == 1 = 1
| otherwise = catalanNumberProductAcc term 2
where
catalanNumberProductAcc :: Integer -> Integer -> Integer
catalanNumberProductAcc num acc = catalanNumberProductNum num acc `div` catalanNumberProductDem num acc
catalanNumberProductNum :: Integer -> Integer -> Integer
catalanNumberProductNum num acc
| acc == num = (num + acc)
| otherwise = (num + acc) * catalanNumberProductNum num (acc + 1)
catalanNumberProductDem :: Integer -> Integer -> Integer
catalanNumberProductDem num acc
| acc == num = acc
| otherwise = acc * catalanNumberProductDem num (acc + 1)