HaskellでFibonacci数列を計算する

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

## Version 1: 基本的な再帰

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

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

```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. 負の数を引数に取った場合にエラーが発生する

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


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


## Version 2: ガード構文の導入

```haskell
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`文に相当します

```typescript
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`を使って、負の数に対するエラー処理を追加しています

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


## Version 3: メモ化の導入

```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."

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

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

`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];
  };
}
```

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

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

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

### `where`句

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

Haskellの例：

```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の例：

```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);
}
```
:::note info
まとめると、`where`句は関数内で使う`プライベート`な関数や変数を定義するといことになる
:::

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

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

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の例：

```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）の導入
:::note info
コメントでもっと効率化が可能であることを教えていただいたので、取り入れてみました！
@yukikurage_2019 さんありがとうございます！！
:::

```hs: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: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の問題点
```haskell: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. 処理を高速化したいが、`!!`を利用することで、結局処理に時間がかかってしまう
1. memoを利用することで、重複した計算は回避することができている
1. `fibonacci (n - 1) + fibonacci (n - 2)`で`+`を挟むという計算処理を挟んでいることで`末尾再起最適化`が行われていない

**今回発生しているこれらの問題を解決するには、**
1. `!!`を利用しない
1. `末尾再起最適化`を行うことになる

@yukikurage_2019 さんの式では、
```hs
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の文法はとっつきづらいので、もう少し簡単なプログラムを作成していこうと思う。