Thinking Functionally with Haskell勉強メモ: 第6章3 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
を返す。