関数合成を機械的に扱う試み

引数が複数ある時の関数合成は直感的な理解が困難です。あまり理解は追及しないで、機械的な式変形や解釈を試みました。

※ ちょっとした思い付きのようなもののため、どのような場面で有用なのかは未検証です。

この記事は[Haskell 超入門](http://qiita.com/7shi/items/145f1234f8ec2af923ef)シリーズの番外編です。

【追記 2016.7.1】似たような記事を見付けました。相互に独立ですが、観察すれば似たようなことに気付くのだと思いました。

* @necojackarc [ポイントフリースタイルへの道 〜最大公約数編〜](http://qiita.com/necojackarc/items/1bccc9643857d3ce7896) 2015.7.3

【追記 2016.7.1】同じテーマを扱った記事です。

* @etoilevi [Haskellの関数合成、または (.) 関数](http://qiita.com/etoilevi/items/abd6c0063eae11a43237) 2015.6.13

# 関数合成を進める

1引数の関数合成は簡単ですが、多引数に拡張できる形での式変形を導入します。

```hs:型
f :: a -> a
g :: a -> a
```

`$`→`.`の書き換えでは、引数を括弧の外に出します。括弧がなければ式を囲みます。

* `f $ g x` → `(f $ g x)` → `(f . g) x`

`$`が足りない時は、中置演算子をセクションで分断して`$`を挟みます。

* `1 + 1` → `(1 +) $ 1`
* `(f . g) x` → `((f .) $ g) x`

## 2引数

gの引数を増やします。

```hs:型
f :: a -> a
g :: a -> a -> a
```

`$`→`.`の書き換えでは、最後の引数を括弧の外に出します。`$`が足りなければ水増しします。

1. `f $ g x y`
2. 式を括弧で囲む: `(f $ g x y)`
3. `$`→`.`: `(f . g x) y`
4. `$`を水増し: `((f .) $ g x) y`
5. `$`→`.`: `((f .) . g) x y`

## 3引数

gの引数を増やします。

```hs:型
f :: a -> a
g :: a -> a -> a -> a
```

1. `f $ g x y z`
2. 式を括弧で囲む: `(f $ g x y z)`
3. `$`→`.`: `(f . g x y) z`
4. `$`を水増し: `((f .) $ g x y) z`
5. `$`→`.`: `((f .) . g x) y z`
6. `$`を水増し: `(((f .) .) $ g x) y z`
7. `$`→`.`: `(((f .) .) . g) x y z`

## モナド則3の右辺

少し違うパターンです。ラムダ式の部分を関数合成で書き換えます。

1. `m >>= (\x -> f x >>= g)`
2. `$`を水増し: `m >>= (\x -> (>>= g) $ f x)`
3. 式を括弧で囲む: `m >>= (\x -> ((>>= g) $ f x))`
4. `$`→`.`: `m >>= (\x -> ((>>= g) . f) x)`
5. ポイントフリースタイル: `m >>= ((>>= g) . f)`

モナド則については、次の記事が参考になるかもしれません。

* [@7shi](https://twitter.com/7shi): [Haskell - モナド則がちょっと分かった？ - Qiita](http://qiita.com/7shi/items/547b6137d7a3c482fe68) 2014.12.1

# 関数合成を外す

逆方向の式変形です。1引数の場合から見ます。

```hs:型
f :: a -> a
g :: a -> a
```

`.`→`$`の書き換えでは、引数を括弧の中に入れます。引数を適用するたびに合成が解除されると解釈できます。

* `(f . g) x` → `(f $ g x)`

セクションの後の`$`は外して、引数をセクションに適用します。

* `(1 +) $ 1` → `(1 + 1)`
* `((f .) $ g) x` → `((f . g)) x`

無駄な括弧があれば整理します。

* `(f $ g x)` → `f $ g x`
* `(1 + 1)` → `1 + 1`
* `((f . g)) x` → `(f . g) x`

## 2引数

gの引数を増やします。

```hs:型
f :: a -> a
g :: a -> a -> a
```

`.`→`$`の書き換えは右から行います。最初の引数を括弧の中に入れます。

1. `((f .) . g) x y`
2. `.`→`$`（右から）: `((f .) $ g x) y`
3. セクションに適用: `((f . g x)) y`
4. `.`→`$`: `((f $ g x y))`
5. 括弧を整理: `f $ g x y`

## 3引数

gの引数を増やします。

```hs:型
f :: a -> a
g :: a -> a -> a -> a
```

1. `(((f .) .) . g) x y z`
2. `.`→`$`（右から）: `(((f .) .) $ g x) y z`
3. セクションに適用: `(((f .) . g x)) y z`
4. `.`→`$`（右から）: `(((f .) $ g x y)) z`
5. セクションに適用: `(((f . g x y))) z`
6. `.`→`$`: `(((f $ g x y z)))`
7. 括弧を整理: `f $ g x y z`

## 引数不足

`.`→`$`の書き換え時に引数が足りないときは、式をラムダ式で包んで引数を補います。既にラムダ式で包まれていれば、引数は後ろに追加します。

1. `((f .) .) . g`
2. ラムダ式化して引数を補う: `\x -> (((f .) .) . g) x`
3. `.`→`$`（右から）: `\x -> (((f .) .) $ g x)`
4. セクションに適用: `\x -> (((f .) . g x))`
5. 引数を追加: `\x y -> (((f .) . g x)) y`
6. `.`→`$`（右から）: `\x y -> (((f .) $ g x y))`
7. セクションに適用: `\x y -> (((f . g x y)))`
8. 引数を追加: `\x y z -> (((f . g x y))) z`
9. `.`→`$`: `\x y z -> (((f $ g x y z)))`
10. 括弧を整理: `\x y z -> f $ g x y z`

`.`の数だけ引数が出て来ました。

## モナド則3の右辺

上で書き換えたものを元に戻します。

1. `m >>= ((>>= g) . f)`
2. ラムダ式化して引数を補う: `m >>= (\x -> ((>>= g) . f) x)`
3. `.`→`$`: `m >>= (\x -> ((>>= g) $ f x))`
4. セクションに適用: `m >>= (\x -> ((f x >>= g)))`
5. 括弧を整理: `m >>= (\x -> f x >>= g)`

# 関数合成の解釈

関数合成がネストしているとどう解釈して良いのか戸惑います。意味の把握は難しいですが、先ほど示した式変形に沿えば、計算の流れを追うことはできます。

引数を適用するたびに合成が解除されて、計算が内部に移動します。式変形をしないで、適用の流れだけを追うイメージです。

![apply.png](https://qiita-image-store.s3.amazonaws.com/0/32057/af4f481b-6870-4893-04be-730aee7d9f9c.png)

1. 引数を適用: `(((f .) .) $ g x) y z`
2. セクションに適用: `(((f .) . g x)) y z`
3. 引数を適用: `(((f .) $ g x y)) z`
4. セクションに適用: `(((f . g x y))) z`
5. 引数を適用: `(((f $ g x y z)))`

## モナド則3の右辺（関数合成版）

式変形せずに計算の流れを追います。

![monad3.png](https://qiita-image-store.s3.amazonaws.com/0/32057/c3504f8a-55e3-0b91-1cdd-40db41d6a855.png)

1. `m`から値を取り出して`f`に適用: `((>>= g) . (m >>= f))`
2. `f`の戻り値をセクションに適用: `(((m >>= f) >>= g))`
3. `g`に適用: `(m >>= f) >>= g`

計算過程を式変形で表現した結果、モナド則3の左辺に一致しました。