Haskellの簡約の実装とMemoTrieの秘密?

関数型言語では,グラフ簡約と最外簡約を行うと効率が良くなるらしい.

っていうのを

Amazon.co.jp: 関数プログラミング: R. バード, P. ワドラー, 武市 正人: 本

で読んだきがする.

だから,多分,Haskellも基本的にはグラフ簡約と最外簡約を行なっているはず.

したがって,次のフィボナッチ関数は遅いが.

fib 1 = 1
fib 2 = 1
fib n = fib (n - 1) + fib (n - 2)
*Main> fib 30
832040
it :: Integer
(2.10 secs, 171727632 bytes)

グラフ簡約を使っていることを考えれば,下のように書けば,

各fibNは高々1回しか評価されないので,速い.

fib1 = 1
fib2 = 1
fib3 = fib2 + fib1
fib4 = fib3 + fib2
.
.
.
(略)
.
.
.
fib38 = fib37 + fib36
fib39 = fib38 + fib37
fib40 = fib39 + fib38
*Main> fib30
832040
it :: Integer
(0.00 secs, 525800 bytes)

多分,MemoTrieはこういうことを利用して,メモ化を行ってるのでは?

(ソースコード読んでみたけど,よく分からない)