Thinking Functionally with Haskell勉強メモ: 第６章３ foldlとscanl

foldl関数

foldrに似たfoldl関数を定義したい。挙動は以下のとおり（@は任意の演算子）：

foldr (@) e [a, b, ... y, z] = (a @ (b @ ... (y @ (z @ e))))

foldl (@) e [a, b, ... y, z] = (( ... ((e @ a) @ b) ... @ y) @ z)

lisp系やpythonでいうところのreduce。定義は：

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f e [] = e
foldl f e (x:xs) = foldl f (f e x) xs

これを使うと例えば

reverse = foldl (flip (:)) []

と簡潔かつ効率良くかける。

foldlとfoldrの関係：

foldl f e xs = foldr (flip f) e (reverse xs)
foldr f e xs = foldl (flip f) e (reverse xs)

そしてもしxsが有限リストで

(x <> y) @ z = x <> (y @ z)
e @ x = x <> e

が成り立つなら：

foldl (@) e xs = foldr (<>) e xs

も成り立つ。

一例として、(@) = (<>) = (++)でe = []で：

concat xss = foldl (++) [] xss = foldr (++) [] xss

となる。あくまで有限リストの場合のみ。

scanl関数

scanlはClojureでいうところのreductions。

scanl (+) 0 [1..10] = [0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55]

と、foldlの途中経過をリストとして返す。

scanl :: (b -> a -> b) -> b -> [a] -> [b]
scanl f e = map (foldl f e) . inits

inits :: [a] -> [[a]]
inits [] = [[]]
inits (x:xs) = [] : (map (x:) (inits xs))

と定義できる。

initsがなかなか直感的に理解しにくかった。試しに適当に引数をいれて式を展開してみる：

inits [] = [[]]

inits [3] = [] : (map (3:) (inits []))
          = [] : (map (3:) [[]])
          = [] : [[3]]
          = [[], [3]]

inits [2, 3] = [] : (map (2:) (inits [3]))
          = [] : (map (2:) [[], [3]])
          = [] : [[2], [2, 3]]
          = [[], [2], [2, 3]]

inits [1, 2, 3] = [] : (map (1:) (inits [2, 3]))
                = [] : (map (1:) [[], [2], [2, 3]])
                = [] : [[1], [1, 2], [1, 2, 3]]
                = [[], [1], [1, 2], [1, 2, 3]]

これにmap (foldl f e)すればいい、というのはわかりやすい。

さて、上記のscanlの定義は算出する値という意味では正しいのだが、非常に非効率（O(）。

効率化のために、同値であることが証明できる式変換を行う。

数独ソルバーの時は「こういう形にしたい」という式を思い浮かべて、原型からその形に向かって式変換をしていった。今回はそうではなく、帰納法で式転換をしていって、よさげな式に変形できれば成功とする。

Case []

scanl f e []

= {scanlの定義}
map (foldl f e) (inits [])

= {initsの定義}
map (foldl f e) [[]]

= {foldl f e [] = e}
[e]

Case x:xs

scanl f e (x:xs)

= {scanlの定義}
map (foldl f e) (inits (x:xs))

= {initsの定義}
map (foldl f e) ([] : (map (x:) (inits xs)))

= {map f x:xs = (f x) : map f xs}
(foldl f e []) : map (foldl f e) (map (x:) (inits xs))

= {(foldl f e []) = e}
e : map (foldl f e) (map (x:) (inits xs))

= {functor law of map}
e : map ((foldl f e) . (x:)) (inits xs))

= {(foldl f e) . (a:) = (foldl f (f e a)) (後で証明する)}
e : map (foldl f (f e x)) (inits xs)

= {scanlの定義}
e : scanl f e (f e x) xs

二つの結果を合わせるとscanlの定義は：

scanl f e [] = [e]
scanl f e (x:xs) = e : scanl f e (f e x) xs

となる。これでO(n)になった。

(foldl f e) . (a:) = (foldl f (f e a))の証明：

Case []

foldl f e [a]

= {foldlの定義}
foldl f (f e a) []

Case x:xs

foldl f e (a:x:xs)

= {foldlの定義}
foldl f (f e a) (x:xs)

foldlの定義からほとんど自明に導き出されることがわかる。

実際のpreludeのscanlの定義はもう一手間かかっていて：

scanl f e xs = e : (case xs of
                      [] -> []
                      x:xs -> scanl f (f e x) xs)

となっている。

この定義だとscanl f e undefinedがundefinedではなくe:undefinedを返す。