# 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
```

も成り立つ。

```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 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`の定義からほとんど自明に導き出されることがわかる。

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

となっている。

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