36
33

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

多価関数と Category

Last updated at Posted at 2014-12-27

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
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] を返す函数なので,次のように Preludeconst 函数を使って書くこともできます.

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.これにより sqrtsschroedingerscat は次のように書くことができます.

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

しかし,もし合成するとしたら例えば次のような感じになるでしょうか.
test.png

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

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]

しかしいちいち mapconcat を記述しなければならないのは,特に合成が長くなってくると面倒です.

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 (カテゴリー, 圏) 型クラスが定義されています.まずは定義を見てみます.

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

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

import qualified Control.Category as Cat

以降,Control.Category.idCat.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] }

ということで試しに catNonDet で置き換えてみると,次のようになります

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

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

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

NonDetCategory のインスタンスにする

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

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

(Cat..) :: NonDet b c -> NonDet a b -> NonDet a c の方は,先ほど考えた mapconcat を使った合成 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, (.) には修飾は必要ないことにも注意してください.
(右辺の (.) は通常の函数合成であることにも注意してください.)

さて,これで無事 NonDetCategory のインスタンスにすることができましたが,期待通り動くでしょうか.

まず succ_nNonDet 版を作っていなかったので作成します.

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

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 のインスタンスはこれを満たさなければなりません.

  1. 恒等性 Cat.id >>> f = f >>> Cat.id = f
  2. 結合性 (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.idNonDet (\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

と書くことができます.よって NonDetCategory インスタンスは次のように書けます.

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

通常の函数 (->) と非決定性計算 NonDetCategory のインスタンスであるということがわかりました.
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)

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 パッケージに含まれています.

36
33
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
36
33

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?