Haskellのメモ化のこと

Haskell Memoize


僕の今までのメモ化の理解はこうです：

Haskellでは値を必要となるときまで式は評価されない。(遅延評価）したがって値が必要にならない式は評価されない。そして、評価された式の値は記憶されるので式が再評価されることはない（メモ化）。

さて、Debug.Traceというライブラリに

trace :: String -> a -> a

という関数があります。これは式が評価されたときにエラー出力にStringを出力して、評価結果としてaを返すという関数です。unsafeなのでデバッグ用にのみ使うことという但し書きが着いています。これを使えば、こんなことができます：

plus1 x = trace "plus1 is called" (x + 1)

main = do
	print plus1 2
	print plus1 3
	
=>
plus1 is called
3
plus1 is called
4

ということで、これがあればIO型でない関数でも実際に評価がされたときを知ることができます。さて、僕のメモ化の理解によれば、｢評価された式の値は記憶される」なので、ひょっとしたら上のサンプルに2回出てくるplus1のパラメタの値を両方同じにしたらplus1は1回だけ呼ばれて終わるのでしょうか？

plus1 x = trace "plus1 is called" (x + 1)

main = do
	print plus1 2
	print plus1 2
	
=>
plus1 is called
3
plus1 is called
3

結果はそんなことはありません。メモ化はどこ行った？この時点で僕が思ったことは、ひょっとして変数にしかメモ化できないのか？ということです。そこでやったのが、これ：

plus1 x = trace "plus1 is called" (x + 1)
plus1and2 = plus1 2
main = do
	print plus1and2
	print plus1and2
	
=>
plus1 is called
3
plus1 is called
3

まだ２回呼ばれています…このほかにも、letもwhereも使ってみましたが、結果は同じでした。どうやらHaskellのメモ化はどこでも起きているわけではないようです。

それじゃあ一体いつメモ化は起きるんだということで、色々読んでみたり、試したりして見つけたのが次のような例でした：

sumL = (trace "sumL 0 is called" 0) : zipWith (+) sumL [1..]

sum' 0 = (trace "sum' 0 is called" 0)
sum' x = sum' (x - 1) + x

main = do
	print $ take 5 sumL
	print $ map (sum') [0..4]
	
=>
sumL 0 is called
[0,1,3,6,10]
sum' 0 is called
sum' 0 is called
sum' 0 is called
sum' 0 is called
sum' 0 is called
[0,1,3,6,10]

ということで、mainの2つのprintは両方とも0から4までについての合計を求めているわけですが、sumLを使っているほうは0は一回しか評価されていないのに対して、sum'のほうは5回評価されています。なるほど…やっと出てきましたよ、メモ化。この例でわかるのはsumLは評価の結果をリストに格納して、それを参照することで、メモ化を達成しているということ。sum'のほうは単なる再帰呼び出しなわけですが、ここではメモ化はまったく起きていないようです。

次に試してみたのが、ちょっと意地の悪いサンプル：

print $ zipWith (!!) (replicate 5 sumL) [0..4]

この例では、zipWith (!!) [sumL, sumL, sumL, sumL, sumL] [0..4]となって、sumLが何度も繰り返されるのでメモ化はそれぞれのsumLの間では共有されないのではと思ったのですが、なんとこれでもトレースは1回しか出力されません。

色々試している間に気づいたのですが、

main = do
	print $ sumL!!3
	print $ sumL!!4

とやったときはトレースは2回出力されます。
でも
main = print $ [sumL!!3, sumL!!4]
とやるとトレースは1回しか出ません…なんじゃこりゃ？なんだか、リスト型にメモ化はインプリメントされているということなんでしょうか？とおもって、
main = print $ (sumL!!3, sumL!!4)
とやるとなんとトレースが2回出てくるじゃぁありませんか！ほんとにリスト型にメモ化が入ってるのか？Treeとか、Maybeとか、ほかのコンテナ型はどうなってるんでしょうか？

そもそもの興味の始まりはメモ化とMutableな型の関係なんですが、Haskellのメモ化は思ったより奥が深いということを知らなかったおかげで、Mutableまでいけませんでした…自分の理解がいかにあいまいだったか、よくわかりました…どうやらHaskellでメモ化を積極的に使うためには色々と知っておいたほうが良いことがありそうです…

今日はこの辺で。
ではでは。