Haskellをかけない中年

「[**Haskellをかける少女**](https://qiita.com/jzmstrjp/items/11dcd3ec26027ff30214)」の続編です。
**アルゴリズムの最適化**および**末尾呼出し最適化**について書きます。

# 今日もブラックな某Web制作会社にて
ハスケル子「おはようございます」

ワイ「おう、おはよう」

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

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

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

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

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

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

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

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

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

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

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

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

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

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

# 再帰的な処理が重くなった理由
ハスケル子「まず、昨日の関数ですけど」

```javascript:keruko.js
const fibo = n => (n === 0 || n === 1)? n: fibo(n - 1) + fibo(n - 2);
```

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

```javascript:keruko.js
fibo(10);
```

ハスケル子「↑これが」

```javascript:keruko.js
fibo(9) + fibo(8)
```

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

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

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

```javascript:keruko.js
fibo(8) + fibo(7) + fibo(7) + fibo(6)
```

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

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

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

```javascript: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回だけ呼び出す**ような関数に書き換えればいいんです」

```javascript: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回するだけ**なので」
ハスケル子「変身するたびに**回数が倍増しない**んです」

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

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

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

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

```javascript:keruko.js
fibo(10);
```

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

```javascript:keruko.js
rec(0, 1, 10);
```

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

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

```javascript: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回ちょっと**で終わりです」
ハスケル子「要は・・・」

```javascript:keruko.js
fibo(n - 1) + fibo(n - 2)
```

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

```javascript:keruko.js
rec(f1, f2+f1, n-1)
```

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

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

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

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

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

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

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

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

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

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

ハスケル子「**まだです**」

ワイ「」

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

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

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

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

# そんなこんなで今日の研修（？）終了
ハスケル子「昨日はすみませんでした」
ハスケル子「実用性のないコードをお見せしてしまって」

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

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

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

**〜Fin〜**

# 追記
さらに続編や！
→[**純粋関数型言語と参照透過性**](https://qiita.com/jzmstrjp/items/1de3c2b76b8a4dc2d30d)
→[**ワイのElmデビュー**](https://qiita.com/jzmstrjp/items/eb6fd45fe6324906a71a)
[^1]: **末尾呼出し最適化**は```strict mode```でないと有効にならへんで。