メモ化とボックス型とグラフ簡約（Haskellとメモ化のこと　その３）

Haskell Memoize

本業のほうが立て込んでしまって、ずいぶんと時間が空いてしまいました。

えー、ここまでのHaskellの勉強の過程で、どうゆう理由でか、あるいはどこから仕入れたのかははっきりしないのですが、Haskellではメモ化が自動、兼タダで手に入ると僕は思い込んでいたわけです。

それで色々と試してみたのがその1とその2だったわけなんですが、結果から言って、確かにメモ化されているような動きをすることもあるのですが、なんと言うか、いつでもメモ化の作用が効いているわけでもないようです。

Haskellで定義される関数は参照透過性がIOモナドな関数などの一部を除いて保証されているので、もっとアグレッシブにメモ化を進めることもできるような気もするのですが、なぜそうなっていないかは謎です。

こちらに記事を書いていない間もちょこちょこと調べてみていたのですが、一つ試してみたのが、IOArrayとIOUArrayでした。何を試してみたかというと、次のようなことです。

module Main where

import Data.Array.IO
import Debug.Trace

foo x = trace "Foo called" x * 2

testArray ar = do
	trace "newArray done" $ return ()
	readArray ar 0 >>= print
	readArray ar 1 >>= print
	trace "calling mapArray" $ return ()
	ar' <- mapArray (foo) ar
	trace "mapArray done" $ return ()
	readArray ar' 0 >>= print
	readArray ar' 1 >>= print

main = do
	trace "testing IOArray" $ return ()
	ref::(IOArray Int Int) <- 
		newListArray (0, 1) [(foo 3), (foo 3)]
	testArray ref

	trace "testing IOUArray" $ return ()
	refUB::(IOUArray Int Int) <- 
		newListArray (0, 1) [(foo 3), (foo 3)]
	testArray refUB
	
=>
testing IOArray
newArray done
Foo called
6
Foo called
6
calling mapArray
mapArray done
Foo called
12
Foo called
12

testing IOUArray
Foo called
Foo called
newArray done
6
6
calling mapArray
Foo called
Foo called
mapArray done
12
12

といった感じで、IOArrayとIOUArrayの能書きどおり、IOArrayはMutableなArray型。Mutableなこと以外はHaskellのほかの型と同じようにその値の計算がLazyに行われているのがわかります。一方IOUArrayのほうはMutableな上にUnboxなんだそうで、そのUnboxというのは一体何かというと、それはつまり、いわゆるC/C++言語で言うところの変数に近いもののようです。つまりLazyができない。代入する時点で計算を行わなくてはならないわけですね…これに対してHaskellでは普通なLazyな変数のことをBox型というらしいです。

ここで、立ち返ってメモ化をするためには一体何が必要かを考えると、メモ化をするためには、2つのデータを記憶する必要があることがわかります…つまりそれは計算自身とその計算結果です。次のようなマップを維持してこそどの計算が実行済みかどうかがわかるわけですよね…

	　式	値
	(1 + 1)	=2
	2 * 3	=6
	1 + 4	=5
	foo 1	=2

この観点でHaskellのLazyなBox型を見てみると、Box型は評価前は計算式を覚えているけど、評価後は計算結果しか覚えていない…ということで実はBox型だけではメモ化は達成できないはずです…

では何でメモ化がうまく行ってる部分があったのか…それはどうやらHaskellが式の評価のために行っている｢グラフ簡約｣というものによるようです。こちらの記事に詳しい説明が載っていました。以前にも読んだと思ったのですが、内容が盛りだくさんだったので頭に残らなかったようです。

グラフ簡約では式をグラフの形に表現するようで、

foo i = i * 2
foo3 = foo 3
xs = [foo3, foo3]

とやった場合、xsの中身を表現するデータ構造の中ではfoo3は1回しか出てこない。だからfoo3が評価されるのは1回だけで、2回目の参照はメモ化された計算結果が利用されるということになっているようです。つまり、Haskellのメモ化はBox型＋グラフ簡約によるということのようです。（というか、グラフ簡約といった時点でBox型は前提とされているようにも思われます…)

だとすると、焦点になってくるのは一体プログラムのどの塊が一つのグラフに表現されるのかという点なわけですが、これは今まで色々と試したサンプルから判断して、プログラム全体であるはずはなくて、更に関数一つというわけでもなさそうです。
僕が関数一つではないと思う理由はその2のときのサンプルで

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

main = do
print [(sumL!!3, sumL!!4)]
print [(sumL!!3, sumL!!4), (sumL!!3, sumL!!4)]
    :
print ([sumL!!3, sumL!!4], 
[sumL!!5, sumL!!6], 
[sumL!!7, sumL!!8])

とやったときには関数sumLは少なくとも各printに対して1回は呼ばれていたからです。

do文は一つの式であることは変わりなくて、各行がラムダ式でつながっているわけですから、そんなに特殊なわけでもないですよね…ということでやってみたのが次の実験です。

foo i = trace "Foo called" i * 2
foo3 = foo 3

main = do
　　print "lambda"
　　print $ (\x -> x + foo3) foo3
　　print "monad"
　　print $ fromJust $ (Just foo3) >>= \i -> Just (foo3 + i)
　　print $ fromJust $ do
	　　i <- (Just foo3) 
	　　Just (foo3 + i)

=>
"lambda"
Foo called
12
"monad"
Foo called
12
Foo called
12

ということで、ラムダ式でも、Maybeモナドで>>=を使った式とdo文を使った式のいづでれでもfoo3は一回しか評価されていないことがわかります。
でもIOモナドである一番外側のdo文についてはfoo3はまったく共有されていません…これはつまりIOモナドがグラフ簡約のスコープの境目を作っているということなんでしょうか…

運がよければ関数全体がグラフ簡約の対象になるけれど、IOモナドなどが入ってくるとグラフ簡約のユニットはもっと小さなものになるということのようです。

ということは、Haskellのグラフ簡約をうまく利用するには、メモ化したい対象の値を変数に代入して、その変数の参照をできるだけ一つのIOモナドでない関数にまとめると良いということかもしれません。

ほかにもグラフ簡約のユニットの制約になるものはあるのでしょうか…

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