トランポリン最適化
概要
スタックの代わりにヒープを使うことで再帰呼び出しを行う
末尾再帰最適化もトランポリン最適化もスタック→ヒープ最適化なのでメモリとかコンピュータの実行モデルのイメージがあると理解しやすい 関数の合成が積み重なると、それを最後に呼び出す時に一気にコールスタックが積まれることになる
トランポリン化は関数呼び出しが数珠つなぎになって深くなってしまうのを、一回ずつの呼び出しにして切断する
https://gyazo.com/d3c92e1e34c12854c71616ed68547dec
トランポリンは、TCO（コンパイラの自動最適化）が使えない場合の「手動TCO」のようなものです。コンパイラに頼れない代わりに、プログラマが自ら計算の「継続」をデータ構造として管理し、それを一つのループで処理するテクニックと言えます 例
catsでのmonad実装
Freeモナド
参照