GHCで自動的にメモ化される条件

ghcコンパイラで自動的にメモ化される条件を調べてみました。
##フィボナッチ数を計算
例としてよくあげられているフィボナッチ数の計算です。

fib1.hs

fib 0 = 0
fib 1 = 1
fib n = fib (n-2) + fib (n-1)

main = print $ fib 40

これをtimeで時間を測ってみますと、0m19.056sかかりました。
次にfib nを展開したプログラムです。長くなりますが40まで展開しています。

fib2.hs

fib' 0 = 0
fib' 1 = 1
fib' 2 = fib' 0 + fib' 1
fib' 3 = fib' 1 + fib' 2
fib' 4 = fib' 2 + fib' 3
fib' 5 = fib' 3 + fib' 4
fib' 6 = fib' 4 + fib' 5
fib' 7 = fib' 5 + fib' 6
fib' 8 = fib' 6 + fib' 7
fib' 9 = fib' 7 + fib' 8
fib' 10 = fib' 8 + fib' 9
fib' 11 = fib' 9 + fib' 10
fib' 12 = fib' 10 + fib' 11
fib' 13 = fib' 11 + fib' 12
fib' 14 = fib' 12 + fib' 13
fib' 15 = fib' 13 + fib' 14
fib' 16 = fib' 14 + fib' 15
fib' 17 = fib' 15 + fib' 16
fib' 18 = fib' 16 + fib' 17
fib' 19 = fib' 17 + fib' 18
fib' 20 = fib' 18 + fib' 19
fib' 21 = fib' 19 + fib' 20
fib' 22 = fib' 20 + fib' 21
fib' 23 = fib' 21 + fib' 22
fib' 24 = fib' 22 + fib' 23
fib' 25 = fib' 23 + fib' 24
fib' 26 = fib' 24 + fib' 25
fib' 27 = fib' 25 + fib' 26
fib' 28 = fib' 26 + fib' 27
fib' 29 = fib' 27 + fib' 28
fib' 30 = fib' 28 + fib' 29
fib' 31 = fib' 29 + fib' 30
fib' 32 = fib' 30 + fib' 31
fib' 33 = fib' 31 + fib' 32
fib' 34 = fib' 32 + fib' 33
fib' 35 = fib' 33 + fib' 34
fib' 36 = fib' 34 + fib' 35
fib' 37 = fib' 35 + fib' 36
fib' 38 = fib' 36 + fib' 37
fib' 39 = fib' 37 + fib' 38
fib' 40 = fib' 38 + fib' 39

main = print $ fib' 40

0m0.003sと大幅に速くなっています。
何か起こっているのか調べてみます。traceを使うと式が評価される状況がわかります。

fib3.hs

import Debug.Trace

fib'' 0 = 0
fib'' 1 = 1
fib'' n = trace ("fib'' "++show n) (fib'' (n-2) + fib'' (n-1))

main = print $ fib'' 40

この場合は、同じnであっても何回も評価されています。

fib2.hsの方も同じくtraceで調べると(長くなるのでここには書きません)、一回ずつしか評価されないことがわかります。
要するに、fib2.hsでは自動的にメモ化され、その効果が出ていることがわかりました。

(注意)
必ずコンパルして実行してください。ghciだとメモ化されないことが多くあります。

##リストを出力する場合
次は1からnまでのリストを出力するプログラムです。
33, 34, 35までを連続して出力します。

fib4.hs

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

fibList n = map fib [0..n]

main = do
  print $ fibList 33
  print $ fibList 34
  print $ fibList 35

この場合は0m8.229sかかりました。
5行目だけを変えています。

fib5.hs

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

fibList' n = take n $ map fib [0..]

main = do
  print $ fibList' 33
  print $ fibList' 34
  print $ fibList' 35

こちらの方は、0m2.536sと速くなっています。
traceを使ってみますと、上はfibが1から33,1から34,1から35と毎回計算されていますが、下のプログラムでは1から35までを1回計算しただけです。

map fib [0..]は自動的にメモ化されるが、map fib [0..n]ではされないこと結果になりました。

まとめると、変数を使わない計算は自動的にメモ化されるが、変数があるとメモ化がされないようです。

こちらの方は使い道がかなりありそうです。

使用装置
MacOS 10.12.5 CPU Core i5-2467M 1.60GHz
GHC 8.0.2