[Haskell途中下車の旅] fold村散策(その1)

|
前回は一般的なループに使える until関数を紹介しましたが今回から複数回に渡りリストの要素を 順次処理していくループに使う fold系関数とその親戚達を紹介します。
foldl は二項演算関数と初期値とリストを引数に取り初期値からスタートし リストの要素を順次二項演算していく(このような処理を「畳み込み」といいます) 関数です。
例えば
  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, &:+)
と書けます。

このブログ記事について

ひとつ前のブログ記事は「「仕様策定の意図を伝えることの難しさ」 JBF第29回研究会の感想」です。

次のブログ記事は「制約プログラミングは使われているか:スケジューリング・シンポジウム2008に参加して」です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。