コンパイラ最適化
既に計算されている結果を再利用することで、再計算する無駄を省く。
Haskell などの関数型言語でのデータ構造の特徴として、一時的なデータ構造を作成・使用する複数の再帰関数を結合することができ、データ構造構築にかかる時間を省くことができる。
コンパイラがより精密な情報を得られれば、各種最適化技法を適用できるようになる。
メモリからロードせずに再計算を行うことで実行時間を節約する。これはレジスタ割り当ての最適化と同時に行われる。再計算コストとメモリアクセスコストのトレードオフによって選択される。
ここで挙げる最適化技法は関数型言語以外にも適用可能な場合が多いが、LISPやMLといった関数型言語向けに開発された技法である。