※現在、ブログ記事を移行中のため一部表示が崩れる場合がございます。
順次修正対応にあたっておりますので何卒ご了承いただけますよう、お願い致します。

階乗とフィボナッチの計算負荷は凄い!


2012年 11月 09日

Haskells.jpg

『関数プログラミング入門』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-c

9で1秒、10で10秒ほどだから、11なら数分で戻ってくるかと思ったが、ダメだった。
1.4Gくらいメモリを食いつぶして、なかなか止まらなかったのだ。
C-cでは止められなくて、直接GHCiのプロセスを殺した。

ということで、自然数の定義に基づいて階乗、フィボナッチ数を計算するのは危険なようだ。