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

次の記事 → 綱渡りと Category (と，Kleisli)

多価函数

多価函数とは

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

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

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

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

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

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

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

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

ghci

ghci> sqrts 4
[2.0,-2.0]

ghci> sqrts 2
[1.4142135623730951,-1.4142135623730951]

非決定性計算

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

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

data DA = Dead | Alive
  deriving (Show)

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

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

data DA = Dead | Alive
  deriving (Show)

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

`NonDet i o` 型

`type`

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

type NonDet i o = i -> [o]

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

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 型をつくることにしましょう．

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 型を生み出します．

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 函数を次のように定義します．

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

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

ghci

ghci> runNonDet sqrtsND 4
[2.0,-2.0]

ghci> runNonDet sqrtsND 2
[1.4142135623730951,-1.4142135623730951]

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

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

`newtype`

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

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] }

ghci

ghci> runNonDet sqrtsND 4
[2.0,-2.0]

ghci> runNonDet sqrtsND 2
[1.4142135623730951,-1.4142135623730951]

ghci> runNonDet schroedingerscatND 1
[Dead,Alive]

計算の合成と `Category`

非決定性計算の合成

ここで新しく次のような函数を考えます．

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

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

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] なのでそのままではこの二つは当然函数合成できません．

しかし，もし合成するとしたら例えば次のような感じになるでしょうか．

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

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]

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

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 を記述しなければならないのは，特に合成が長くなってくると面倒です．

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 モジュール⁵です．
Control.Category モジュール内には Category (カテゴリー, 圏) 型クラスが定義されています．まずは定義を見てみます．

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 は引数をそのまま返す恒等函数，(.) は函数合成を行う函数でした．

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 モジュールをインポートするときは下のように「修飾付きインポート」するようにします．

import qualified Control.Category as Cat

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

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

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..) に一致します⁶．

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

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

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

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

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 でくるんでみます．

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

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 版を作っていなかったので作成します．

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 を使って実行します．

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) の合成を行ってみます．

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 とちゃんと結果が一致しています！

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

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 も使ってみましょう．

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 モジュールには (<<<) と (>>>) の二つの函数が定義されています．が，これらの定義はいたって単純です⁷．

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.. と書く代わりに <<< を用いることができるようになります．

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)

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 内にあるので，見てみましょう．

Control.Category

instance Category (->) where
    id = Prelude.id
    (.) = (Prelude..)

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

`Category` 則

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

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

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

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

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

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

ここで，

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

は

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

さらに

(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]) と定義したので

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

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

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

よって

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

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

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 インスタンスは次のようになっています．

GHC.Base

instance Monad [] where
    return x = [x]
    xs >>= f = concat (map f xs)
    faile _ = []

また，Control.Monad モジュールには次のように (>=>), (<=<) という函数が定義されています．

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 インスタンスは次のように書けます．

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 のインスタンスになれるものは他にもたくさん考えることができますが，どれにも共通しているのは入力と出力がある「計算」であるということです．

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

状態変換子

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

写像変換子

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

単純オートマトン

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

以下のページで詳しく解説されています
Intro to Machines & Arrows (Part 1: Stream and Auto) · in Code
Auto as Category, Applicative & Arrow (Intro to Machines/Arrows Part 2) · in Code

Reader

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

Writer

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

Kleisli

newtype Kleisli m i o = Kleisli (i -> m o)

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

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 のすごさに感動している年末です．

注釈

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

多価関数と Category

多価函数

多価函数とは

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

非決定性計算

NonDet i o 型

type

data

newtype

計算の合成と Category

非決定性計算の合成

Control.Category

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

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

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

Category 則

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

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

もっと Category

Arrow

参考文献

あとがき

注釈

`NonDet i o` 型

`type`

`data`

`newtype`

計算の合成と `Category`

`Control.Category`

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

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

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

`Category` 則

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

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

もっと `Category`

`Arrow`