[Haskell途中下車の旅] fold村散策(その1)
前回は一般的なループに使える until関数を紹介しましたが今回から複数回に渡りリストの要素を
順次処理していくループに使う fold系関数とその親戚達を紹介します。
foldl は二項演算関数と初期値とリストを引数に取り初期値からスタートし
リストの要素を順次二項演算していく(このような処理を「畳み込み」といいます)
関数です。
例えば
f が中置演算子のときの方がわかりやすいので f がプラス演算子 (+)、初期値が 0 の場合を書いてみましょう。
foldl f z xs の気分を手続き型言語で書くと
さて foldl では
それが foldr です。
ここでも f がプラス演算子 (+)、初期値が 0 の場合を書いてみましょう。
(ここで「気分」と書いたのには理由があります。詳しくは次回説明します)
foldl と foldr は map, filter と並ぶリスト処理の基本関数です。
Prelude(インポートしなくても最初から使えるライブラリモジュールのこと) の中で foldl と foldr を使って定義されている関数を探すと
次回は foldl と foldr の違い、特に無限リストに対するときの違いについて 説明します。
----
[註1]
実は ruby には inject という foldl にあたるメソッドがあり例えば sum xs は
例えば
foldl f z [x1,x2,x3,...,x_n]は
f (... (f (f (f z x1) x2) x3) ...) x_nという計算値になります。
f が中置演算子のときの方がわかりやすいので f がプラス演算子 (+)、初期値が 0 の場合を書いてみましょう。
(...(((0 + x1) + x2) + x3) ...) + x_nこれは [x1,x2,x3,...,x_n] の要素の合計ですからリストの合計関数 sum は
sum xs = foldl (+) 0 xsと書けることになります。
foldl f z xs の気分を手続き型言語で書くと
# ruby のコード[註1] y = z for x in xs y = f y x end return yといったところでしょう。
さて foldl では
f (... (f (f (f z x1) x2) x3) ...) x_nのようにリストの初めの要素ほど内側の括弧の中に入っていきましたがこれとは逆に
f x1 (f x2 (f x3 (... (f x_n z)...)))のように後ろの要素ほど内側の括弧の中に入っていく計算を作る畳み込み関数があります。
それが foldr です。
ここでも f がプラス演算子 (+)、初期値が 0 の場合を書いてみましょう。
x1 + (x2 + (x3 + (... (x_n + 0) ...)))foldl でのリストの要素を左(left)から順に処理していく「気分」とは逆に foldr ではリストの要素を右(right)から処理していく「気分」です。
(ここで「気分」と書いたのには理由があります。詳しくは次回説明します)
foldl と foldr は map, filter と並ぶリスト処理の基本関数です。
Prelude(インポートしなくても最初から使えるライブラリモジュールのこと) の中で foldl と foldr を使って定義されている関数を探すと
{- Prelude.hs より -} concat xss = foldr (++) [] xss reverse = foldl (flip (:)) [] and = foldr (&&) True or = foldr (||) False sum = foldl (+) 0 product = foldl (*) 1 maximum xs = foldl1 max xs minimum xs = foldl1 min xs unzip = foldr (\(a,b) ~(as,bs) -> (a:as,b:bs)) ([],[]) sequence = foldr mcons (return []) where mcons p q = p >>= \x -> q >>= \y -> return (x:y)などの有用な関数が並びます。 これを見ただけでもいかに foldl と foldr が基本的な関数かわかるでしょう。
次回は foldl と foldr の違い、特に無限リストに対するときの違いについて 説明します。
----
[註1]
実は ruby には inject という foldl にあたるメソッドがあり例えば sum xs は
xs.inject(0){|y,x| y + x}と書くことができます。 ruby1.9 ではさらに短く
xs.inject(0, &:+)と書けます。