Haskellの評価戦略とfoldl/foldr (1)
- 末尾再帰はループに最適化されるのでメモリ消費量が少なくなる
と、一般には言われます。
が、これは評価戦略によっては成り立たなくなります。
foldlとfoldr
リストの内容をある演算子によって畳み込む処理は、一般に fold というプログラミングパターンとして知られています。
例えば、
[a0,a1,a2,a3,a4,a5,a6]
というリストを、初項をzとして、<+>という演算子で畳み込みたいとします。
この場合、演算を右結合で行うか左結合で行うかで二通りの解釈が存在します。
左結合の場合、
(((((((z<+>a0)<+>a1)<+>a2)<+>a3)<+>a4)<+>a5)<+>a6) ... (*1)
となりますし、右結合の場合は
(a0<+>(a1<+>(a2<+>(a3<+>(a4<+>(a5<+>(a6<+>z))))))) ... (*2)
となります。
これを一般のリストについて再帰関数で記述すると、左結合の場合は
foldl :: (b -> a -> b) -> [a] -> b foldl (<+>) r [] = r foldl (<+>) r (x:xs) = foldl (<+>) (r<+>x) xs
右結合の場合は
foldr :: (a -> b -> b) -> [a] -> b foldr (<+>) z [] = z foldr (<+>) z (x:xs) = x <+> (foldr (<+>) z xs)
となります。
この、foldl, foldr を使って先の例を記述すると、(*1)は
result = foldl (<+>) z [a0,a1,a2,a3,a4,a5,a6]
(*2)は
result = foldr (<+>) z [a0,a1,a2,a3,a4,a5,a6]
と書けることがわかると思います。
foldlは末尾再帰
上のfoldlの定義を見ても分かるとおり、foldlは式の一番外側が自分自身の呼び出しになっているので、末尾再帰になります。
一方、foldrは自分自身を呼び出した後で演算をするので、末尾再帰にはなっていません。
ではここで、「遅延評価でない」通常の言語でfoldl(末尾再帰)を評価することを考えます。
定義通りに式を評価していくと……
result = foldl (<+>) z (a0:[a1,a2,a3,a4,a5,a6]) = foldl (<+>) (z <+>a0) (a1:[a2,a3,a4,a5,a6]) = foldl (<+>) b0 (a1:[a2,a3,a4,a5,a6]) = foldl (<+>) (b0<+>a1) (a2:[a3,a4,a5,a6]) = foldl (<+>) b1 (a2:[a3,a4,a5,a6]) = foldl (<+>) (b1<+>a2) (a3:[a4,a5,a6]) = foldl (<+>) b2 (a3:[a4,a5,a6]) = foldl (<+>) (b2<+>a3) (a4:[a5,a6]) = foldl (<+>) b3 (a4:[a5,a6]) = foldl (<+>) (b3<+>a4) (a5:[a6]) = foldl (<+>) b4 (a5:[a6]) = foldl (<+>) (b4<+>a5) (a6:[]) = foldl (<+>) b5 (a6:[]) = foldl (<+>) (b5<+>a6) [] = foldl (<+>) b6 [] = b6
というように、リストの頭から要素を取り出しつつ次々と左側に畳み込んでいきます。
このとき、
- 再帰の一段前のコンテキストは捨ててよい
- foldlの第2引数には常に演算の「結果」が入っている
という性質があります。
一方、foldrを評価すると、
result = foldr (<+>) z (a0:[a1,a2,a3,a4,a5,a6]) = a0<+>(foldr (<+>) z (a1:[a2,a3,a4,a5,a6])) = a0<+>(a1<+>(foldr (<+>) z (a2:[a3,a4,a5,a6]))) = a0<+>(a1<+>(a2<+>(foldr (<+>) z (a3:[a4,a5,a6])))) = a0<+>(a1<+>(a2<+>(a3<+>(foldr (<+>) z (a4:[a5,a6]))))) = a0<+>(a1<+>(a2<+>(a3<+>(a4<+>(foldr (<+>) z (a5:[a6])))))) = a0<+>(a1<+>(a2<+>(a3<+>(a4<+>(a5<+>(foldr (<+>) z (a6:[]))))))) = a0<+>(a1<+>(a2<+>(a3<+>(a4<+>(a5<+>(a6<+>(foldr (<+>) z []))))))) = a0<+>(a1<+>(a2<+>(a3<+>(a4<+>(a5<+>(a6<+>z)))))) = a0<+>(a1<+>(a2<+>(a3<+>(a4<+>(a5<+>c6))))) = a0<+>(a1<+>(a2<+>(a3<+>(a4<+>c5)))) = a0<+>(a1<+>(a2<+>(a3<+>c4))) = a0<+>(a1<+>(a2<+>c3)) = a0<+>(a1<+>c2) = a0<+>c1 = c0
というように、再帰を一段辿る度に式が組み上げられていき、リストを最後まで辿ったところで今度は順番に演算を消化していっていることがわかります。
この、「式を組み上げていく」ということがいわゆる「スタックを消費している」ことに相当します。
内部簡約と最外最左簡約
さて、前節でfoldlを評価する際に、
foldl (<+>) (z <+>a0) (a1:[a2,a3,a4,a5,a6]) = ... (*3) foldl (<+>) b0 (a1:[a2,a3,a4,a5,a6])
という計算(式変形)を行いました。しかし、上の式に対して適用できる式変形はこの一通りではありません。
foldlの定義から
foldl (<+>) (z <+>a0) (a1:[a2,a3,a4,a5,a6]) = foldl (<+>) ((z <+>a0)<+>a1) (a2:[a3,a4,a5,a6])
という展開も行えることがわかります。つまり、(*3)のような式を見たときに、内側の部分
foldl (<+>) (z <+>a0) (a1:[a2,a3,a4,a5,a6]) {- ~~~~~~~~~ -}
を先に簡約(計算)するという選択肢と、一番外側の部分
foldl (<+>) (z <+>a0) (a1:[a2,a3,a4,a5,a6]) {- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -}
を先に簡約(展開)するという選択肢の2通りの計算順序が存在することになります。
一般に、簡約できる箇所が複数存在するとき、前者のように内側を先に簡約する評価戦略を内部簡約、後者のように一番外側(の一番左)を先に簡約する評価戦略を最外最左簡約と呼んでいます。
OCamlや一般の手続き型言語では基本的に内部簡約、Haskellでは基本的に最外最左簡約で計算が行われます。
実は、この最外最左簡約というのが遅延評価の性質を持っているのです。
