はじめに
今月からHaskellというプログラミング言語を趣味で使い始めました。
その中で、フィボナッチ数列の実装をやってみたところ、Haskellという言語の素晴らしさを肌で感じることができたので、新鮮なうちにこの感動を共有したいと思い、筆を取りました。
Haskellを知らない方に、Haskellの面白さが伝わると嬉しいです!
フィボナッチ数列とは、各項は直前2つの項の話で求められる数の数列である
フィボナッチ数列は、次のような漸化式で定義される数列です。
$$
\begin{cases}
a_0 = 0,
a_1 = 1,
a_n = a_{n-1} + a_{n-2}, & n \ge 2
\end{cases}
$$
つまり、各項は直前2つの項の和になっています。
前提: フィボナッチ数列を再帰で無邪気に実装してみると計算コストの問題が発生する
フィボナッチ数列の一般項は知られていますが、これを使わずに
各項は直前2つの項の和
という性質を使って実装してみます。
参考: フィボナッチ数列の一般項
まず黄金比 $\phi$ を
$$
\phi = \frac{1 + \sqrt{5}}{2}, \quad \hat{\phi} = \frac{1 - \sqrt{5}}{2}
$$
と定義すると、n番目のフィボナッチ数 $a_n$ は
$$
a_n = \frac{\phi^n - \hat{\phi}^n}{\sqrt{5}}
$$
で与えられる。
-- フィボナッチ数列の計算（再帰定義）
-- NOTE: 計算量的に良くないが再帰の例として作成
fibonacciNumber :: Int -> Int
fibonacciNumber n
| n == 0 = 0
| n == 1 = 1
| otherwise = fibonacciNumber (n - 1) + fibonacciNumber (n - 2)
main :: IO ()
main = do
-- 0から35までのフィボナッチ数列を生成
let range = [0 .. 35]
let fibonacciNumberList = map fibonacciNumber range
print fibonacciNumberList
手元のコンピュータで実行してみるとn = 35まで生成するのに20秒ほどかかりました。
最初の方は高速なのですが、後半になるにつれフィボナッチ数の生成がどんどん遅くなります。
これはfibonacciNumber nを求めるのにfibonacciNumber n-1とfibonacciNumber n-2をもとめる必要があり、fibonacciNumber n-1を求めるためには...と指数関数的に計算量が増えてしまいます。
計算量はおおよそ、$$O(2^n)$$になります。
time runghc recursive_definision.hs
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465]
runghc recursive_definision.hs 20.58s user 0.05s system 100% cpu 20.595 total
解決策: 計算量が増えないよう、一度求めた値をキャッシュしておく
一度求めたフィボナッチ数をキャッシュしておくことで、計算量が指数関数的に増えなくなりました。万歳!!
import Data.Array
-- nまでのフィボナッチ数列を計算して配列にキャッシュ
fibonacciArray :: Int -> Array Int Int
fibonacciArray n = arr
where
arr = listArray (0, n) [fib i | i <- [0..n]]
fib 0 = 0
fib 1 = 1
fib i = arr ! (i - 1) + arr ! (i - 2) -- 計算済みを参照
main :: IO ()
main = do
let n = 35
let fibs = fibonacciArray n
print [fibs ! i | i <- [0..n]]
計算量は$$O(n)$$になります。
# 速度の改善もされた
time runghc fibonacci.hs
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465]
runghc fibonacci.hs 0.08s user 0.04s system 92% cpu 0.123 total
Haskellのよりエレガントでかっこいい実装を紹介!
計算量の問題は解決しましたが、Haskellを使うとよりエレガントにフィボナッチ数列を表現できます。
-- 無限リストを使ったフィボナッチ
fibs :: [Int]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
main :: IO ()
main = do
print $ take 36 fibs
Haskellはじめましての方は何が書いてあるかぱっとわからないかも知れません。
(自分も数時間前は何書いてあるかわかりませんでした)
順を追って説明します。
Haskellの遅延評価により、無限リストを作成できる
Haskellは遅延評価(Non-strict semantics)という機能があります。
This is another one of Haskell's features - it means that nothing is evaluated until it has to be evaluated.
This demand-driven approach, free of language-wide ordering, means that you could, for example, define an infinite list of primes without ending up in an infinite recursion.
Only the elements of this list that are actually used will be computed.1
遅延評価とは、式の値が実際に必要になるまで計算を行わない機能です。
普通の言語では、無限の要素を持つリストを作成しようとすると無限のメモリが必要になります。
しかしHaskellでは、リストの要素が使用されるタイミングで初めて計算されるため、無限リストを定義することが可能なのです。
この式でやっていることの説明
-- 無限リストを使ったフィボナッチ(コメントを付けて再掲)
fibs :: [Int]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
main :: IO ()
main = do
print $ take 36 fibs -- 無限リストからn=0〜36のみ切り出している
問題となるのはfibs = 0 : 1 : zipWith (+) fibs (tail fibs)の部分かと思うのでこの部分を詳しく書いていきます。
-
0 : 1の部分はn=0、n=1の時のフィボナッチ数の値を設定しているだけ -
zipWithを使ってフィボナッチ数列fibsとfibsの先頭を1つ落としたフィボナッチ数列を結合している# 具体例をいれるとこんな感じ ghci> zipWith (+) [0,1,1,2,3] [1,1,2,3] [1,2,3,5] ghci> 0 : 1 : zipWith (+) [0,1,1,2,3] [1,1,2,3] [0,1,1,2,3,5]
数式風に書くと以下のような感じです。
fibs$$[a_0, a_1, a_2, a_3, \dots]$$
tail fibs$$[a_1, a_2, a_3, \dots]$$
zipWith (+) fibs (tail fibs)$$[a_0, a_1, a_2, \dots],\ [a_1, a_2, a_3, \dots])
= [a_0+a_1,\ a_1+a_2,\ a_2+a_3,\dots]
$$
したがって、再帰的に
$$
a_n = a_{n-1} + a_{n-2}
$$
という関係をHaskellが簡潔に表していることがわかります。
Haskellの遅延評価により、自己参照的な無限リストが作成できることでよりエレガントな記述が可能になります。