多価関数と Category

`Control.Category` モジュールを用いて多価函数[^1] の合成について考えてみます．
余力があればより有用な `Control.Arrow` モジュールについて見ていきたいです．
GHC, GHCi を使う環境を想定しています．


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

# 多価函数

## 多価函数とは

与えられた数 x に対して，その平方根を返す函数について考えてみます．

例えば 4 の平方根は 2 と -2,
9 の平方根は 3 と -3,
17 の平方根は √17 と -√17
のように平方根は (0 等を除いて) 二つ存在することがわかります．

このように入力に対して複数の出力を持つ "函数" を多価函数と呼びます．
数学においては冪根，複素数の対数函数，周期函数の逆函数などさまざまな多価函数が存在します．

## 多価函数は函数ではない？

函数は一般的に "1 つの入力に対して 1 つの出力を返す" ものであり，複数の出力を返す多価函数などは函数ではなく「関係」と呼ばれるようです．


Haskell においても，すべての函数は 1 つの値を返すようになっています．
しかし複数の値をリストにまとめて "1 つのリスト" を返すことで多価函数っぽいものを実装することができます．

例えば平方根を返す函数は次のように書けます

```hs
sqrts :: Floating t => t -> [t]
sqrts x = [sqrt x, - sqrt x]
```

```hs:ghci
ghci> sqrts 4
[2.0,-2.0]

ghci> sqrts 2
[1.4142135623730951,-1.4142135623730951]
```

## 非決定性計算
以降，上の `sqrts` のようにリストを返す函数のことを「非決定性計算」と呼ぶことにします．
これは値 (出力) が 1 つに定まらない計算であるという意味です．多価函数は函数ではないとのことなので，「函数」ではなく「計算」という単語を用いました．

非決定性は，複数の値が重なり合っているなどと言われることもあります．どこかで聞いたことがありますね．Haskell では箱の中の猫は次のように表現することができます[^2]．

```hs
data DA = Dead | Alive
  deriving (Show)

schroedingerscat :: t -> [DA]
schroedingerscat _ = [Dead, Alive]
```

`schroedingerscat` は引数にかかわらずリスト `[Dead, Alive]` を返す函数なので，次のように `Prelude` の `const` 函数を使って書くこともできます．

```hs
data DA = Dead | Alive
  deriving (Show)

schroedingerscat :: t -> [DA]
schroedingerscat = const [Dead, Alive]
```

# `NonDet i o` 型

## `type`
非決定性計算は `i -> [o]` [^3]のような型を持つ函数で表されると考えられます．よって，次のように非決定性計算を表す型を定義することができます．

```hs
type NonDet i o = i -> [o]
```

とりあえず `type` によって型シノニムを作成してみました[^4]．これにより `sqrts` や `schroedingerscat` は次のように書くことができます．

```hs
sqrts :: Floating t => NonDet t t
sqrts x = [sqrt x, - sqrt x]

data DA = Dead | Alive
  deriving (Show)

schroedingerscat :: NonDet t DA
schroedingerscat = const [Dead, Alive]
```

## `data`
Haskell の `type` は単に型に別名 (シノニム) を与えるだけであることを思い出してください．Haskell では型シノニムをある型クラスのインスタンスにする，というようなことはできません．
そこで, `type` ではなく `data` を用いて新しい `NonDet i o` 型をつくることにしましょう．

```hs
data NonDet i o = NonDet (i -> [o])
```

`type` の時と異なり，もはや `i -> [o]` 型と `NonDet i o` 型は異なる型です．
`sqrts` 函数の型は `Floating t => t -> [t]` であるため，そのままでは `NonDet t t` のような型にはなりません．そこで，`NonDet` 値コンストラクタを用いて `sqrts` 函数から `NonDet t t` 型を生み出します．

```hs
sqrts :: Floating t => t -> [t]
sqrts x = [sqrt x, - sqrt x]

sqrtsND :: Floating t => NonDet t t
sqrtsND = NonDet sqrts
```

こうしてできた `sqrtsND` 型は `NonDet t t` 型にはなりましたが，当然このまま `sqrtsND 4` のようには使えません．そこで `runNonDet` 函数を次のように定義します．

```hs
runNonDet :: NonDet i o -> (i -> [o])
runNonDet (NonDet f) = f
```

`runNonDet` 函数は `NonDet` をほどく役割を果たします．これにより，次のように `sqrtsND` 函数を実行できます．

```hs:ghci
ghci> runNonDet sqrtsND 4
[2.0,-2.0]

ghci> runNonDet sqrtsND 2
[1.4142135623730951,-1.4142135623730951]
```

実は，`runNonDet` 函数は別途実装しなくても `NonDet i o` 型を次のようにレコード構文で定義することによって得ることができます．

```hs
data NonDet i o = NonDet { runNonDet :: i -> [o] }
```

## `newtype`
いままで `data` を用いてきましたが，`newtype` を用いるほうが高速なので以降は `newtype` を用いることにします．

```hs
sqrts :: Floating t => t -> [t]
sqrts x = [sqrt x, - sqrt x]

sqrtsND :: Floating t => NonDet t t
sqrtsND = NonDet sqrts


data DA = Dead | Alive
  deriving (Show)

schroedingerscat :: t -> [DA]
schroedingerscat = const [Dead, Alive]

schroedingerscatND :: NonDet t DA
schroedingerscatND = NonDet schroedingerscat


newtype NonDet i o = NonDet { runNonDet :: i -> [o] }
```

```hs:ghci
ghci> runNonDet sqrtsND 4
[2.0,-2.0]

ghci> runNonDet sqrtsND 2
[1.4142135623730951,-1.4142135623730951]

ghci> runNonDet schroedingerscatND 1
[Dead,Alive]
```

# 計算の合成と `Category`
## 非決定性計算の合成
ここで新しく次のような函数を考えます．

```hs
succ_n :: Int -> Int -> [Int]
succ_n n x = [x..x+n]
```

この函数は x から x + n までのリストを返す函数です．

```hs:ghci
ghci> succ_n 2 10
[10,11,12]

ghci> succ_n 10 2
[2,3,4,5,6,7,8,9,10,11,12]
```

この `succ_n` 函数の合成について考えてみます．

たとえば `(succ_n 2)` と `(succ_n 5)` を合成することを考えてみます．
`(succ_n 2) :: Int -> [Int]`, `(succ_n 5) :: Int -> [Int]` なのでそのままではこの二つは当然函数合成できません．

しかし，もし合成するとしたら例えば次のような感じになるでしょうか．
![test.png](https://qiita-image-store.s3.amazonaws.com/0/64300/003e8537-5f5d-c9d6-188d-f73dd7bc2201.png)

このような合成は `map` と `concat` を用いれば行うことができます．

```hs:ghci
ghci> concat (map (succ_n 5) ((succ_n 2) 10))
[10,11,12,13,14,15,11,12,13,14,15,16,12,13,14,15,16,17]
```

括弧が多いですが函数合成を用いると次のように書き直せます．

```hs:ghci
ghci> concat . map (succ_n 5) . (succ_n 2) $ 10
[10,11,12,13,14,15,11,12,13,14,15,16,12,13,14,15,16,17]
```

しかしいちいち `map` と `concat` を記述しなければならないのは，特に合成が長くなってくると面倒です．

```hs:ghci
ghci> concat . map (succ_n 4) . concat . map (succ_n 3) . concat . map (succ_n 2) . (succ_n 1) $ 10
[10,11,12,13,14,11,12,13,14,15,12,13,14,15,16,13,14,15,16,17,11,12,13,14,15,12,13,14,15,16,13,14,15,16,17,14,15,16,17,18,12,13,14,15,16,13,14,15,16,17,14,15,16,17,18,15,16,17,18,19,11,12,13,14,15,12,13,14,15,16,13,14,15,16,17,14,15,16,17,18,12,13,14,15,16,13,14,15,16,17,14,15,16,17,18,15,16,17,18,19,13,14,15,16,17,14,15,16,17,18,15,16,17,18,19,16,17,18,19,20]
```

## `Control.Category`
ここで満を持して登場するのが `Control.Category` モジュール[^5]です．
`Control.Category` モジュール内には `Category` (カテゴリー, 圏) 型クラスが定義されています．まずは定義を見てみます．


```hs:Control.Category
class Category cat where
    -- | the identity morphism
    id :: cat a a

    -- | morphism composition
    (.) :: cat b c -> cat a b -> cat a c
```

見ての通り， `Category` 型クラスの定義は非常に簡単で，`id` 函数と `(.)` 函数を持つだけです．

`id` も `(.)` も見覚えのある函数です．どちらも `Prelude` に同名の函数が定義されていて， `id` は引数をそのまま返す恒等函数，`(.)` は函数合成を行う函数でした．

```hs:ghci
Prelude> :t id
id :: a -> a
Prelude> id 10
10
Prelude> :t (.)
(.) :: (b -> c) -> (a -> b) -> a -> c
Prelude> (\x -> 2 * x) . (\x -> 2 + x) $ 10
24
```

まず，このままだと `Prelude` の `id`, `(.)` と `Control.Category` の `id`, `(.)` が名前の衝突を起こしてしまうので，`Control.Category` モジュールをインポートするときは下のように「修飾付きインポート」するようにします．

```hs
import qualified Control.Category as Cat
```

以降，`Control.Category.id` を `Cat.id`, `(Control.Category..)` を `(Cat..)` と書くことにします．
`.` が二つ見えるのは気のせいではないです．`Cat.` 部分が修飾で `.` が合成を行う函数 `(.)` です．

さて，`Cat.id` と `(Cat..)` は一体どういう働きをする函数なのでしょう．
`Prelude` にある函数と同名なのだから，きっと同じような働きをするのだろうと考えられます．

```hs
Prelude.id :: a -> a
Cat.id :: Cat.Category cat => cat a a

(Prelude..) :: (b -> c) -> (a -> b) -> a -> c
(Cat..) :: Cat.Category cat => cat b c -> cat a b -> cat a c
```

それぞれを見比べてみると，あることがわかります．
`Cat.id` と `(Cat..)` において `cat` を `(->)` に置き換えるとそれぞれ `Prelude.id` と `(Prelude..)` に一致します[^6]．

つまり，型クラス `Category` の型変数 `cat` には，`(->)` のようなものが入るということです．

実は `(->)` は二つの型引数をとる型コンストラクタなのですが，少々わかりにくいですね．そういえば二つの型引数をとる型コンストラクタといえば，先ほど定義した `NonDet` もそうでした．

```hs
newtype NonDet i o = NonDet { runNonDet :: i -> [o] }
```

ということで試しに `cat` を `NonDet` で置き換えてみると，次のようになります

```hs
Cat.id :: NonDet a a
(Cat..) :: NonDet b c -> NonDet a b -> NonDet a c
```

なんだかこれ，「非決定性計算における恒等計算」 と「非決定性計算の合成を行う函数」 に見えてきました．

実は，`Category` 型クラスは「恒等計算 (引数をそのまま返すような計算) `Cat.id`」と「計算の合成を行う函数 `(Cat..)`」を提供してくれる型クラスだったのです．

## `NonDet` を `Category` のインスタンスにする

とりあえず，`Category` は型クラスであり，`NonDet` は `Category` のインスタンスになれそうであるというので，実際にインスタンスにしてみることにします．

まず `Cat.id :: NonDet a a` は引数をそのまま返すようなものということですが，リストを返さなければならない都合上 `NonDet (\x -> x)` とはできないので `NonDet (\x -> [x])` とします．

`(Cat..) :: NonDet b c -> NonDet a b -> NonDet a c` の方は，先ほど考えた `map` と `concat` を使った合成 `concat . map f . g` を使って，それを `NonDet` でくるんでみます．

よって次のようなインスタンス宣言が書けると思います．

```hs
import qualified Control.Category as Cat

newtype NonDet i o = NonDet { runNonDet :: i -> [o] }

instance Cat.Category NonDet where
    id = NonDet (\x -> [x])
    (NonDet f) . (NonDet g) = NonDet $ concat . map f . g
```

修飾付きインポートをしているので，`instance Cat.Category` の部分の `Category` にも修飾が必要なことを忘れないでください．
逆に `instance` 宣言中の `id`, `(.)` には修飾は必要ないことにも注意してください．
(右辺の `(.)` は通常の函数合成であることにも注意してください．)

さて，これで無事 `NonDet` を `Category` のインスタンスにすることができましたが，期待通り動くでしょうか．

まず `succ_n` の `NonDet` 版を作っていなかったので作成します．

```hs
import qualified Control.Category as Cat

newtype NonDet i o = NonDet { runNonDet :: i -> [o] }

instance Cat.Category NonDet where
    id = NonDet (\x -> [x])
    (NonDet f) . (NonDet g) = NonDet $ concat . map f . g

succ_n :: Int -> Int -> [Int]
succ_n n x = [x..x+n]

succ_n_ND :: Int -> NonDet Int Int
succ_n_ND n = NonDet (succ_n n)
```

例のように `runNonDet` を使って実行します．

```hs:ghci
ghci> runNonDet (succ_n_ND 2) 10
[10,11,12]

ghci> runNonDet (succ_n_ND 10) 2
[2,3,4,5,6,7,8,9,10,11,12]
```

では `(Cat..)` を使って `(succ_n_ND 2)` と `(succ_n_ND 5)` の合成を行ってみます．

```hs:ghci
ghci> runNonDet ((succ_n_ND 5) Cat.. (succ_n_ND 2)) 10
[10,11,12,13,14,15,11,12,13,14,15,16,12,13,14,15,16,17]
```

`concat . map (succ_n 5) . (succ_n 2) $ 10` とちゃんと結果が一致しています！

合成が長くなっても同じようにできます．

```hs:ghci
ghci> runNonDet ((succ_n_ND 4) Cat.. (succ_n_ND 3) Cat.. (succ_n_ND 2) Cat.. (succ_n_ND 1)) 10
[10,11,12,13,14,11,12,13,14,15,12,13,14,15,16,13,14,15,16,17,11,12,13,14,15,12,13,14,15,16,13,14,15,16,17,14,15,16,17,18,12,13,14,15,16,13,14,15,16,17,14,15,16,17,18,15,16,17,18,19,11,12,13,14,15,12,13,14,15,16,13,14,15,16,17,14,15,16,17,18,12,13,14,15,16,13,14,15,16,17,14,15,16,17,18,15,16,17,18,19,13,14,15,16,17,14,15,16,17,18,15,16,17,18,19,16,17,18,19,20]
```

いい感じです．

 `Cat.id` も使ってみましょう．

```hs:ghci
ghci> runNonDet (Cat.id) 10
[10]
ghci> runNonDet (Cat.id Cat.. Cat.id) 10
[10]
ghci> runNonDet ((succ_n_ND 5) Cat.. Cat.id Cat.. (succ_n_ND 2) Cat.. Cat.id) 10
[10,11,12,13,14,15,11,12,13,14,15,16,12,13,14,15,16,17]
```

`Cat.id` はまさに通常の函数合成における `id` のように，合成しても影響を与えません．

## `Control.Category` モジュールの他の函数

`Control.Category` モジュールには `(<<<)` と `(>>>)` の二つの函数が定義されています．が，これらの定義はいたって単純です[^7]．

```hs:Control.Category
-- | Right-to-left composition
(<<<) :: Category cat => cat b c -> cat a b -> cat a c
(<<<) = (.)

-- | Left-to-right composition
(>>>) :: Category cat => cat a b -> cat b c -> cat a c
f >>> g = g . f
```

つまり `(<<<)` は `Cat..` とまったく同じで `(>>>)` は `(<<<)` を逆にしただけです．

次のようにインポートすることで `Cat..` と書く代わりに `<<<` を用いることができるようになります．

```hs
import Control.Category hiding (id, (.)) -- Prelude との衝突防止
import qualified Control.Category as Cat

newtype NonDet i o = NonDet { runNonDet :: i -> [o] }

instance Category NonDet where
    id = NonDet (\x -> [x])
    (NonDet f) . (NonDet g) = NonDet $ concat . map f . g

succ_n :: Int -> Int -> [Int]
succ_n n x = [x..x+n]

succ_n_ND :: Int -> NonDet Int Int
succ_n_ND n = NonDet (succ_n n)
```

```hs:ghci
ghci> runNonDet ((succ_n_ND 5) <<< (succ_n_ND 2)) 10
[10,11,12,13,14,15,11,12,13,14,15,16,12,13,14,15,16,17]

ghci> runNonDet ((succ_n_ND 2) >>> (succ_n_ND 5)) 10
[10,11,12,13,14,15,11,12,13,14,15,16,12,13,14,15,16,17]

ghci> runNonDet ((succ_n_ND 5) >>> (succ_n_ND 2)) 10
[10,11,12,11,12,13,12,13,14,13,14,15,14,15,16,15,16,17]
```


## 通常の函数も `Category` のインスタンス

通常の函数 `(->)` も `Category` のインスタンスです．インスタンス宣言は `Control.Category` 内にあるので，見てみましょう．

```hs:Control.Category
instance Category (->) where
    id = Prelude.id
    (.) = (Prelude..)
```

通常の函数に於いては，`Cat.id` は通常の恒等函数 `Prelude.id` であり， `(Cat..)` は通常の函数合成 `(Prelude..)` ということになります．

## `Category` 則

Functor や Monad に存在する Functor 則や Monad 則のように，Category にも「則」があります．一般にあまり聞かないですが，とりあえずここでは Category 則と呼ぶことにします．

Category 則は以下の二つで，Category のインスタンスはこれを満たさなければなりません．

1. 恒等性 `Cat.id >>> f = f >>> Cat.id = f`
1. 結合性 `(f >>> g) >>> h = f >>> (g >>> h)`

### `NonDet` カテゴリーが `Category` 則を満たすことの確認

再度インスタンス宣言を見てみると，

```hs
instance Category NonDet where
    id = NonDet (\x -> [x])
    (NonDet f) . (NonDet g) = NonDet $ concat . map f . g
```

ここで，

```hs
(NonDet f) . (NonDet g) = NonDet $ concat . map f . g
```

は

```hs
(NonDet f) <<< (NonDet g) = NonDet $ concat . map f . g
```

さらに

```hs
(NonDet g) >>> (NonDet f) = NonDet $ concat . map f . g
```

と同じ等式になります．右辺の `(.)` は通常の函数合成であることに注意してください．

- 恒等性 `Cat.id >>> f = f >>> Cat.id = f` の確認

恒等性の式 `Cat.id >>> f = f >>> Cat.id = f` を変形してこれが成り立っていることを確かめます．

`Cat.id` は `NonDet (\x -> [x])` と定義したので

```hs
NonDet (\x -> [x]) >>> f = f >>> NonDet (\x -> [x]) = f
```

さらに `f = NonDet f'` とおくと

```hs
NonDet (\x -> [x]) >>> NonDet f' = NonDet f' >>> NonDet (\x -> [x]) = NonDet f'
```

よって

```hs
NonDet $ concat . map f' . (\x -> [x]) = NonDet $ concat . map (\x -> [x]) . f' = NonDet $ f'
```

即ち，次の等式が成立していることが確認できれば OK です．


```hs
concat . map f' . (\x -> [x]) = concat . map (\x -> [x]) . f' = f'
```


ここで，`f': i -> [o]` なので， `f' s = [t_1, t_2, ..., t_n]` とします．

すると，

```
concat . map f' . (\x -> [x]) $ s
= concat . map f' $ [s]
= concat [f' s]
= concat [[t_1, t_2, ..., t_n]]
= [t_1, t_2, ..., t_n]
= f' s
```


より `concat . map f' . (\x -> [x]) = f'` であることがわかりました．

また，

```
concat . map (\x -> [x]) . f' $ s
= concat . map (\x -> [x]) $ [t_1, t_2, ..., t_n]
= concat [[t_1], [t_2], ..., [t_n]]
= [t_1, t_2, ..., t_n]
= f' s
```

より `concat . map (\x -> [x]) . f' = f'` であることもわかりました．

以上より NonDet カテゴリーは恒等性を満たしていることがわかりました．

- 結合性 `(f >>> g) >>> h = f >>> (g >>> h)` の確認

結合性の確認も，恒等性のときと同様に地道にやっていけば確認できるのですが，ここではモナド則を利用して結合性を確認してみたいと思います．

リストは `Monad` でした．リストの `Monad` インスタンスは次のようになっています．

```hs:GHC.Base
instance Monad [] where
    return x = [x]
    xs >>= f = concat (map f xs)
    faile _ = []
```

また，`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

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

これらを利用すると，

```
concat . map f . g 
= \x -> concat (map f (g x))
= \x -> (g x) >>= f
= g >=> f
= f <=< g
```

と書くことができます．よって `NonDet` の `Category` インスタンスは次のように書けます．

```hs
import Control.Category hiding (id, (.))
import qualified Control.Category as Cat
import Control.Monad

newtype NonDet i o = NonDet { runNonDet :: i -> [o] }

instance Category NonDet where
    id = NonDet return
    (NonDet f) . (NonDet g) = NonDet $ f <=< g
```

`id` (`Cat.id`) のほうもリストモナドの `return = \x -> [x]` に書き直してみました。

さて，モナド則の一つに結合法則 `f <=< (g <=< h) = (f <=< g) <=< h` というものがあります．リストモナドももちろんこの法則を満たしています．


これを利用して `NonDet` カテゴリーの結合性を証明します．

`f = NonDet f'`, `g = NonDet g'`, `h = NonDet h'` とおくと，

```
(f >>> g) >>> h
= (NonDet f' >>> NonDet g') >>> NonDet h'
= NonDet h' <<< (NonDet g' <<< NonDet f')
= NonDet h' <<< (NonDet $ g' <=< f')
= NonDet $ h' <=< (g' <=< f')
= NonDet $ (h' <=< g') <=< f'
= (NonDet $ h' <=< g') <<< NonDet f'
= (NonDet h' <<< NonDet g') <<< NonDet f'
= NonDet f' >>> (NonDet g' >>> NonDet h')
= f >>> (g >>> h)
```

以上より `NonDet` カテゴリーは結合性を満たしていることがわかりました．

### `(->)` カテゴリーが `Category` 則を満たすことの確認

通常の函数 `(->)` については，恒等性 `Cat.id >>> f = f >>> Cat.id = f` は通常の函数の恒等性 `f . id = id . f = f`, 結合性 `(f >>> g) >>> h = f >>> (g >>> h)` は通常の函数合成の結合性 `h . (g . f) = (h . g) . f` となり，`Category` 則を満たしていることがわかります．


## もっと `Category` 
通常の函数 `(->)` と非決定性計算 `NonDet` が `Category` のインスタンスであるということがわかりました．
`Category` のインスタンスになれるものは他にもたくさん考えることができますが，どれにも共通しているのは入力と出力がある「計算」であるということです．

詳しくは参考文献「関数プログラミングの楽しみ」を読むかググるか強い人に聞くといいと思います．

- 状態変換子

```hs
newtype StateA s i o = StateA ((s, i) -> (s, o))
```

- 写像変換子

```hs
newtype MapTrans s i o = MapTrans ((s -> i) -> (s -> o))
```

- 単純オートマトン

```hs
newtype Auto i o = Auto (i -> (o, Auto i o))
```

以下のページで詳しく解説されています
[Intro to Machines & Arrows (Part 1: Stream and Auto) · in Code](http://blog.jle.im/entry/intro-to-machines-arrows-part-1-stream-and "Intro to Machines & Arrows (Part 1: Stream and Auto) · in Code")
[Auto as Category, Applicative & Arrow (Intro to Machines/Arrows Part 2) · in Code](http://blog.jle.im/entry/auto-as-category-applicative-arrow-intro-to-machines "Auto as Category, Applicative & Arrow (Intro to Machines/Arrows Part 2) · in Code")

- Reader

```hs
newtype ReaderA s i o = ReaderA ((s, i) -> o)
```

- Writer

```hs
newtype WriterA w i o = WriterA (i -> (w, o))
```

- Kleisli

```hs
newtype Kleisli m i o = Kleisli (i -> m o)
```
今回作った `NonDet` カテゴリーは `i -> [o]` という計算をもっていましたが，リスト以外でも任意のモナドを返す計算 `i -> m o` はカテゴリーにすることができます．`Kleisli` カテゴリーはそのことを表しています．
実際，Kleisli カテゴリーのインスタンス宣言は以下のようになっています (`Control.Arrow` モジュール[^8])

```hs:Control.Arrow
instance Monad m => Category (Kleisli m) where
    id = Kleisli return
    (Kleisli f) . (Kleisli g) = Kleisli (\b -> g b >>= f)
```

`(\b -> g b >>= f)` は `f <=< g` と同値です．

# `Arrow`

`Control.Arrow` モジュールには `Category` 型クラスを拡張した (?) `Arrow` 型クラスが定義されています．
`Arrow` にも触れようかと思いましたが力尽きたのでとりあえずここまでにします．



# 参考文献

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

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

# あとがき

最後のほうが投げやりになってしまったのと，自分もまだ勉強中のため間違い等等あると思います．指摘などいただけると嬉しいです．
Arrow のすごさに感動している年末です．

# 注釈

[^1]: let 函数 = 関数
[^2]: すごい H 本の `Prob` モナドを使うと，各状態の確率も表せそうです．
[^3]: input, output
[^4]: nondeterministic (非決定性の)
[^5]: `Control.Category` モジュールは base パッケージに含まれています．
[^6]: `a -> b` は `(->) a b` と書くことができます．
[^7]: `Control.Category` モジュール内では `import qualified Prelude` しています．
[^8]: `Control.Arrow` モジュールは base パッケージに含まれています．