『関数プログラミング入門』3.3 畳み込み関数 の続きをやろう。
数の定義から出発して、 ＋, ×, ↑ の計算を定義してきた。
ここで、再帰定義のお勉強の王道である、階乗とフィボナッチ数を求めてみよう。
とりあえず、何も考えず、本を写経してみた。
data Nat = Zero | Succ Nat
deriving (Eq,Ord,Show)
foldn :: (a -> a) -> a -> Nat -> a
foldn h c Zero = c
foldn h c (Succ n) = h (foldn h c n)
m ＋ n = foldn Succ m n
m × n = foldn (＋ m) Zero n
m ↑ n = foldn (× m) (Succ Zero) n
fact :: Nat -> Nat
fact = snd . foldn f (Zero, Succ Zero)
where f (m,n) = (Succ m, Succ m × n )
fib :: Nat -> Nat
fib = fst . foldn g (Zero, Succ Zero)
where g (m,n) = (n,m ＋ n)ちょっと実行して、動作確認してみよう。
*Main> fact Zero
Succ Zero
*Main> fact (Succ Zero)
Succ Zero
*Main> fact (Succ (Succ Zero))
Succ (Succ Zero)
*Main> fact (Succ (Succ (Succ Zero)))
Succ (Succ (Succ (Succ (Succ (Succ Zero)))))
*Main> fact (Succ (Succ (Succ (Succ Zero))))
Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero)))))))))))))))))))))))
*Main> 0! から 4! までやってみた。 4! は 24 であるから、 Succ が24個あるはずだ。
もっと大きな数で確認したいが、結果が正しいのかどうか、とても判定できない。
ということで、練習問題3.1.2 自然数を整数に変換する関数
convert :: Nat -> Integerを定義してみた。
-- 練習問題 3.1.2
convert :: Nat -> Integer
convert Zero = 0
convert (Succ a) = (convert a) + 1これを加えると、結果が長くなっても普通の数字に直してくれるのだ。
*Main> convert (fact (Succ (Succ (Succ (Succ Zero)))))
24
*Main> convert (fact (Succ (Succ (Succ (Succ (Succ Zero))))))
120
*Main> convert (fact (Succ (Succ (Succ (Succ (Succ (Succ Zero)))))))
720
*Main> convert (fact (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero))))))))
5040確かに動いているようだが、自然数を (Succ (Succ (.... (Succ Zero)...) と書くのはとても面倒だ。
ここは、横着なことを考えよう。
普通の数字を与えて、自然数に直してしまおう。
つまり、 convert の逆関数を作ってみた。
-- その逆関数
expand :: Integer -> Nat
expand 0 = Zero
expand (n + 1) = Succ (expand n)名前は、展開するという感じの関数なので、 expand と名付けた。
とりあえず、動作確認だ。
*Main> expand 0
Zero
*Main> expand 1
Succ Zero
*Main> expand 2
Succ (Succ Zero)
*Main> expand 5
Succ (Succ (Succ (Succ (Succ Zero))))正しく動いているようなので、 fact の引数をこれで指定し直した。
*Main> convert (fact (expand 3))
6
*Main> convert (fact (expand 7))
5040
*Main> (convert . fact . expand) 7
5040
*Main>最後は、関数合成にしてみた。
フィボナッチ数も確認してみよう。
*Main> (convert . fib . expand) 0
0
*Main> (convert . fib . expand) 1
1
*Main> (convert . fib . expand) 2
1
*Main> (convert . fib . expand) 3
2
*Main> (convert . fib . expand) 4
3
*Main> (convert . fib . expand) 5
5
*Main> (convert . fib . expand) 6
8
*Main> (convert . fib . expand) 7
13
*Main> フィボナッチ数も大丈夫なようだ。
ということで、うまくいったので終わり。
としたいところだが、ちょっとやってみたい実験がある。
それは、どのくらいまで、耐えられるかだ。
*Main> (convert . fact . expand) 7
5040
*Main> (convert . fact . expand) 8
40320
*Main> (convert . fact . expand) 9
362880
*Main> (convert . fact . expand) 10
3628800
*Main> (convert . fact . expand) 11
C-c C-c C-c C-c C-c C-c9で1秒、10で10秒ほどだから、11なら数分で戻ってくるかと思ったが、ダメだった。
1.4Gくらいメモリを食いつぶして、なかなか止まらなかったのだ。
C-cでは止められなくて、直接GHCiのプロセスを殺した。
ということで、自然数の定義に基づいて階乗、フィボナッチ数を計算するのは危険なようだ。
＃人気の記事
＃タグ
