bitterharvest’s diary

A Bitter Harvestは小説の題名。作者は豪州のPeter Yeldham。苦闘の末に勝ちえた偏見からの解放は命との引換になったという悲しい物語

Haskellで学ぶ圏論・ウォームアップ編 邪推

1.合成関数から元の関数を探る

合コン後の出口調査を利用して、それぞれの男性に対して、彼が可愛いと思った女性が頼もしいと思う男性を求めることができた。これは「男性の恋敵」を示しているともいえるが、その図は次のようになっていた。
f:id:bitterharvest:20150127100831p:plain
上記の図を男性の恋敵図と呼ぶことにする。男性の恋敵図は、それぞれの男性に対して恋敵である男性(多くて1名)を示している。

それでは、男性の恋敵図から、男性はどの女性を可愛いと思ったのか、また、女性はどの男性を頼もしいと思ったのかが推察できるだろうか。

2.選択的な問題

前者の場合を考えてみよう。女性のグループは男性の恋敵図を入手したばかりでなく、仲間同士でおしゃべりしているうちに、誰がどの男性を頼もしいと思ったかが分かったとしよう。そして、女性のグループの次の話題は、どの男性がだれを可愛いと思ったかに移ったとしよう。即ち、下図で疑問符で記した個所の関数を、女性のグループが推察している場面を考える。
f:id:bitterharvest:20150127162613p:plain

今、男性の恋敵図(最初の図)で与えられた対応関係を関数compsiteとする。また、上の図(二番目の図)で疑問符で示された箇所の関数をcute'とする。この時、cute'は次のようにして求めることができる(利用できる関数はcomposeとreliableである)。

cute' :: Men -> [Women]
cute' x = [ y | y <- [W1 .. W4], let z = compose x, reliable y == z]

上記のプログラムは次のようになっている。男性xと恋敵である男性をz(男性xが可愛いと思った女性が頼もしいと思った男性をz)とし、zをcompose xから求める。そして、zを頼もしいと思った女性yを関数reliableを用いて探す。この時、yはすべての女性について試み、条件を満たしたものをリストとして取り出す。その結果は次のようになる。

*MatchmakingParty> cute' M1
[W3]
*MatchmakingParty> cute' M2
[W1]
*MatchmakingParty> cute' M3
[W2,W4]

この結果、M1,M2に対してはだれを可愛いと思ったかは判明するが、M3はW2かW3ということになり「選択」の余地が残る。この結果、W2とW3の女性はいずれかが選ばれたのだろうと、場合によっては、自分の都合のよいほうに邪推することであろう。

一般に\(h = g \circ f \)において、\(h\)と\(g\)が分かっているとき、\(f\)の決定は選択的である。この証明はそれほど難しくはないので、試みるとよい。

3.決定的な問題

それでは後者の場合を考えてみよう。今度は男性グループが「女性たちはだれを頼もしいと思ったか」を判断する場面である。下図で疑問符の関数を判断することになる。
f:id:bitterharvest:20150127170354p:plain

この関数をreliable'とするとプログラムは次のようになる(利用できる関数はcomposeとcuteである)。

reliable' :: Women -> [Men]
reliable' y = [ z | x <- [M1 .. M3], cute x == y, let z = compose x]

関数reliable'は女性yを入力とする。yを可愛いと思った男性xをcuteを用いてさがす。このとき、xはすべての男性について試み、条件を満たしたものを取り出す。さらに、男性の恋敵図から、この男性xと恋敵である男性z(男性xが可愛いと思った女性が頼もしいと思った男性z)を関数composeから求める。

上記のプログラムを実行すると次のようになる。

*MatchmakingParty> reliable' W1
[M3]
*MatchmakingParty> reliable' W2
[M2]
*MatchmakingParty> reliable' W3
[M1]
*MatchmakingParty> reliable' W4
[]

全ての入力に対して、出力は高々一つ(この場合には、W1,W2,W3に対しては一つの出力をW4に対しては空)である。この結果から、reliable'という関数が一意に決まることが分かる。

一意に決まったのは、この問題が特殊なためではない。一般に、\(h = g \circ f \)において、\(h\)と\(f\)が分かっているとき、\(g\)は「決定的」に定めることが可能である。

これは、zを定めているところをよく読むと分かる。先の例では、「この男性xが可愛いと思った女性が頼もしいと思った男性zを関数composeで求める」となっていたが、可愛いと思った女性はyである。このため、ここの部分は、yからzを求める関数reliable'そのものとなる。このことは一般化して証明できるがここでは省略する。

なお、W4については値が定まらないが、これは合成関数を作るとき、W4が使われていないためである。従って、reliable'は全関数ではなく、部分関数として与えられる。男性たちの会話を後で知って、W4の女性は仲間外れにされたようでさみしい思いをすることであろう。