Control.Category
モジュールを用いて多価函数1 の合成について考えてみます.
余力があればより有用な 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> sqrts 4
[2.0,-2.0]
ghci> sqrts 2
[1.4142135623730951,-1.4142135623730951]
非決定性計算
以降,上の sqrts
のようにリストを返す函数のことを「非決定性計算」と呼ぶことにします.
これは値 (出力) が 1 つに定まらない計算であるという意味です.多価函数は函数ではないとのことなので,「函数」ではなく「計算」という単語を用いました.
非決定性は,複数の値が重なり合っているなどと言われることもあります.どこかで聞いたことがありますね.Haskell では箱の中の猫は次のように表現することができます2.
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]
3のような型を持つ函数で表されると考えられます.よって,次のように非決定性計算を表す型を定義することができます.
type NonDet i o = i -> [o]
とりあえず type
によって型シノニムを作成してみました4.これにより 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> 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> 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> 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> 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> 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> 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
(カテゴリー, 圏) 型クラスが定義されています.まずは定義を見てみます.
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
は引数をそのまま返す恒等函数,(.)
は函数合成を行う函数でした.
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..)
に一致します6.
つまり,型クラス 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> 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> 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> 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> 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.
-- | 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> 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
内にあるので,見てみましょう.
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
インスタンスは次のようになっています.
instance Monad [] where
return x = [x]
xs >>= f = concat (map f xs)
faile _ = []
また,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
モジュール8)
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 のすごさに感動している年末です.