Haskellで高階関数を組み合わせて部分文字列を作る例が全然わからなかったから考えた

最近、Haskellの勉強のために「<a href="http://www.amazon.co.jp/%E9%96%A2%E6%95%B0%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E5%AE%9F%E8%B7%B5%E5%85%A5%E9%96%80-%E2%94%80%E2%94%80%E7%B0%A1%E6%BD%94%E3%81%A7%E3%80%81%E6%AD%A3%E3%81%97%E3%81%84%E3%82%B3%E3%83%BC%E3%83%89%E3%82%92%E6%9B%B8%E3%81%8F%E3%81%9F%E3%82%81%E3%81%AB-WEB-PRESS-plus/dp/4774169269">関数プログラミング実践入門</a>」を読んでいる。
高階関数のところまでいったけど僕の頭がクソ雑魚だから例題が全然理解出来なかった…。
順番に読み解いていって理解しようと思う。

# 問題
本書のp.186では

```bash
*Main> segments "ABC"
["A","AB","ABC","B","BC","C"]
```

このように引数の部分文字列のリストが取り出せる関数、`segments`を扱っている。

この実装は以下のようになるそうだ。

```hs
segments :: [a] -> [[a]]
segments = foldr (++) [] . scanr (\a b -> [a] : map (a:) b) []
```

一見簡単そうに見えるが何をやっているのだろうか？　わからない。

# map関数とその使い方
まず、

```hs
map (a:) b
```

について考えてみよう。`map`関数のことは本で学んだ。試しに`map`関数の型を調べよう。
REPL上でこうすれば型がわかる。

```bash
*Main> :t map
map :: (a -> b) -> [a] -> [b]
```

`map`関数は関数とリストを引数にとって、リストの要素それぞれに関数を適用した結果をリストに並べて返す関数だ。

## リストの先頭への追加
`(:)`というのは何だ？これも本で学んだ。リストの先頭に要素を追加する関数だ。だから

```bash
*Main> 1 : [2,3,4]
[1,2,3,4]
```

となる。

## mapを使う

さて、`map`の第2引数はリストでなければならない。更にそのリストの要素はリストでなければ、`:`によるリストへの追加操作が行えない。ということは、`map`と組み合わせて使うには以下のようにすればよい。

```bash
*Main> map (1:) [[2,3,4], [5,6]]
[[1,2,3,4], [1,5,6]]
```

わかった。

## ラムダ関数
じゃあこれはなんだ。

```hs
(\a b -> [a] : map (a:) b)
```

これは知っている。ラムダ関数だ。aとbを引数に取って`[a] : map (a:) b`を返す名前が無い関数だ。
`[a] : map (a:) b`というのは`map`から帰ってくるリストの先頭に、`a`をリストで包んだ`[a]`を追加する操作になる。
ということは、

```bash
*Main> (\a b -> [a] : map (a:) b) 1 [[2,3,4], [5,6]]
[[1],[1,2,3,4],[1,5,6]]
```

こうなる。これはさっき`map (1:) [[2,3,4], [5,6]]`とした結果の先頭に`[1]`を追加したものだ。
わかった。

# 畳み込みscanr, foldr
次に

```hs
scanr (\a b -> [a] : map (a:) b) []
```

これについて考えよう。まず、`scanr`の型を調べてみる。

```bash
*Main> :t scanr
scanr :: (a -> b -> b) -> b -> [a] -> [b]
```

「2引数を取る関数」、「値」、「リスト」の3つの引数を取り、リストを返す関数だ。このとき、

```hs
scanr f b [a_1, ..., a_n]
```

は
`[f a_1 (f a_2 f(...))..., ... , f a_{n-2} (f a_{n-1} (f b a_n)), f a_{n-1} (f b a_n), f b a_n, b]`
という感じのリストを返す。
こういった計算を畳み込み(fold)というらしい。図で表すとこんな感じ。
![scanr.png](https://qiita-image-store.s3.amazonaws.com/0/29029/585b3dcf-97ee-57be-1c4c-e9f0185f24b2.png)

`b`は初期値で、その後リストの中身を順番に`ｆ`に適用していく。初期値`b`や、リストの右のほうにある値(`a_n`とか)には何重にも`f`が作用することがわかる。
ちなみに、`scanr f b [a_1, ..., a_n]`の結果リストの先頭要素だけ返す関数が`foldr`である。

`scanr`についてはわかった。そうすると、下の結果もわかりそうだ。

```bash
scanr (\a b -> [a] : map (a:) b) [] "ABC"
```

いや、ちょっと待った。引数がリストじゃなくて文字列に見える。`scanr`の第3引数はリストのはずだったのに、困ってしまう。
でも大丈夫。`"ABC"`の型を見てみよう。

```bash
*Main> :t "ABC"
[Char]
```
なるほど。文字列とは文字のリストだったか。つまり`"ABC" = ['A', 'B', 'C']`ってこと。わかった。

じゃあ`scanr (\a b -> [a] : map (a:) b) [] "ABC"`で得られるリストの最後尾から逆順に考えていこう。計算？の過程は以下になる。

```hs
[]
['C'] : map 'C': [] = ['C'] : [] = [['C']] = ["C"]
['B'] : map 'B': [['C']] = ['B'] : [['B', 'C']] = [['B'], ['B', 'C']] = ["B", "BC"]
['A'] : map 'A': [['B'], ['B', 'C']] = ['A'] : [['A', 'B'], ['A', 'B', 'C']] = [['A'], ['A', 'B'], ['A', 'B', 'C']] = ["A", "AB", "ABC"]
```

ということで、

```bash
*Main> scanr (\a b -> [a] : map (a:) b) [] "ABC"
[["A", "AB", "ABC"], ["B", "BC"], ["C"], []]
```
となることがわかった。

# 部分適用
ちなみに、`segments`関数では

```hs
scanr (\a b -> [a] : map (a:) b) []
```
となっていて、`scanr`の引数が2個しかない。これは3つうちの2つの引数を部分適用することで、引数が1つの関数を新たに生み出しているのだ。Haskellの関数はカリー化されているからこういうことができる。これは後の関数の合成のために一役買っている。

# 関数の合成
さて、最初の`segments`の実装を見直そう。

```hs
segments :: [a] -> [[a]]
segments = foldr (++) [] . scanr (\a b -> [a] : map (a:) b) []
```
まだ触ってないところでまず気になるのが、`.`ドットだ。これは関数の合成を表す。
`f`、`g`が関数のとき、`f . g`は`\x -> f( g x )`と同じということらしい。
だから、`segments = \x -> foldr (++) [] ( scanr (\a b -> [a] : map (a:) b) [] x )`と考えればいい。

`(++)`は2つのリストを結合する関数だ。`foldr (++) [] [リスト]`は`[]`を初期値として順番にリストの中のリストを結合していった最終結果を返す。
だから、

```bash
*Main> foldr (++) [] . scanr (\a b -> [a] : map (a:) b) [] "ABC"
["A","AB","ABC","B","BC","C"]
```
となるのだ。
これで`segments`の実装の意味がはっきりとわかった。

# おわりに
慣れればすぐに読み解けるようになるのだろうか？僕はとてもそうは思わない。でも頑張りますから。