top page > computer > haskell > web_lecture > for_programmer > fold_left.html
更新日:
文責: 重城良国

たたみこみ(左)

結合則

x `op` (y `op` z) == (x `op` y) `op` z

すべてのx, y, zについてうえの式が成り立てば演算子`op`は結合則を満たす。足し算やかけ算がそうだ。

x + (y + z) == (x + y) + z
x * (y * z) == (x * y) * z

引き算やわり算は結合則を満たさない。(/=)は不等式を表す。

x - (y - z) /= (x - y) - z
x / (y / z) /= (x / y) / z

左結合での計算

足し算は結合則を満たすのでリストの要素の総和は右結合でも左結合でも計算できる。

5 + (3 + (7 + 2)) == ((5 + 3) + 7) + 2

蓄積変数

リスト[5, 3, 7, 2]を考える。右結合でなら[3, 7, 2]の総和を誰かに頼みそれに5を足す。左結合での演算ではそうはいかない。[3, 7, 2]というリストだけをもらっても次の人は何もできない。そこで5と[3, 7, 2]とを次の人にわたす。その人はもらった5と3を足して8にして8と[7, 2]を次の人にわたす。その人は8と7を足した15と[2]を次の人にわたす。17と[]がわたされた人は17を結果として返す。右結合での計算ではリストだけをわたすが、左結合での計算ではリスト以外に5, 8, 15, 17と変化する変数をわたす必要がある。この変数は演算の結果をためていくので蓄積変数と呼ぶ。

左結合の総和

sumIter :: Integer -> [Integer] -> Integer
sumIter s [] = s
sumIter s (x : xs) = sumIter (s + x) xs

例では5と[3, 7, 2]をわけて蓄積変数の初期値を5とした。これだと空リストに対して定義できない。初期値を0として0と[5, 3, 7, 2]をわたすやりかたのほうが良い。

sumIter 0 [5, 3, 7, 2]
-> sumIter (0 + 5) [3, 7, 2]
-> sumIter ((0 + 5) + 3) [7, 2]
-> sumIter (((0 + 5) + 3) + 7) [2]
-> sumIter ((((0 + 5) + 3) + 7) + 2) []
-> (((0 + 5) + 3) + 7) + 2
-> 17

mySumをsumIterを使って定義する。

mySum = sumIter 0

反復的処理

以下のような置き換えとなっている。

sumIter s (x : xs) -> sumIter (s + x) xs

それぞれの引数を以下のように変化させて同じ関数に与えている。

蓄積含数: s -> s + x
リスト: x : xs -> xs

蓄積変数にx足してリストの先頭の要素をけずる操作のループだ。このような処理を反復的処理と呼ぶ。Schemeでいう末尾再帰だ。

再帰的処理

右結合のほうはどうだろうか。

mySum (x : xs) = x + mySum xs

単純に引数だけを変化させた形ではない。関数mysumの実行のあとにxを足している。単純なループではない。このような処理を再帰的処理と呼ぶ。

関数foldl

左からのたたみこみを抽象化した関数がある。関数foldlは演算子(関数)と蓄積変数の初期値とリストをとりたたみこみの結果を返す。

使いかた

% ghci
Prelude> foldl (+) 0 [5, 3, 7, 2]
17

定義

myFoldl _ s [] = s
myFoldl op s (x : xs) = myFoldl op (s `op` x) xs

蓄積変数sをs `op` xに更新してリストからはxを削る。これを同じ関数に与える。ループとなる。リストが空ならそのときの蓄積変数の値が全体の値となる。

蓄積変数の型は結果の値と同じ型だ。その型はopの第1引数の型でもあり返り値の型でもある。定義をよく見て、蓄積変数sがopの第1引数となっていること、関数myFoldlの蓄積変数の場所にs `op` xが置かれていることを確認する。opの第2引数の型はリストの要素の型と同じだ。

myFoldl :: (a -> b -> a) -> a -> [b] -> a

空間効率

今回定義したmySumは右結合のものも左結合のものも空間効率は悪い。遅延評価なので足し算は必要とされるまで行われない。つまり右結合であればx1 + (x2 + (x3 + ...))のような形に左結合であれば(..((x1 + x2) + x3) + ...)のような形に一度完全に展開されてそれから足し算が評価される。

正格評価

右結合のほうはどうしようもない。しかし左結合のほうはちょっとした変更で空間効率を改善できる。以下のような形で展開が行われるsumIter'を考える。

sumIter' 0 [5, 3, 7, 2]
sumIter' 5 [3, 7, 2]
sumIter' 8 [7, 2]
sumIter' 15 [2]
sumIter' 17 []
17

これなら空間効率はO(1)だ。引数の評価を先に行うことを「正格評価」と呼ぶ。正格評価についてはここでは説明しない。このような形でたたみこみを行う関数foldl'が用意されている。

使いわけ

今まで挙げてきた例はすべてfoldl'で書いたほうが良い。足し算やかけ算ではいずれにしても値を求めるのにリストすべての値が必要だからだ。foldrが威力を発揮するのは途中で計算がやめられるような場合だ。foldrならば無限リストを扱うこともできる。

自分用のメモ
foldl op v xs = foldr (\x k -> \y -> k $ y `op` x) id xs v
foldl' op v xs = foldr (\x k -> \y -> k $! y `op` x) id xs v

「たたみこみ(右)」へもどる 「ポーランド記法電卓」へ

正当なCSSです! HTML5 Powered with CSS3 / styling, and Semantics