Haskellをかけない中年

Haskellをかけない中年:

「Haskellをかける少女」の続編です。
末尾呼出し最適化について書きます。

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

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

ワイ「おう、おはよう」

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

ワイ「おお、これはな」

ワイ「データベースのパスワードをプリントアウトしてシュレッダーにかけてんねや」

ワイ「うちの会社では全ての機密情報をシュレッダーにかけなあかん事になっとる」

ワイ「コンピュータ上の機密情報も、形式上一旦プリントアウトしてシュレッダーにかけなあかんねや」

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

ワイ「君も覚えときや？」

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

ハスケル子「ハ、ハンコ・・・」

ハスケル子「（押印、即シュレッダー・・・？）」

ワイ「ハンコがどうしたんや」

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

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

ハスケル子「（何が大丈夫なんだろう）」

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

ワイ「実はさっきワイのMacのSafariが急に固まってもうてな」

ワイ「ちょっとMacを休ませたろ思って、その間にシュレッダーをやってたんやけど」

ワイ「そのことでケル子ちゃんに聞きたい事があんねん」

ワイ「昨日教えてもらったフィボナッチ数を求める関数で」

ワイ「100番目のフィボナッチ数を表示させてみようとしたらSafariが固まってしまってん」

ハスケル子「それはそうですね」

ハスケル子「あのコードは実用的ではないので」

ワイ「あら」

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

ハスケル子「実用性を考えたら別の書き方もあるんですけど」

ハスケル子「フィボナッチ数を再帰で求めることも知らない人に」

ハスケル子「いきなりその先のコードを教えるのは難しいと思って」

ワイ「（ぐぬぬ）」

ワイ「（悔しいが、勉強になったから素直に聞いとこか）」

ワイ「ほな、その先のやつをワイに教えてみてくれへん？」

ワイ「教え方の研修みたいなもんや」

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

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

再帰的な処理が重くなる理由

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

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

ハスケル子「10番目のフィボナッチ数を求めるために」

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

ハスケル子「つまり」

fibo(10); 

ハスケル子「↑これが」

fibo(9) + fibo(8) 

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

ワイ「せやな」

ワイ「（なるほどな・・・）」

ワイ「（戻り値が返ってくることを変身すると捉えるんやな）」

ワイ「（ここまでは分かるで）」

ハスケル子「そして次は」

ハスケル子「9番目と8番目のフィボナッチ数を求めなければいけないので」

ハスケル子「9番目を求めるために8番目と7番目を求め、」

ハスケル子「8番目を求めるために7番目と6番目を求めることになります」

ハスケル子「つまり、さっきのコードが更に・・・」

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

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

ワイ「せやせや」

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

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

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

ハスケル子「こんな感じでどんどん2乗になっていくので・・・」

ワイ「せや」

ワイ「最終的にはMacが」

ワイ「さて、関数fiboをウン百回実行するで〜！！！」

ワイ「いうていっぱいいっぱいになってまうわけやな」

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

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

ハスケル子「JavaScriptが最後にまとめて計算してるのか、先に部分的に計算してるのかは分かりません」

ワイ「せやな」

ワイ「（もう何を言うてんのか分からん）」

ハスケル子「そしてこのコード、というか処理をどうやって最適化するかですけど」

ハスケル子「関数fiboの中で関数fiboを再帰的に呼び出すときに」

ハスケル子「それが関数内の最後の処理になるように書けばいいんです」

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っていうのが再帰的に呼び出される関数なんですけど」

ハスケル子「再帰呼出しが関数の最後の処理になっているので」

ハスケル子「変身するたびにコードが長くならないんです」

ワイ「せや」

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

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

ワイ「お、おう」

ワイ「一応たのむわ」

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

fibo(10); 

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

rec(0, 1, 10); 

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

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

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 

ハスケル子「倍々ゲームにならないんです」

ハスケル子「要は・・・」

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

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

ハスケル子「それを」

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

ハスケル子「というように、最後に1回だけ呼び出すようなコードに変換してあげれば」

ハスケル子「あとはSafariで使用されているJSエンジンが内部で最適化して」

ハスケル子「関数の実行予約を溜め込まない形で実行してくれるんです」

ハスケル子「昨日のコードだと42番目のフィボナッチ数を求めたくらいでSafariが悲鳴を上げ始めますけど、」

ハスケル子「末尾再帰にしたコードでは、1000番目のフィボナッチ数が」

ハスケル子「1ミリ秒以下で返ってきます」

ワイ「1ミリ秒・・・！」

ワイ「（まじか）」

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

ワイ「いうても最近のブラウザは対応してんねやろ？」

ハスケル子「はい、iOSのSafariもMacのSafariも対応してます」

ワイ「え・・・」

ワイ「ChromeはんとFirefoxはんは・・・？」

ハスケル子「まだです」

ワイ「」

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

ワイ「（いやいや、ChromeもFirefoxもメッチャ素敵なブラウザやろ・・・）」

ワイ「（なんや、もしかしてApple信者かいな）」

ワイ「（あれ・・・この子、よく見たら・・・）」

ワイ「（両腕にApple Watchを3つずつ着けとるやないか・・・！！！）」

ワイ「（いやいやいやいや・・・）」

ワイ「（こらSafariを批判するのは危険や・・・）」

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

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

ハスケル子「昨日はすみませんでした」

ハスケル子「実用性のないコードをお見せしてしまって」

ワイ「ええで、勉強になったから」

ワイ「（なんや、ええ子やないか）」

ハスケル子「なんていうか」

ハスケル子「for文でループしたり」

ハスケル子「その中で配列にどんどん数値を継ぎ足したりして」

ハスケル子「フィボナッチ数列の状態を管理していくことを意識しなくても」

ハスケル子「定義を書くだけで答えは求まる・・・」

ハスケル子「その感じをやめ太郎さんに教えたかっただけなんです」

ワイ「せやよな・・・」

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

〜Fin〜