「Haskell初心者」がFibonacci数の計算を書いてみた
code:Fib.hs
{-# LANGUAGE NPlusKPatterns #-} {-# LANGUAGE BangPatterns #-} module Fib where
import Numeric.Natural
Fibonacci数の定義
$ 0 \leq nのとき
$ F_{0} = 0
$ F_{1}=1
$ F_{n+2} = F_{n+1} + F_{n}
Haskellでこのフィボナッチ数を計算するコードを書くことにしましょう．
code:Fib.hs
fib :: Natural -> Natural
fib 0 = 0
fib 1 = 1
fib (n+2) = fib (n+1) + fib n
このコードはFibonacci数の定義そのままです．嗚呼なんて美しいんでしょう．これは「初心」なんです．
Fibonacci数の定義はFibonacci数の計算プログラムの仕様になります．このコードの驚くべきところは，プログラムの仕様記述が，そのまま実行可能な実装になっていることです．これは少くとも「正しい」プログラムです．
Fibonacci関数の計算量
プログラムが「正しい」ことはすべてに優先されます．しかし，正しいだけでは「使える」プログラムにはなれません．「使える」ためには使いたい場面で待てる範囲の時間内に正しい答えが得られなければなりません．
さて，上述のプログラムの時間計算量はどうでしょうか．
関数$ fがあるとき，$ T(f)(n)と書いて，最悪の場合で「大きさ」$ nの引数に対して$ fを評価するのに必要なステップ数を漸近的に見積ったものを表すとすると
$ T(\mathit{fib})(0) = O(1)
$ T(\mathit{fib})(1) = O(1)
$ T(\mathit{fib})(n+2) = T(\mathit{fib})(n+1) + T(\mathit{fib})(n) + O(1)
結局$ T(\mathit{fib})(n) = \Theta(\mathit{fib}\;n)なので，$ \mathit{fib}を計算するのにかかる時間は結果の大きさに比例します．$ \phiを黄金比$ \frac{1 + \sqrt{5}}{2}だとすると$ \mathit{fib}\;n = \Theta(\phi^{n})なので，計算時間は$ nの指数オーダーということになります．
タプリング
指数オーダーの計算量というのは絶望的です．これを改善する方法はあるでしょうか．
fibの定義の3行目のは2つの項fib (n+1)とfib nの足し算になっています．左側の項fib (n+1)を定義にしたがって1ステップ展開すると，fib n + fib (n-1)になります．これは，fib (n+2)を計算するとき2つの項fib (n+1)とfib nを独立に計算すると，fib nという項の計算を2度行うことになります．ここが改善できるポイントですね．
$ F_{n+1}と$ F_{n}を同時に計算する関数$ \mathit{fib}_2を考えてみましょう．仕様としては，
$ \mathit{fib}_2(n) = (\mathit{fib}(n+1), \mathit{fib}(n))
です．このfib2の再帰的定義を構成してみましょう．「再帰のこころ」は，「一歩手前までできたとして，最後の一歩を考える」です．fib2 (n+1)の一歩手前はfib2 nですね．仕様上は，fib2 (n+1) = (fib (n+2), fib (n+1))なので，右辺の2つ組の第一要素を一段階展開するとfib2 (n+1) = (fib (n+1) + fib n, fib n)となります．したがって，
(a, b) = fib2 nとおくと，fib2 (n+1) = (a + b, a)となります．
code:Fib.hs
fib2 :: Natural -> (Natural, Natural)
fib2 0 = (1, 0)
fib2 (n+1) = (a + b, a)
where
(!a, b) = fib2 n
fib' :: Natural -> Natural
fib' = snd . fib2
このプログラムの時間計算量は線形であるのは明らかです．また，fib2を利用したfib'は導出過程から，fibと同じ仕様を満すことも明らかです．
対数時間アルゴリズムの導出
Fibonacci数には以下のような性質があります．
$ 1 \leq m, 0 \leq nについて
$ F_{m + n} = F_{m}F_{n+1} + F_{m-1}F_{n}
この性質は「Fibonacci数の加法定理」と呼ばれることがあります．この定理そのものはFibonacci数の定義と自然数$ n上の帰納法により簡単に証明できます．ここで，$ mを$ nで置き換えると，
$ F_{2n} = F_{n}F_{n+1} + F_{n-1}F_{n}
Fibonacci数の定義より，$ F_{n-1} = F_{n+1} - F_{n}なので
$ F_{2n} = 2F_{n+1}F_{n} - F_{n}^{2} (1)
また，加法定理の$ mを$ n+1で置き換えると，
$ F_{2n+1} = F_{n+1}^2 + F_{n}^2 (2)
性質(1)，(2)を用いて，$ \mathit{fib}_2の仕様を満たす関数fib2'は以下のように再帰定義できます．
code:Fib.hs
fib2' :: Natural -> (Natural, Natural)
fib2' 0 = (1, 0)
fib2' n'@(n+1)
| even n' = (p * p + q * q, 2 * p * q - q * q)
| otherwise = (a + b, a)
where
k = n' div 2
(!p, q) = fib2' k
(!a, b) = fib2' n
fib'' :: Natural -> Natural
fib'' = snd . fib2'
これで，いくつか(加減乗除演算の計算量が定数オーダーなど)の前提のもとで時間計算量が対数のプログラムができました．
ここまでの過程で重要なのは，最終的に導出した高速なプログラムは，仕様を満していることが確証されているということです．すなわち，「正しい」プログラムであることが保証できるということです．
Haskellの美しさは，仕様記述と実装記述とのギャップが比較的小さいことではないでしょうか．仕様上の論証をプログラムコードに移すことの困難が多少軽減されるところが魅力でしょう．そういうところにうっとりします．