「Haskellをかける少女」の続編です。
アルゴリズムの最適化および末尾呼出し最適化について書きます。

今日もブラックな某Web制作会社にて

ハスケル子「おはようございます」

ワイ「おう、おはよう」

ハスケル子「やめ太郎さん、それ何してるんですか」

ワイ「おお、これはな」
ワイ「データベースのパスワードをプリントアウトしてシュレッダーにかけてんねや」
ワイ「うちの会社では全ての機密情報をシュレッダーにかけなあかん事になっとる」
ワイ「コンピュータ上の機密情報も、形式上一旦プリントアウトしてシュレッダーにかけなあかんねや」

ハスケル子「そ、それはすごいセキュリティ意識ですね」

ワイ「君も覚えときや？」
ワイ「機密情報をプリントアウトして、その紙に社長のハンコを押して、そのあとシュレッダーや」

ハスケル子「（押印→即シュレッダー・・・！？）」
ハスケル子「そのハンコの意味は・・・」

ワイ「ん？ハンコがどうしたんや」
ワイ「ああ、社長のハンコならいつでもこのデスクの上に置いてあるから大丈夫やで？」

ハスケル子「わ、分かりました」
ハスケル子「（何が大丈夫なんだろう）」

なんで今それをやってたか

ワイ「実はさっきワイのMacのSafariが急に固まってもうてな」
ワイ「ちょっとMacを休ませたろ思って、その間にシュレッダーをやってたんやけど」
ワイ「そのことでケル子ちゃんに聞きたい事があんねん」
ワイ「昨日教えてもらったフィボナッチ数を求める関数で」
ワイ「100番目のフィボナッチ数を表示させてみようとしたらSafariが固まってしまってん」

ハスケル子「それはそうですね」
ハスケル子「あのコードは実用的ではないので」

ワイ「あら」
ワイ「何でそんなん教えたん・・・」

ハスケル子「実用性を考えたら別の書き方もあるんですけど」
ハスケル子「フィボナッチ数を再帰で求めることも知らない人に」
ハスケル子「いきなりその先のコードを教えるのは難しいと思って」

ワイ「（ぐぬぬ）」
ワイ「（悔しいが、勉強になったから素直に聞いとこか）」
ワイ「ほな、その先のコードってやつをワイに教えてみてくれへん？」
ワイ「教え方の研修みたいなもんや」

社長「（ぜんぜん素直ちゃうやん・・・)」

ハスケル子「分かりました」

再帰的な処理が重くなった理由

ハスケル子「まず、昨日の関数ですけど」

keruko.js

const fibo = n => (n === 0 || n === 1)? n: fibo(n - 1) + fibo(n - 2);

ハスケル子「10番目のフィボナッチ数を求めるために」
ハスケル子「9番目と8番目のフィボナッチ数を求めようとする」
ハスケル子「つまり」

keruko.js

fibo(10);

ハスケル子「↑これが」

keruko.js

fibo(9) + fibo(8)

ハスケル子「これに変身するイメージです」

ワイ「せやな」
ワイ「（なるほどな・・・）」
ワイ「（戻り値が返ってくることを変身すると捉えるんやな）」
ワイ「（ここまでは分かるで）」

ハスケル子「そして次は」
ハスケル子「9番目と8番目のフィボナッチ数を求めなければいけないので」
ハスケル子「9番目を求めるために8番目と7番目を求め、」
ハスケル子「8番目を求めるために7番目と6番目を求めることになります」
ハスケル子「つまり、さっきのコードが更に・・・」

keruko.js

fibo(8) + fibo(7) + fibo(7) + fibo(6)

ハスケル子「↑こう変身するイメージです」

ワイ「せやせや」
ワイ「（おお、分かってきたで・・・！）」

ハスケル子「その次はこう」

keruko.js

fibo(7) + fibo(6) + fibo(6) + fibo(5) + fibo(5) + fibo(4) + fibo(4) + fibo(3)

ハスケル子「こんな感じで関数fiboの実行回数がどんどん2乗になっていくので・・・」
ハスケル子「Safariちゃんの計算量も激増していきます」

ワイ「せやな」
ワイ「関数fiboをウン百回実行するで〜！！！」
ワイ「いうてSafariがいっぱいいっぱいになってまうわけやな」

ハスケル子「177回ですね」

ワイ「せやな（ぐぬぬ）」

ハスケル子「ちなみに、あくまでイメージなので実際の計算順序は異なります」

ワイ「せやな」
ワイ「（もはや何を言うてんのか分からんで）」

ハスケル子「そしてこのコードをどうやって最適化するかですけど」
ハスケル子「自分自身を1回だけ呼び出すような関数に書き換えればいいんです」

keruko.js

const rec = (f2, f1, n) => {
  if (n === 1) return f1;
  return rec(f1, f2+f1, n-1);
};

const fibo = n => (n < 2)? n: rec(0, 1, n);

ハスケル子「こうです」

ハスケル子「recっていうのが再帰的に呼び出される関数なんですけど」
ハスケル子「再帰呼出しは関数の最後に1回するだけなので」
ハスケル子「変身するたびに回数が倍増しないんです」

ワイ「せや」
ワイ「（どういう事・・・？）」

ハスケル子「一応解説しますね」

ワイ「お、おう」
ワイ「一応たのむわ」

ハスケル子「まず・・・」

keruko.js

fibo(10);

ハスケル子「このように関数fiboを実行すると」

keruko.js

rec(0, 1, 10);

ハスケル子「その中で再帰呼出し用の関数recが実行されます」

ハスケル子「そのあとの変身イメージはこんな感じです」

keruko.js

rec(0, 1, 10);
// ↓
rec(1, 1, 9)
// ↓
rec(1, 2, 8)
// ↓
rec(2, 3, 7)
// ↓
rec(3, 5, 6)
// ↓
rec(5, 8, 5)
// ↓
rec(8, 13, 4)
// ↓
rec(13, 21, 3)
// ↓
rec(21, 34, 2)
// ↓
rec(34, 55, 1)
// ↓
55

ハスケル子「関数の実行回数が倍々ゲームにならないんです」
ハスケル子「10回ちょっとで終わりです」
ハスケル子「要は・・・」

keruko.js

fibo(n - 1) + fibo(n - 2)

ハスケル子「っていうように自分の中で自分自身を2回呼ぶから倍々ゲームになるわけなので」
ハスケル子「それを」

keruko.js

rec(f1, f2+f1, n-1)

ハスケル子「というように、1回だけ呼び出すようなコードに変換してあげれば」
ハスケル子「関数の実行回数は倍々ゲームにならないので」
ハスケル子「Safariちゃんの負担を激減できるんです」

ワイ「せやな」
ワイ「（おお・・・！）」

ハスケル子「昨日のコードだと42番目のフィボナッチ数を求めたくらいでSafariが悲鳴を上げ始めますけど、」
ハスケル子「今のコードなら、1000番目のフィボナッチ数が」
ハスケル子「1ミリ秒以下で返ってきます」

ワイ「1ミリ秒・・・！」
ワイ「（まじか）」

ハスケル子「しかも、関数の処理の最後に1回だけ再帰呼出しするようなコードにしておくと」
ハスケル子「Safariで使用されているJSエンジンが内部で最適化して」
ハスケル子「関数の実行予約を溜め込まない形で実行してくれるんです¹」
ハスケル子「そうすることで、再帰呼出しを何十万回もできたりします」

ワイ「スタックオーバーフローにならへんいうことやな」

ハスケル子「はい」
ハスケル子「ただ、ブラウザやコンパイラが対応していないと末尾呼出しの最適化はされませんけどね」

ワイ「いうても最近のブラウザは対応してるから大丈夫やで」

ハスケル子「してませんよ」
ハスケル子「iOSのSafariとMacのSafariくらいです」

ワイ「（アカン、間違えた！？）」
ワイ「でも、ChromeはんとかFirefoxはんとかは・・・？」

ハスケル子「まだです」

ワイ「」

ハスケル子「2015年に策定された仕様なのに、何やってるんですかね。ほかのブラウザたちは」

ワイ「（いやいや、ChromeもFirefoxもメッチャ素敵なブラウザやろ・・・）」
ワイ「（なんや、もしかしてApple信者かいな）」
ワイ「（あれ・・・この子、よく見たら・・・）」
ワイ「（両腕にApple Watchを3本ずつ着けとるやないか・・・！！！）」
ワイ「（もはや狂信者やないかい・・・）」

ワイ「せやな、Safari一択やで！！！」

社長「（危険を察知して忖度しおった・・・！）」

そんなこんなで今日の研修（？）終了

ハスケル子「昨日はすみませんでした」
ハスケル子「実用性のないコードをお見せしてしまって」

ワイ「ええで、勉強になったから」
ワイ「（なんや、ええ子やないか）」

ハスケル子「なんていうか」
ハスケル子「for文でループしたり」
ハスケル子「その中で配列にどんどん数値を継ぎ足したりして」
ハスケル子「フィボナッチ数列の状態を管理していくことを意識しなくても」
ハスケル子「定義を書くだけで答えは求まる・・・」
ハスケル子「Haskellで知ったその感じを、やめ太郎さんにも教えてあげたかっただけなんです」

ワイ「せやよな・・・」
ワイ「（結局ちょっと上からやねんな・・・・）」

〜Fin〜

追記

さらに続編や！
→純粋関数型言語と参照透過性
→ワイのElmデビュー

末尾呼出し最適化はstrict modeでないと有効にならへんで。 ↩