Tech Tips: Haskellで正格評価

2011年6月27日月曜日

　遅延評価は、

・無駄な計算をしない

・無限長のデータ構造を定義できる

などの利点がある。

　「無駄な計算をしない。」については、たらいまわし関数が有名。

tarai x y z  | x <= y    = y
              | otherwise = tarai (tarai (x-1) y z) (tarai (y-1) z x) (tarai (z-1) x y)

あとは、以下のような処理に対しても遅延評価が有効的にはたらく。

(?) :: Integer -> Integer -> Integer
(?) _ 0 = 0
(?) 0 _ = 0
(?) x y = x * y

main = print $ foldl (?) 1 [100000,99999..0]

　だが、「無駄な計算をしない」=「計算が速くなる」が必ず成り立つかというとそうでもない。簡約されない式がメモリを圧迫してパフォーマンス低下の原因になることがある。たとえば、以下の式を考えてみる。

main = print $ foldl (+) 0 [1..1000000]

上の処理はスタックオーバーフローを起こす。（foldrの場合も同様。）

　なぜ、スタックオーバーが起こるのかfoldl、foldrの場合それぞれにおいて考える。

まずは、foldl、foldrを自分で定義してみる。

foldr f z []     = z
foldr f z (x:xs) = x `f` foldr f z xs

foldl f z []     = z
foldl f z (x:xs) = foldl f (f z x) xs

こうやって見てみると、foldlは命令型言語のループに近いと思う。（または、末尾再帰。）

これに対して、foldrは再帰処理のように見える。

　foldrがstack overflowを起こすのは、C++で深い再帰を書いたときにオーバーフローが起こるのと同じ原因。非末尾型の再帰のような形で式が簡約されるので、現ループの結果を出すために、次のループの結果が必要、次のループを計算するためには、次の次の結果が必要・・・。

というふうになる。結果保持しておかなければいけない値がスタックを圧迫してしまう。

　foldlの場合は、少し違う。遅延評価が関係している。foldrの場合と違って、現ループの結果はその時点で計算できるが、遅延評価のおかげで実際に必要になるまでに評価されない。

結果、thunkがヒープに書きこまれる。（簡約がはじまるまでは、遅延評価はヒープを食いつぶしている。。）実際に必要になったときに簡約が始まるが、外側から（一番深いところ）簡約が始まるため、foldlと同じことが起こってしまう。（詳しくはこのページを参照。）

　これに対してfoldl'を使うと、遅延評価をせずに、すぐにthunkをforceするため、オーバーフローは起こらない。

import Data.List

main = print $ foldl' (+) 0 [1..1000000]

foldl'は次のように定義することができる。

foldl' f z []     = z
foldl' f z (x:xs) = f z x `seq` foldl' f (f z x) xs

ここで、seq x y はxを先に簡約して、y（yはxを参照している）をreturnする関数である。

seqは以下のような書き方もできる。

f $! x = x `seq` f x

これに対して、遅延評価をするために以下のような演算子がある。（この演算子はは良く見るはず。）

f $ x  = f x

　基本的には遅延評価を使うというスタンスで、どうしても遅延評価がパフォーマンスを低下させている場合のみ、正格評価を利用するよう感じで書けばいいと思う。

遅延評価のメリットは、計算を速くすることというよりも、無限長のリストや停止しない処理を定義できることにあると思う。

Tech Tips