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

っていうのを

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はこういうことを利用して，メモ化を行ってるのでは？

（ソースコード読んでみたけど，よく分からない）