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

はじめに

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

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

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

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

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

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

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

bad_fibo.py

def bad_fibo(n):
    if n <= 2:
        return 1
    return bad_fibo(n-1) + bad_fibo(n-2)

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で書いてみます.

bad_fibo.clj

(defn bad-fibo [n]
  (if (<= n 2)
    1
    (+ (bad-fibo (- n 1)) (bad-fibo (- n 2)))))

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

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

Clojure のコードを見ること自体が初めての人はこの時点で驚くかもしれません.
Clojure では1 + 1 を(+ 1 1)と書きます.
前置記法(ポーランド記法)というらしいです.

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

いろいろと書く前にいきなりゴールを書いちゃいます.
プログラミングClojure という本にフィボナッチ数列の模範回答が載っています. こんな感じです.

good_fibo.clj

(defn good-fibo []
  (map first (iterate (fn [[a b]] [b (+ a b)]) [1N 1N])))

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

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

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

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

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

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

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

これらの問題を解決しながら, 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 - コールスタック

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

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

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

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

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

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

メモ化してみる

とりあえずこんなことがやりたいんだぞということを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 で書いてみます.

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番目の問題は解決できていませんでした.

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

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

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

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では再帰呼び出しはこんな感じでした.

(+ (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 と紐づけられます.

(def num (recur-fibo 10000))

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

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

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

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 には引数がありません!

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

(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 にはシーケンスを扱う便利な関数が多く用意されているので, それらを使えばもっとスマートに同じことができるのです.
ここで最初に出した模範回答に戻ってきます.

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つのフィボナッチ数だけです.
なので, こんなシーケンスを作ってみます.

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

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

[13 (+ 8 13)]

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

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

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

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

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