もっと fold を使おう

Haskell

関数型言語というと「ループじゃなくて再帰」というイメージが強くて，実際自分も最初の頃はそう思い込んでいたけど，
実際には fold 等の高階関数を使うほうが多いよという話と，それに関連して foldl と foldr の違いの話．


Prelude に様々なリスト操作関数が定義されてるが，その多くは fold さえあれば自分で再帰しなくても書ける．

map f = foldr ((:) . f) []

(++) = flip (foldr (:))

filter f = foldr (\a b -> if f a then a:b else b) []

length = foldr (const (+1)) 0

reverse = foldl (flip (:)) []

and = foldr (&&) True

or = foldr (||) False

all f = foldr ((&&) . f) True

any f = foldr ((||) . f) False

maximum = foldl1 max

minimum = foldl1 min

concat = foldl (++) []

f がちゃんと停止する関数なら fold f a xs も必ず停止する*1ことや，
自分で再帰で書くよりたいていの場合において読み易いことなどの理由で fold が使えるなら使ったほうがいいと俺は思っている．


Haskell には foldr と foldl の2種類があり，その違いについても少し触れておく．
上で挙げた中では例えば length や and は foldr でも foldl でも変わらないように思える．
しかし，実は and, or, all, any に関しては foldr と foldl の場合で結果が異なる場合がある．

andr = foldr (&&) True
andl = foldl (&&) True
ls = False:[True, True, ..]

とすると，

andr ls

の計算は停止して False を返すが，

andl ls

の計算は停止しない．


foldr と foldl はこのように定義されている．

foldr k z xs = go xs
  where
    go []     = z
    go (y:ys) = y `k` go ys

foldl f z0 xs0 = lgo z0 xs0
  where
    lgo z []     =  z
    lgo z (x:xs) = lgo (f z x) xs

andr をこの定義に従って書き下してみると，

andr ls = False && go [True, True, ..]
        = False

であるが，

andl ls = lgo (True && False) [True, True, ..]
        = lgo False [True, True, ..]
        = lgo (True && False) [True, True, ..]
        = ...

となって，たしかに停止しないことがわかる．


このようなことから foldr のほうが理想上は好ましいことが多いのだが，foldr は末尾再帰になっていないため，foldl に比べて非効率的な面もある．
したがって，場合によって foldl と foldr (と Data.List の foldl') をちゃんと使い分ける必要がある．
実は foldr も foldl も foldMap で定義できるのだが，そのへんは 第34回 様々なデータ構造でfoldを使えるようにするFoldableクラス | 日経 xTECH（クロステック） が参考になる．

参考

*1:xs が無限リストの場合はこの限りでない