HaskellでFibonacci数列を計算する

概要

Haskellを学習する過程で、Fibonacci数列を計算する関数を実装してみました。この記事では、実装の進化の過程を紹介し、各バージョンの特徴と問題点を説明します。また、Haskell独自の記法にも触れ、TypeScriptとの対応関係を示します。

Version 1: 基本的な再帰

fibonacci :: Int -> Int
fibonacci 0 = 0
fibonacci 1 = 1
fibonacci n = fibonacci (n - 1) + fibonacci (n - 2)

Version 1は、Fibonacciの基本的な定義に基づいた素直な実装です。TypeScriptで同様の実装を書くと、以下のようになります。

function fibonacci(n: number): number {
  if (n === 0) return 0;
  if (n === 1) return 1;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

この実装の問題点は以下の通りです

1. 実行速度が遅い：スタックを再利用せずに、毎回新たに作成してしまっている(訳:リソースの無駄遣い)
2. 負の数を引数に取った場合にエラーが発生する

1の説明が初学者の理解では難易度が高かったためClaudeさんの説明も併せて載せておきます
今の自分の理解に近いですが、何かしらの異常がある場合はご連絡下さい

1. 再帰呼び出しによるスタックフレームの蓄積: 現在の実装では、再帰呼び出しのたびに新しいスタックフレームが作成され、スタックが蓄積されていきます。これによりメモリ消費が増大し、実行速度が低下する可能性があります
2. スタックの再利用の欠如: 現在の実装では、スタックの再利用が行われていません。新しいスタックフレームの割り当てと解放に時間がかかるため、実行速度が遅くなる原因となります
3. 末尾再帰最適化の未適用: Haskellコンパイラは末尾再帰を検出し、スタックを再利用するように最適化することができます。しかし、現在の実装は末尾再帰の形になっていないため、最適化の恩恵を受けることができません。

素直な実装ですが、再帰で回す分処理が重くなります。簡単に言うと、n = 40で渡すと数分結果が返ってこないレベルになります

Version 2: ガード構文の導入

fibonacci :: Int -> Int
fibonacci n
  | n == 0 = 0
  | n == 1 = 1
  | n > 1 = fibonacci (n - 1) + fibonacci (n - 2)
  | otherwise = error "fibonacci: invalid input"

Version 2では、ガード構文を使って条件分岐を表現しています。これは、TypeScriptのif文に相当します

function fibonacci(n: number): number {
  if (n === 0) return 0;
  if (n === 1) return 1;
  if (n > 1) return fibonacci(n - 1) + fibonacci(n - 2);
  throw new Error("fibonacci: invalid input");
}

ガード構文を使うことで、条件に合致する場合のみ処理を行うことができます。また、otherwiseを使って、負の数に対するエラー処理を追加しています

ただし、実行速度の問題は解決されていません

Version 3: メモ化の導入

fibonacci :: Int -> Integer
fibonacci = memo fib
  where
    fib 0 = 0
    fib 1 = 1
    fib n
      | n > 1 = fibonacci (n - 1) + fibonacci (n - 2)
      | otherwise = error "fibonacci: invalid input."

memo :: (Int -> a) -> Int -> a
memo f = (map f [0..] !!)

Version 3では、メモ化を導入することで実行速度の問題を解決しています。メモ化とは、一度計算した結果を保存しておき、同じ計算を繰り返さないようにする手法らしい

memo関数は、与えられた関数をメモ化します。これは、TypeScriptの高階関数とクロージャを使って以下のように表現できます。by Claude3

function memo<T>(f: (n: number) => T): (n: number) => T {
  const cache: T[] = [];
  return (n: number): T => {
    if (cache[n] === undefined) {
      cache[n] = f(n);
    }
    return cache[n];
  };
}

memo関数は、与えられた関数fをラップし、キャッシュを使って結果を保存します。同じ引数で呼び出された場合は、キャッシュから結果を返します。

Haskell独自の記法とTypeScriptとの対応

Version 3では、Haskellならではの記法を使用している。これらの記法は、関数型プログラミングの考え方を反映したものである。それぞれの記法についてTypeScriptと比較しながら見ることで理解を深めたい

where句

where句は、関数の本体で使用する関数や変数を定義するために使用します。これは、関数内で局所的に使用する関数や変数を定義するための構文です。

Haskellの例：

fibonacci :: Int -> Integer
fibonacci = memo fib
  where
    fib 0 = 0
    fib 1 = 1
    fib n
      | n > 1 = fibonacci (n - 1) + fibonacci (n - 2)
      | otherwise = error "fibonacci: invalid input."

TypeScriptで、関数内で直接関数を定義することに対応する

TypeScriptの例：

function fibonacci(n: number): number {
  function fib(n: number): number {
    if (n === 0) return 0;
    if (n === 1) return 1;
    if (n > 1) return fibonacci(n - 1) + fibonacci(n - 2);
    throw new Error("fibonacci: invalid input.");
  }

  return memo(fib)(n);
}

まとめると、where句は関数内で使うプライベートな関数や変数を定義するといことになる

無限リストと演算子セクション

Haskellでは、無限リストと演算子セクションを組み合わせることで、メモ化を簡潔に表現できます。

Haskellの例：

memo :: (Int -> a) -> Int -> a
memo f = (map f [0..] !!)

• [0..]は、0から始まる無限リストを表します。TypeScriptには無限リストの概念がないため、直接的な対応はない
  • [0, 1, 2, 3, ...] のような無限に続く整数のリストを一発で作成可能らしい
• map関数は、リストの各要素に対して指定された関数を適用し、新しいリストを生成する
• map f [0..] は、無限リストの各要素に関数fを適用する。つまり、[f 0, f 1, f 2, f 3, ...] のような新しい無限リストが生成される
• 関数fは、memo関数の引数として与えられた関数である。この関数は、整数を受け取り、何らかの値を返す

TypeScriptでは、メモ化を以下のように実装できる。by Claude3

TypeScriptの例：

function memo<T>(f: (n: number) => T): (n: number) => T {
  const cache: T[] = [];
  return (n: number): T => {
    if (cache[n] === undefined) {
      cache[n] = f(n);
    }
    return cache[n];
  };
}

TypeScriptでは、配列とクロージャを使ってメモ化を実現している。cache配列に計算結果を保存し、次回以降の呼び出しではキャッシュから結果を返している。

これらの記法は、Haskellの関数型プログラミングの特徴を活かしたもので、TypeScriptでも同じ概念を異なる方法で表現することができる

Version 4: 末尾再帰最適化（Tail Call Optimization）の導入

コメントでもっと効率化が可能であることを教えていただいたので、取り入れてみました！
@yukikurage_2019 さんありがとうございます！！

hs

fibonacci :: Int -> Maybe Integer
fibonacci n
    | n < 0     = Nothing
    | otherwise = Just (go n 0 1)
    where
        go 0 prePre pre = prePre
        go 1 prePre pre = pre
        go n prePre pre = go (n - 1) pre (prePre + pre)

ts

function fibonacci(n: number): number | null {
  if (n < 0) return null;

  // Haskellでは暗黙的にカリー化されるが、今回は通常の記法を用いる
  function go(n: number, prePre: number, pre: number): number {
    if (n === 0) return prePre;
    if (n === 1) return pre;
    return go(n - 1, pre, prePre + pre);
  }
  return go(n, 0, 1);
}

// 使用例
console.log(fibonacci(0)); // 0
console.log(fibonacci(1)); // 1
console.log(fibonacci(2)); // 1
console.log(fibonacci(10)); // 55
console.log(fibonacci(-5)); // null

よりよいものとしてはこのようになるが、速度・スタックオーバーフロー対策に関していろいろと手が打たれているため順次見ていこうと思う

Version 3の問題点

version:3

fibonacci :: Int -> Integer
fibonacci = memo fib
  where
    fib 0 = 0
    fib 1 = 1
    fib n
      | n > 1 = fibonacci (n - 1) + fibonacci (n - 2)
      | otherwise = error "fibonacci: invalid input."

memo :: (Int -> a) -> Int -> a
memo f = (map f [0..] !!)

@yukikurage_2019 さんからの指摘にもあったが、

List の !! は O(n) なので、Version 3 も O(n^2) かかります

簡単に言うと、fib関数の呼び出し*リスト要素の取り出しがn回かかるため、処理回数が増えると指数関数的に処理時間が増えていくということである

現状を再考する

1. 処理を高速化したいが、!!を利用することで、結局処理に時間がかかってしまう
2. memoを利用することで、重複した計算は回避することができている
3. fibonacci (n - 1) + fibonacci (n - 2)で+を挟むという計算処理を挟んでいることで末尾再起最適化が行われていない

今回発生しているこれらの問題を解決するには、

1. !!を利用しない
2. 末尾再起最適化を行うことになる

@yukikurage_2019 さんの式では、

go n prePre pre = go (n - 1) pre (prePre + pre)

と、純粋にgo関数を呼び出すことを行っているため、末尾再起最適化を正しく行うことができている

Version 4の式では先ほど挙げた問題を行っていないため、速度・スタックオーバーフローのどちらに対しても対処しているといえる

それぞれの実行速度

n=45
※　Version 1-2は実行速度に関して変更はないため2に関しては計測しない

criterionを利用して測定

回数	Verson 1	Version 2	Version 3	Version 4
1	6.274 s	-	43.30 ns	8.532 ns
2	7.842 s	-	42.16 ns	8.316 ns
3	5.900 s	-	42.49 ns	8.322 ns

このようにして実際に実行速度を比較すると大幅に短縮できていることを確認できる

まとめ

Fibonacci数列の計算を通して、Haskellの基本的な文法やベストプラクティスを学ぶことができたが、理解が及ばない部位分もまだ多い。しかし、再帰、ガード構文、メモ化などの概念は、他の言語でも役立つと思う。

特にメモ化の概念は、キャッシュの概念に通じるため今後ほかの分野にもつぶしが効くと感じた。

Hakellの文法はとっつきづらいので、もう少し簡単なプログラムを作成していこうと思う。