Clojure でフィボナッチ数列を作ってみる

# はじめに

[Clojure](https://clojure.org/) というプログラミング言語をご存知でしょうか.
ものすご~くざっくり紹介するとJVM 上で動く関数型言語なのですが, このClojure という言語, C++やPython, Java や TypeScript といったメジャーな言語しか知らない人や, オブジェクト指向の考え方に慣れ切ってその世界しか知らない人が初めて触れると, **ビックリします**(多分). 私はびっくりしてひっくり返って頭を抱えました.

そんなClojure 初心者がひっくり返った**びっくり**を共有するのがこの記事の目的です.

ですので, この記事はClojure のエキスパートが書いたものではないことに注意して下さい.
深く理解していればもっとスマートな説明の仕方があるのに……とか記事の内容に未熟な点は多々あると思いますが, そういう趣旨なのだとご理解ください.

私の自己紹介をしておきますと,　私はClojure の**超ド初心者**です. 
Clojure歴はそろそろ1か月くらいというところ.
Clojureを学んでいる理由は, 転職先の会社がメインでClojureを使っているからです. 社内にはClojure激つよエンジニアの先輩方がわんさかいるので, 学ぶ環境としては最高だと思っています.

# Clojure でフィボナッチ数列を作ってみる

この記事ではフィボナッチ数列を出力する関数をClojure で書いてみる, ということをテーマにしたいと思います. 
理由は, 私が最初にClojureの奥深さを痛感して衝撃を受けたお題だからです.

まずはPython で素朴に書いてみましょう.
この記事ではフィボナッチ数列のインデックスを1から数えていこうと思います.
また, 1番目のフィボナッチ数を1とします. 

```Python3:bad_fibo.py
def bad_fibo(n):
    if n <= 2:
        return 1
    return bad_fibo(n-1) + bad_fibo(n-2)
```

```Python3
print(bad_fibo(1))
# > 1

print(bad_fibo(10))
# > 55

print(bad_fibo(10000))
# > RecursionError: maximum recursion depth exceeded in comparison
```

`fibo(n)` を呼び出すとn番目のフィボナッチ数を返す関数です.
n=10 ではきちんと計算できましたが, n=10000 にするとエラーになってしまいました.

同じコードをClojureで書いてみます.

```clojure:bad_fibo.clj
(defn bad-fibo [n]
  (if (<= n 2)
    1
    (+ (bad-fibo (- n 1)) (bad-fibo (- n 2)))))
```

```Clojure
(bad-fibo 10) ; => 55
(bad-fibo 10000) ; => 応答が返ってきませんでした...
```

こんな感じで, Python とかClojure とか関係なく, 何も考えずに再帰呼び出しで巨大なフィボナッチ数を計算しようとすると失敗します.
Clojureではこれをどう解決するのかという話をします.

:::note
Clojure のコードを見ること自体が初めての人はこの時点で驚くかもしれません.
Clojure では`1 + 1` を`(+ 1 1)`と書きます.
[前置記法(ポーランド記法)](https://ja.wikipedia.org/wiki/%E3%83%9D%E3%83%BC%E3%83%A9%E3%83%B3%E3%83%89%E8%A8%98%E6%B3%95)というらしいです.
:::

# Clojure で書くフィボナッチ数列の模範回答

いろいろと書く前にいきなりゴールを書いちゃいます.
[プログラミングClojure](https://www.ohmsha.co.jp/book/9784274069130/) という本にフィボナッチ数列の模範回答が載っています. こんな感じです.

```Clojure:good_fibo.clj
(defn good-fibo []
  (map first (iterate (fn [[a b]] [b (+ a b)]) [1N 1N])))
```

**なんじゃこりゃあ!?!?**
となりました. 私は.

まずif文がなくなっています.
それから, 自分と同じ名前の関数を呼び出して再帰させている気配がありません.
そもそもmap とかfirst とかiterate って何? みたいな.

初めて見た時は「自分じゃ一生かかってもこんなコード書けないよ!」と頭を抱えました. 
(でもClojure に慣れてくるとそんなに無茶なことではないのかもと感じ始めてもいます)

同じようにびっくりした人は, この先を読むと少し面白いかもしれないです.
「こんなの当たり前じゃん」と思ったつよつよな人はこれ以上の話はここではもう出てこないです......ごめんなさい.

# フィボナッチ数列の前に立ちはだかる問題

なぜフィボナッチ数の計算は失敗してしまうのかというと, いくつかの要因があります.

1. 計算量が爆発する
1. 再帰的な関数呼び出しが深くなりすぎる
1. メモリ消費量が大変なことになる

これらの問題を解決しながら, `bad-fibo`から`good-fibo`へ少しずつ近づいていってみます.
まずはこれらの問題がどのようなものなのかについて簡単に説明します.

## 計算量が爆発する

フィボナッチ数列を再帰でそのまま実装すると計算量が大変なことになるのは有名な話かなと思います.
たとえば`bad-fibo(10)`を呼び出すと, その中で`bad-fibo(8) + bad-fibo(9)`の計算が行われます。`bad-fibo(9)`の中でもやっぱり`bad-fibo(7) + bad-fibo(8)`を計算する必要があります. こんな感じで1回の`bad-fibo`の計算の中で2回の`bad-fibo`が呼び出されるので, $ O(2^n) \$の計算量がかかってしまいます.

この問題を解決するために他の言語だとよく**メモ化**というテクニックが使われています.

## 再帰的な関数呼び出しが深すぎる

**call stack**というものが関係してきます.
[Wikipedia - コールスタック](https://ja.wikipedia.org/wiki/%E3%82%B3%E3%83%BC%E3%83%AB%E3%82%B9%E3%82%BF%E3%83%83%E3%82%AF)

ある関数の中で別の関数を呼び出して, その中でさらに別の関数を呼び出して...といったことはプログラミングでは日常茶飯事だと思います. こんな時, 今処理している関数はどれなのか, 今の関数の処理が完了したらプログラムのどこに戻ればいいのかを覚えておくためにあるのがcall stackです.　stack というのはデータ構造の名前で, 最後に入れたデータを最初に取り出します(LIFO).　このstack のデータ構造に, 呼び出し中の関数を入れて覚えておくということですね.

フィボナッチ数列でこれが問題になるのは, 関数の中で別の関数を呼び出して...という連鎖があまりに長く続きすぎるからです. call stack で覚えておける最大量を超えてあまりに深く再帰的に関数を呼び出しているので「これ以上は覚えきれないよ」というエラーになったのです. スタックオーバーフローというやつです.

この問題を解決するための最適化手法として末尾再帰最適化(TCO)というものがあります. 
Clojure では`recur` という呪文によってTCO が使えます.

## メモリ消費量が大変なことになる

TCO によってある程度フィボナッチ数列が計算できるようになった後で気になってくる最後の問題は, 巨大なフィボナッチ数を計算するときに必要になる大量のメモリです. たとえば`fibo(100000)` を計算するために`fibo(1)` から`fibo(99999)` までの数字を全部覚えておかなければならないのはとても大変です. 

無限に続くシーケンスを簡単に扱うために, Clojure では遅延シーケンス(lazy seq) というものがあります. 

# メモ化してみる

とりあえずこんなことがやりたいんだぞということをPython で書いてみます.

```Python:memo_fibo.py
memo = {}

def memo_fibo(n):
    if n in memo:
        ans = memo[n]
    else:
        if n <= 2:
            ans = 1
        else:
            ans = memo_fibo(n-1) + memo_fibo(n-2)
    memo[n] = ans
    return ans
```

フィボナッチ数列の計算量が爆発してしまう原因は, 同じ計算を無駄に何度も繰り返しているからです.
たとえば`bad-fibo(10)`を計算するためには`bad-fibo(8)` と`bad-fibo(9)` の結果が必要ですが, `bad-fibo(9)` を計算する時にも`bad-fibo(8)`の結果は必要です.
`bad-fibo`では過去に計算した値までもを何度も繰り返し計算しているので、とても時間がかかってしまっているのです.
メモ化というのは一度計算した結果はどこかに覚えておいて使える時は再利用しよう, という作戦です.

では上のPython と同じコードをClojure で書いてみます. 

```Clojure:memo_fibo.clj
(def memo (atom {}))

(defn memo-fibo [n]
  (let [key (keyword (str n))]
    (if (contains? @memo key)
      (key @memo)
      (let [ans (if (<= n 2)
                  1N
                  (+ (memo-fibo (- n 1)) (memo-fibo (- n 2))))]
        (swap! memo assoc key ans)
        ans))))
```

Clojure ではほとんどのデータはイミュータブルです. 今回の`memo` のように何度も上書きして複数の計算で状態を共有したい場合は`atom` を使います.

果たしてメモ化で性能は改善されたのでしょうか?

```
(time (bad-fibo 30)) ; => "Elapsed time: 70.126167 msecs"

(time (memo-fibo 30)) ; => "Elapsed time: 0.056125 msecs"
```

**めっちゃ早くなってる!!!**
`bad-fibo`ではギブアップしていた100番目のフィボナッチ数列も計算できます.

```
(memo-fibo 100N) ; => 354224848179261915075N
```
最後にくっついている'N'は「めっちゃ大きな数を使います」というおまじないくらいに思っておいてください.

では10000番目のフィボナッチ数列はどうでしょうか?

```
(memo-fibo 10000N) ; => Execution error (StackOverflowError)
```

怒られてしまいました......
メモ化でだいぶ高速化はできましたが, 再帰が深くなりすぎるという2番目の問題は解決できていませんでした.

:::note
ちなみに, Clojure の[公式リファレンス](https://clojure.org/reference/atoms)にもatomを使ったフィボナッチ数列のメモ化のコードが載っています.
memoize関数, わけわかんないですね. 自分で同じものを書ける気がしなかったので, 今回は素朴なコードを自前で書きました.
:::


# recur で末尾再帰最適化を使ってみる

スタックオーバーフローの問題を回避するために, `recur` を使って`bad-fibo`を書き直してみます.

```Clojure:recur_fibo.clj
(defn recur-fibo [n]
  (letfn [(f [current next n]
            (if (= 1 n)
              current
              (recur next (+ current next) (dec n))))]
    (f 1N 1N n)))
```

末尾再帰とは, 再帰的な呼び出しがその関数の中の最後のステップだけにあるもののことらしいです.
`bad-fibo`では再帰呼び出しはこんな感じでした.

```Clojure
(+ (bad-fibo (- n 2)) (bad-fibo (- n 1)))
```
これは`bad-fibo(n-2)`を呼び出して, `bad-fibo(n-1)`も呼び出して, その結果が揃ってから足し算をするということなので, 再帰呼び出しが最後のステップだけになっていないです.

これを再帰呼び出しにするために, `bad-fibo(n-2)` と`bad-fibo(n-1)`の結果を引数で渡してしまいます.
`recur-fibo`の中の関数`f`は引数`current`と`next`, `n`を受け取り, 引数`next`, `current + next`, `n-1`で自分を再帰呼び出ししています.

この`recur-fibo`なら`n = 10000`にしても結果はすぐに出てきます.
数字が巨大になりすぎるので結果をここには載せられませんが.

# 遅延シーケンスを使ってみる

なんだか`recur-fibo`でもう良いような気もしますが, Clojure はこれで満足しません.
たとえばあるフィボナッチ数を`num` という名前に束縛した時には, 10000番目のフィボナッチ数を求める計算がその場で走って, 巨大が数字がnum と紐づけられます. 

```Clojure
(def num (recur-fibo 10000))
```

では9999番目のフィボナッチ数が欲しくなった時は？
あるいは, 1000番目から1100番目までのフィボナッチ数だけが欲しくなった時は?
毎回全部計算しないといけないのでしょうか?

Clojure 的には答えはNo です.
そのために遅延シーケンスというものがあります.

遅延シーケンスというのは, 簡単にいうとシーケンスの生成の仕方だけ覚えておいて, 実際の値は本当に必要になるまで計算しないというものです. (厳密には違うかも)
コードはこんな感じになります.

```Clojure:lazy-fibo.clj
(defn lazy-fibo []
  (letfn [(f [current next]
             (let [n (+ current next)]
               (lazy-seq
                (cons n (f next n)))))]
    (concat [1N 1N] (f 1N 1N))))
```

`recur-fibo` と`lazy-fibo` には１つ重大が違いがあります.
`recur-fibo` は1つの数字(n番目のフィボナッチ数)だけを返していましたが, `lazy-fibo`が返すのはシーケンスです. そもそも`lazy-fibo` には引数がありません! 

ではどのように使うのかというと......

```Clojure
(take 10 (lazy-fibo)) ; => (1N 1N 2N 3N 5N 8N 13N 21N 34N 55N)
(drop 90 (take 100 (lazy-fibo))) ; => 91番目から100番目までのフィボナッチ数
```

`take n`はシーケンスの頭からn個の要素をくださいという関数, `drop n` は逆にシーケンスの最初のn個は捨ててくださいという関数です. こんな風に`lazy-fibo` ではフィボナッチ数をシーケンスとして扱えます. なんだかすごく便利になった気がしますね.

`lazy-fibo` の中にある`cons` とか`concat` はシーケンスに要素を追加したり結合したりする関数です.
`lazy-seq`という呼び出しによって, 結果が遅延シーケンスになるようにしています.

正直遅延シーケンスの中身についてはまだ私も深く理解できているとは言い難いので, 細かい説明は省きます.

# シーケンスライブラリを使う

フィボナッチ数を遅延シーケンスで生成することによって, 使い勝手としては申し分ないフィボナッチ関数が完成しました.
しかし, 上記の`lazy-fibo` の書き方はClojure 的にはあまり格好良くないです.
Clojure にはシーケンスを扱う便利な関数が多く用意されているので, それらを使えばもっとスマートに同じことができるのです.
ここで最初に出した模範回答に戻ってきます.

```Clojure:good_fibo.clj
(defn good-fibo []
  (map first (iterate (fn [[a b]] [b (+ a b)]) [1N 1N])))
```

まず重要なのは`(iterate (fn [[a b]] [b (+ a b)]) [1N 1N])` の部分です.
よく考えるとフィボナッチ数の計算で必要なのは直前の2つのフィボナッチ数だけです.
なので, こんなシーケンスを作ってみます.

```Clojure
'([1 1] [1 2] [2 3] [3 5] [5 8] [8 13] ...)
```

このシーケンスの7番目の要素は, 6番目の要素である`[8 13]` を使って次のように計算できます.

```Clojure
[13 (+ 8 13)]
```
これが`(fn [[a b]] [b (+ a b)])` です.
そして, この操作を延々と繰り返しますよと言っているのが`iterate` です.
それでは最初にある`map` と`first` は何をしているのかというと`iterate` が生成してくれたシーケンスの各要素の1つ目の要素だけを抜き出しています. そうするとこんな感じに......

```Clojure
'(1 1 2 3 5 8 13...)
```

フィボナッチ数列の出来上がりというわけです.

最後はなんだか手品でも見せられたような気分になりますが, これがClojure の世界らしいです. 
怖いですね

ということでこの記事はここでおしまいです.
最後まで読んでくださった方がもしもいらっしゃったらありがとうございます.