(>>=) を (>=>) に書き換える

[綱渡りと Category (と，Kleisli)](http://qiita.com/CyLomw/items/ff1e5d1600291c952c5e "綱渡りと Category (と，Kleisli)") ← 前の記事

今回は少しカテゴリーの話から離れて，モナドの bind 演算子 `(>>=)` を `(>=>)` に書き換えることを考えてみます．

次の記事 → [Category から Arrow へ](http://qiita.com/CyLomw/items/688942f19a5bc3a25037 "Category から Arrow へ")

# `(>>=)` と `(>=>)`

## `(>>=)`

```hs
(>>=) :: Monad m => m a -> (a -> m b) -> m b
```

おなじみ bind 演算子です．この演算子は「モナド値」と「普通の値をとってモナド値を返す函数」をとります．


```hs:ghci
ghci> Just 3 >>= \x -> Just (x * 2)
Just 6

ghci> [10, 20, 30] >>= \x -> [x, -x]
[10,-10,20,-20,30,-30]

ghci> return "Hello, World!" >>= print
"Hello, World!"
```

また逆向きの `(=<<)` も存在します．

```hs
(=<<) :: Monad m => (a -> m b) -> m a -> m b
(=<<) = flip (>>=)
```

## `(>=>)`

この演算子は `Control.Monad` モジュール内で定義されています．

```hs:Control.Monad
-- | Left-to-right Kleisli composition of monads.
(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c)
f >=> g = \x -> f x >>= g
```

ここで一つ注意ですが，
`\x -> f x >>= g` は `\x -> (f x >>= g)` であって `(\x -> f x) >>= g` とはなりません．
わかりやすくするため以降はなるべく括弧をつけていきます．

さて，`(>=>)` は「普通の値をとってモナド値を返す函数」を二つとり合成します．

```hs:ghci
ghci> :module Control.Monad

ghci> (\x -> Just (x * 3)) >=> (\x -> Just (x + 3)) $ 10
Just 33

ghci> (\x -> [x - 1, x + 1]) >=> (\x -> [show x, reverse (show x)]) $ 25
["24","42","26","62"]

ghci> Data.List.inits >=> Data.List.group $ "Hello!"
["H","H","e","H","e","l","H","e","ll","H","e","ll","o","H","e","ll","o","!"]

ghci> const getLine >=> (return . reverse) >=> print $ ()
Is the order a rabbit?
"?tibbar a redro eht sI"
```

また逆向きの `(<=<)` も存在します．

```hs:Control.Monad
-- | Right-to-left Kleisli composition of monads. @('>=>')@, with the arguments flipped
(<=<) :: Monad m => (b -> m c) -> (a -> m b) -> (a -> m c)
(<=<) = flip (>=>)
```


## `(>>=)` を `(>=>)` に書き換える

定義に従って， `f >=> g` は `\x -> (f x >>= g)` と書き直すことができます．
では，逆に `(>>=)` を `(>=>)` を使って書き直すことはできるか考えてみます．

# 初級

## 定義通りの場合

```hs
\x -> (Just (x * 3) >>= \y -> Just (y * 2))
```

まず，`Just (x * 3)` は `(Just . (*3)) x` と書き換えられます．

```hs
\x -> ((Just . (*3)) x >>= \y -> Just (y * 2))
```
 
これはちょうど `(>=>)` の定義の形になっているので，次のように書き換えられます．

```hs
(Just . (*3)) >=> (\y -> Just (y * 2))
```

`\y -> Just (y * 2)` も `Just . (*2)` と書き換えられるので次のようにも書けます．

```hs
(Just . (*3)) >=> (Just . (*2))
```

## `x` が現れない場合

```hs
\x -> (Just 3 >>= \y -> Just (y * 2))
```

似たような例ですが，`Just x` の部分が `Just 3` になってしまっています．
そのため，まず `Just 3` を `(\_ -> Just 3) x` と変形してみます．

```hs
\x -> ((\_ -> Just 3) x >>= \y -> Just (y * 2))
```

これで `(>=>)` の定義の形に持ち込むことができたので，次のようになります．

```hs
(\_ -> Just 3) >=> (\y -> Just (y * 2))
```

`\y -> Just (y * 2)` は `Just . (*2)` と書き換えられます．
また，`(\_ -> Just 3)` は `const (Just 3)` とも書けます[^1]．よって次のようになります．

```hs
const (Just 3) >=> (Just . (*2))
```

# 中級

## `x` が後ろまで現れる場合

```hs
\x -> (Just (x * 2) >>= \y -> Just (y * x))
```

初級の問題と同じように `(>=>)` の定義の形そのままに見えるので，次のように書き換えてみます．

```hs
(Just . (*2)) >=> (\y -> Just (y * x))
```

でもこれってどこかおかしくないでしょうか．
`x` と `y` はあくまでラムダ式 `\x`, `\y` の仮引数だったのに，`\x` が消えた後まで `x` が残ってしまっています．

実はこのような例は簡単には `(>=>)` で書き換えることができません．

`(>=>)` は二つの函数を結合するため，
`(一つ目の函数) >=> (二つ目の函数)`
という形をとります．

そのため，一つ目の函数の引数は二つ目の函数からは見えません．

しかし，`Just (x * 2) >>= \y -> Just (y * x)` の例では二つ目の函数となるはずの `\y -> Just (y * x)` が一つ目の函数の引数 `x` を使ってしまっているのです．


## どうする

- アプローチ 1: ラムダ式で保持

ラムダ式が消えてしまったのが問題であるならば，ラムダ式を残すようにすればいい．

`\x -> ((一つ目の函数) >=> (二つ目の函数))`

みたいな感じでいけそうな気がします．

- アプローチ 2: タプルで保持

問題は，二つ目の函数から一つ目の函数の引数が見えないということでした．
しかし，二つ目の函数から一つ目の函数の引数が見えないのであれば，一つ目の関数が二つ目の函数に自分の引数を教えてあげればよいのです．

即ち，一つ目の函数が，結果と一緒に自分の引数も返してあげればよい，ということになります．

例えば一つ目の函数が `\x -> Just (x * 2)` であるとするならば，これを `\x -> (Just (x * 2), x)` のようにしてあげればいい……いや，`(>=>)` で合成できるのは「普通の値をとってモナド値を返す函数」でした．従って，`\x -> Just (2 * x, x)` としてあげるのがよいでしょう．

## アプローチ 1

まず，函数合成を使うと問題の式は次のように書き換えられます．

```hs
\x -> ( (Just . (*2)) x >>= (Just . (*x)) )
```

見やすくするために，`f = Just . (*2)`，`g = Just . (*x)` とおくと

```hs
\x -> (f x >>= g)
```

となります．ただし注意してください，`g` は内部に `x` を持っています[^2]．(だから `(>=>)` に書き換えられないのでした．)

さて，`f x >>= g` の部分だけを取り出して考えます．

値 `v` を `(\t -> v) ()` と書き換える要領で，この部分は下のように書き換えられます．

```hs
(\y -> (f x >>= g)) ()
```

さらに `f x` は `(\_ -> f x) y`，と書きかえることができ，これは `const (f x) y` とも書くことができます．



よって

```hs
(\y -> (const (f x) y >>= g)) ()
```

前半部分は `(>=>)` の定義の形になっているので，次のように書き換えられます．

```hs
(const (f x) >=> g) ()
```

よって，問題の式は次のようになりました．

```hs
\x -> ( (const (f x) >=> g) () )
```

`f`, `g` を元に戻すと次のようになります．

```hs
\x -> ( (const ((Just . (*2)) x) >=> (Just . (*x))) () )
```

これ以上いじるのは難しそうです．

`(>>=)` から `(>=>)` へ書き換えることはできましたが，きれいに `(一つ目の函数) >=> (二つ目の函数)` の形にはなりませんでした．



## タプル操作関数

アプローチ 2 ではタプルをいじっていくので，ここでちょっと脱線してタプルを操作する函数をいくつか作っておきます．

### ペア[^3]の要素を入れ替えたペアを返す `swap`

```hs
swap :: (b, c) -> (c, b)
swap (x, y) = (y, x)
```

`swap` 函数は `Data.Tuple` モジュール内で定義されているのでそれを使ってもいいです．

### ペアの一番目の要素にのみ函数を適用する函数 `first`

```hs
first :: (b -> c) -> (b, d) -> (c, d)
first f (x, y) = (f x, y)
```

### ペアの二番目の要素にのみ函数を適用する函数 `second`

ちょっとまわりくどいですが，`second` は次のように `swap` と `first` を利用して作ることができます．

```hs
second :: (b -> c) -> (d, b) -> (d, c)
second f = swap . first f . swap
```

### ペアの一番目，二番目の要素にそれぞれ異なる函数を適用する函数 `(***)`

```hs
(***) :: (b -> c) -> (b' -> c') -> (b, b') -> (c, c')
f *** g = second g . first f
```

この函数 (演算子) は次のように動きます．

```hs:ghci
ghci> (*10) *** (+10) $ (2, 3)
(20,13)

ghci> Just *** id $ (2, 3)
(Just 2,3)
```

![prod.png](https://qiita-image-store.s3.amazonaws.com/0/64300/89284b11-ea90-fb1d-6f65-35dcf4cfefbc.png)

### 一つの値に二つの函数 `f`, `g` を適用した結果をペアで返す函数 `(&&&)`

```
(&&&) :: (b -> c) -> (b -> c') -> b -> (c, c')
f &&& g = (f *** g) . (\x -> (x, x))
```

引数を複製して片方には `f`, 片方には `g` を適用する，という感じです．

```hs:ghci
ghci> (*10) &&& (+10) $ 2
(20,12)

ghci> Just &&& id $ 3
(Just 3,3)
```

![dup.png](https://qiita-image-store.s3.amazonaws.com/0/64300/3439c4d6-f433-141c-2f5c-0e057767e8e3.png)

## アプローチ 2

もう一度先ほどの問題を見てみます．

```hs
\x -> (Just (x * 2) >>= \y -> Just (y * x))
```

函数合成を使うと次のように書き換えられます．

```hs
\x -> ( (Just . (*2)) x >>= (Just . (*x)) )
```

見やすくするために `f = Just . (*2)`, `g = Just . (*x)` とおくと，

```hs
\x -> (f x >>= g)
```

となります．繰り返しになりますが，`g` は内部に `x` を持っているためそのまま `(>=>)` に書き換えることはできません．

まず一つ目の函数 `f` を，結果と一緒に自分の引数を返すような函数 `f'` に書き換えてみましょう．

![img1.png](https://qiita-image-store.s3.amazonaws.com/0/64300/0b935b5f-6440-6d77-f630-592271511340.png)

このような函数は，先ほど定義した `(&&&)` 函数を用いることで書くことができます．

よって

![img2.png](https://qiita-image-store.s3.amazonaws.com/0/64300/36185d21-d412-e87f-af73-d00ab48cc456.png)

これより，

```hs
f' = Just . ((*2) &&& id)
```

と書けることがわかりました．

さて，函数 `f' :: Num t => t -> Maybe (t, t)` はタプル (モナドに包まれたタプル) を返すので，`g` の方もタプルを受け取る函数 `g'` に書き換える必要があります．

`f' = Just . (*2) &&& id` より，`f'` が返すタプルの一番目の値が「結果」，二番目の値が「引数をそのまま返したもの」です．

よって `g'` は次のようにします．

```hs
g' = \(y, x) -> Just (y * x)
```

これは，函数 `uncurry` を用いて次のように書き換えられます[^4]．

```hs
g' = Just . uncurry (*)
```

以上より，`\x -> (f x >>= g)` は次のように `f'` と `g'` を用いて書くことができます．


```hs
\x -> (f' x >>= g')
```

`\x -> (f x >>= g)` のときと異なるのは，`g'` の内部に `x` が存在しない，ということです．即ち，これは `(>=>)` の定義の形ということができます！

先に `f'`, `g'` を定義前の形に戻してみると次のようになります．

```hs
\x -> ( (Just . ((*2) &&& id)) x >>= Just . uncurry (*) )
```

`(>=>)` の定義の形に持ち込むことができたので，最終的に次のようになります．

```hs
Just . ((*2) &&& id) >=> Just . uncurry (*)
```

アプローチ 1 の結果と異なり，きれいに `(一つ目の函数) >=> (二つ目の函数)` の形が得られました！

# 上級

```hs
\x -> [1..x] >>= \y -> [y..x]
```

を `f >=> g` の形に書き換えてみてください．

# あとがき

もし次回があれば，函数 `arr`, `first`, `second`, `(***)`, `(&&&)` を提供する型クラス `Arrow` を紹介したいです．

# 参考文献

Jeremy Gibbons and Oege de Moor 編，山下伸夫訳 「関数プログラミングの楽しみ」 (オーム社) 2010, 215-238

Miran Lipovača 著，田中英行・村主崇行訳 「すごい Haskell たのしく学ぼう！」 (オーム社) 2012

# 注釈

[^1]: `const :: a -> b -> a` は第二引数を無視して第一引数を返す函数です．即ち，`const x _ = x` より `const x = \_ -> x` となります．
[^2]: `g` のような函数をクロージャ (函数閉包) と呼びます
[^3]: サイズ 2 のタプルのこと
[^4]: `uncurry :: (b -> c -> d) -> ((b, c) -> d)` はニ引数函数をタプルをとる函数に変換します．