読者です 読者をやめる 読者になる 読者になる

bitterharvest’s diary

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

神奈川県中央部の勝坂遺跡公園を訪ねる

旅行

相模線にゆられて縄文の遺跡を訪ねた。これは横浜から出ている相模本線ではない。JRだ。神奈川県の中央部を縦断するように、東海道線茅ヶ崎駅横浜線橋本駅の間を結んでいるローカル線だ。東京の近郊には珍しい単線運転でもある。

往きは小田急線の海老名駅で乗り換えた。小田急線の駅とJRの駅との間は連絡橋で接続されており、丹沢山塊の景色を楽しみながら渡ることができる。小田急側の駅は大きな駅で町の中心を担っていることを実感させてくれるが、JR側の駅は何とも萎びている。鉄道マニアは既に承知のことと思うが、JR線に沿ってもう一本線路が引かれている。相模本線の方から延びてきて厚木の駅までJR線と並走する。かつて、相模線は相鉄の所有であったが戦時中に国鉄に買収された。並走している線は、これを反映する歴史的な名残なのだろう。

今回、訪れたのは勝坂遺跡公園である。この遺跡は国指定の史跡になっている。最寄り駅は下溝駅である。とはいっても都心の感覚での最寄り駅ではない。田舎の感覚でとらえないと大変なことになる。電車を降りて撮った写真が以下である。
f:id:bitterharvest:20170317150807j:plain
駅員さんももちろんいない。駅を出て振り返っての写真。とてもそっけない。
f:id:bitterharvest:20170317151113j:plain
ここは相模台地の西側であり、さらにその西側を相模川が流れている。川の向こう側に見えるのが丹沢山塊である(下の写真の右側の大きな建物はヤマト運輸の厚木ゲートウェイ)。
f:id:bitterharvest:20170317151551j:plain
f:id:bitterharvest:20170317151631j:plain
相模線に沿って造られている県道46号線を南下する。道の山側にだけ幅の狭い歩道がついている。トラックの交通量が多く歩道を歩いていてもこすられそうな感じがして心地よくない。20分近く歩いたところで、勝坂遺跡公園の駐車場への案内に出会う。駐車場の脇に沿って遺跡に入る道が作られている。幅の狭い山道のようなところを進んでいく。途中には、春の訪れを知らせてくれるかのように、花大根の群れが紫色の可憐な花を咲かせていた。
f:id:bitterharvest:20170317152928j:plain
f:id:bitterharvest:20170317153103j:plain

山道を抜け台地に出ると、走り回る子供たちの大きな歓声が迎えてくれた。遠くに竪穴住居らしきものが見える何もない大きな公園だ。

近くに遺跡があったので、取り敢えずカメラに納める。敷石住居跡だ。
f:id:bitterharvest:20170317154608j:plain
温暖な気候に恵まれた縄文時代は中期末(4500年前)になると冷涼化する。これとともに、竪穴住居の構造が大きく変わり、石を敷いた住居が出現する。写真は敷き詰められた石である。石を温めることで、部屋の温度を上げたのであろう。

縄文時代は前期から中期にかけては、温暖な気候に恵まれていた。当時の生活様式は採取狩猟である。しかし、一般的な採取狩猟民とは異なり、縄文の人たちは定住生活を送っていた。森を開いて住むための空間をつくり、また、住居の周りにはドングリやクリやクルミの木を植樹して、定住しやすい環境を作っていた。住居の周りに作られた林は二次林と呼ばれるが、勝坂遺跡公園にもそれがあった。緑に生い茂っていれば想像できるのだろうが、この時期、葉が落ちてしまって隙間だらけで寂しいけれども次の写真である。
f:id:bitterharvest:20170317163039j:plain
そうこうしているうちに、公園の一番隅にある竪穴住居にたどり着いた。二つほどあったが、一つは笹で他の一つは土で屋根が葺かれていた。笹で作られた竪穴住居は4700年前ごろに作られたものの復元である。入口付近は、
f:id:bitterharvest:20170317165018j:plain
中に入ってみる。内部の壁は木で作られている。豪勢だ。また、少し奥まったところに炉が設けられている。お決まりのパターンだ。温度計と湿度計があるがもちろん当時はない。
f:id:bitterharvest:20170317165458j:plain
建物を支えている柱だ。この当時は石斧しかないので、作るのは大変だったろうと思う。f:id:bitterharvest:20170317165613j:plain
外に出て全景を取る。
f:id:bitterharvest:20170317165744j:plain
次は屋根が土で葺かれた竪穴住居だ。入口の写真を一枚。家というよりもなんとなく土で盛られた墓に入っていくような気分になる。
f:id:bitterharvest:20170317170010j:plain
炉の上に、燻製でも作るのだろうか吊るし棚があった。
f:id:bitterharvest:20170317170212j:plain
内から入口の方を見ると、
f:id:bitterharvest:20170317170327j:plain
二つの住居を一緒に撮る。
f:id:bitterharvest:20170317170500j:plain
建物跡も近くにある。
f:id:bitterharvest:20170317170618j:plain

少し離れたところに中村家住宅があることを案内で知ったのでそこに向かう。この建物は、国登録有形文化財に指定されている。幕末期の和洋折衷の珍しい建物だ。当初は三階建てだったが関東大震災後に三階部分を取り除いたそうだ。
f:id:bitterharvest:20170317171011j:plain
中村家と勝坂遺跡には因縁がある。大正15年に休暇で帰省していた学生の清水二郎が、この家の当主中村忠亮が所有する畑で散在する多数の土器を発見し、それを考古学者の大山柏(維新の元勲の大山巌は父)に標本として渡したことが、この遺跡発見の発端となった。

中村家から少し離れたところに、勝坂式土器発見の地があった。また、勝坂遺跡は相模川の小さな支流の鳩川沿いの谷戸に形成されたとのことであった。

最初に来た公園に戻り管理棟を訪れた。小さな会議ができるかなと思えるぐらいの空間であったが、そこには復元だが大山柏発掘の土器が展示されていた。
f:id:bitterharvest:20170317172812j:plain
また、この遺跡で発見された土器は、勝坂式土器と呼ばれ、中部・関東地方の縄文時代中期の指標となった。
f:id:bitterharvest:20170317173039j:plain
縄文土器は、この後の弥生式土器や古墳時代の土器と比べると重厚感にあふれている。松木武彦さんは『進化考古学の大冒険』のなかで、なぜ形は変わるのかについて説明している。それによれば、縄文時代には祭祀と調理具・食器の両方で使われたため豪華であったが、弥生時代になると後者のためだけに使われるようになり実用的な形になったと認知心理学を用いて説明している。

帰りは相模線の風景をもう少し満喫したかったので、海老名の方には戻らず、相模線をそのまま乗り継いで橋本駅に向かった。春がそこまで来ていることを知らせてくれるのどかな一日を相模の地で楽しむことができた。

プログラマーのための圏論(中)

プログラマーのための圏論 (圏論とHaskell)

プログラマのための圏論』は(上)の後の部分をまとめ(中)にしてPDFファイルにしました。参考にしてください。なお、(上)のホームページはこちら

関手ープロファンクタ

プログラマーのための圏論 (圏論とHaskell)

6.10 プロファンクタ

1)双関手の復習

プロファンクタの話をする前に、双関手を再度勉強しておこう。関手と反関手は矢印が逆向きであるという関係を有していたが、双関手とプロファンクタも同じような関係にある。

Haskellでは双関手はData.Bifunctorで定義されている。それによれば、

Prelude Data.Bifunctor> :i Bifunctor
class Bifunctor (p :: * -> * -> *) where
  bimap :: (a -> b) -> (c -> d) -> p a c -> p b d
  first :: (a -> b) -> p a c -> p b c
  second :: (b -> c) -> p a b -> p a c

このうち、\(bimap\)を図で表すと次のようになる。
f:id:bitterharvest:20170306154429p:plain

この図から分かるように、二つの対象がそれぞれの対象に対して与えられた射によって計算が行われる。双関手は\(Either\)と\( (,) \)などのデータ型に対して用意されている。

\(bimap\)はこれらのデータ型に対しては次のように定義されている。

instance Bifunctor (,) where
  bimap f g ~(a, b) = (f a, g b)

instance Bifunctor Either where
  bimap f _ (Left a) = Left (f a)
  bimap _ g (Right b) = Right (g b)

双関手になれるために少し実行してみよう。二つの関数を必要とするので、これを定義する。左側は3倍する関数としよう。また、右側は文字の長さを計算する関数としよう。

Prelude> import Data.Bifunctor
Prelude Data.Bifunctor> a =  a = bimap (*3) length

これを利用してみる。まず、タプルに対してだ。

Prelude> import Data.Bifunctor
Prelude Data.Bifunctor> a = ((*3), length)
Prelude Data.Bifunctor> a (5, "Bifunctor")
(15,9)

次は\(Either\)に対してである。

Prelude Data.Bifunctor> a (Left 5)
Left 15
Prelude Data.Bifunctor> a (Right "Either is used as a bifunctor.")
Right 30

2)プロファンクタ

プロファンクタの型クラスは次のように定義される。

class Profunctor f where
    dimap :: (a -> b) -> (c -> d) -> f b c -> f a d

図で示すと
f:id:bitterharvest:20170306154021p:plain
となる。

双関手の時の図と比較すると、\(a\)と\(b\)とが逆になっているのが分かる。今、関数\(\rightarrow\)をプロファンクタのインスタンスとすると、\(f\)のところを関数に変えればよいので、\(dimap\)は次のようになる。

instance Profunctor (->) where
  dimap :: (a -> b) -> (c -> d) -> (b -> c) -> (a -> d)
  dimap f g h = g.h.f

となる。

少し利用してみよう。

*Main Data.Bifunctor> a = dimap length odd (`div` 2)
*Main Data.Bifunctor> a "Do you like Profunctor?"
True

長かったが、関手の説明はこれで一応終了である。

関手―反関手

プログラマーのための圏論 (圏論とHaskell)

6.9 反関手

以前に、Readerと呼ばれる関手について説明したことがある。二つの射を得て一つの射を出力するという分かりにくい関手だったのではと想像している。圏論は、射を中心にして考えるので、射を射の入力や出力として利用するのは自然なのだが、値で慣れている場合には頭の切り替えが必要になり、分かりにくいことと思う。

そこで、Readerの復習をした後で、反関手の話をしよう。

1)射を関手にする―復習

具体的な例を用いて、前に説明したファンクタ\(Reader\)を再度考えてみる。そのため、次の問題を考えてみよう。

【問題】苗字という概念がなかったある地域\(\mathcal{C}\)で名前の文字数をカウントする関数\(f\)が用いられていたとしよう。この地域と交流のあった別の地域\(\mathcal{D}\)に、様々な技術移転が生じ、文字数をカウントする関数も他のものと一緒に移転された。しかし、\(\mathcal{D}\)での名前は氏や階級などが一緒になった複雑な構造をなしていた。数学の得意な人がいろいろと考えて、複雑な構造の名前から「名」の部分を取り出す関数\(g\)を考え出した。\(\mathcal{D}\)での名前から名の部分の文字数を得るためにはどうしたらよいかを関手を用いて説明しなさいというのがこの問題である。

それぞれの地域を圏とし、それぞれの圏の構成を下図に示す。
f:id:bitterharvest:20170305160623p:plain
\(\mathcal{C}\)では、名前を対象\(A\)で文字数を対象\(B\)で表わした。また、名前から文字数に変換する射はそのまま\(f\)である。\(\mathcal{C}\)の対象と射は関手\(F\)によって\(\mathcal{D}\)に移される。即ち、\(\mathcal{C}\)の\(A,B\)は\(F(A),F(B)\)に移され、\(f\)は\(F(f)\)に移されている。

複雑な構造の名前の対象は\(F(R)\)で表した(これは、\(\mathcal{C}\)の対象\(R\)を\(\mathcal{D}\)に移したと読める。このように意図しているのだが、\(\mathcal{C}\)にはもしかすると\(R\)は存在しないかもしれない。この問題の場合には明らかに存在しないのだ。従って、ここでは、この国の名前は\(F(R)\)であるという程度に考えて欲しい。\(F\)がついている理由はHaskellのプログラムになった時に分かる)。(同じ理由から)複雑な名前から名に変換する射を\(F(g)\)とした。ここで、求めたいのが、\(F(R)\)から\(F(B)\)への写像である。これは次のようになる。
f:id:bitterharvest:20170305160646p:plain

圏でのこの関係をHaskellで記述すると次のようになる。
f:id:bitterharvest:20170306094934p:plain
具体的にプログラムで記述すると、

{-# LANGUAGE InstanceSigs #-}
newtype Reader r a = Reader { getName :: r -> a }

instance Functor (Reader r) where
  fmap :: (a -> b) -> Reader r a -> Reader r b
  fmap f (Reader g) = Reader (f.g)

first :: (a,a,a) -> a
first (a,_,_) = a

count :: Reader (String, String, String) Int
count = fmap (length :: String -> Int) (Reader first)

smap =[("Takuya","Omi","Kimura"),("Goro","Muraji","Inagaki"),("Hiroaki","Tomonomiyakko","Nakai"),("Singo","Agatanusi","Katori")]

このプログラムで\(count\)が\(Reader \ r \ r\)即ち\(F(r)\)から\(Reader \ r \ b\)即ち\(F(b)\)への射を出力してくれる。そこで、データ型(\(Reader \ r \ a\))で定義されているフィールド\(getName\)を利用して射\(r \rightarrow a\)を取り出す。ここで取り出される射は\(r\)から\(b\)への関数である。

これに、複雑な構造の名前(といっても、ここでは、ファーストネームと氏姓制度での地位とラストネームからなるトリプルだが)を入力に与えると、その文字数を与えてくれる。なお、名を散りだす関数は\(first\)である。これは、トリプルの最初の要素を取り出す。

最初の実行例は個人名を与えたものである。\(count\)は\(F(r)\)から\(F(b)\)への射を与える。これに、\(getName\)を施すと\(r\)から\(b\)への射\(length.first)\)を与える。これに("Mike", "Omuraji", "Brooks")という名前を与えてるとファーストネームの文字数が出力される(因みに、友人のMike Brooksは現在は学長だ。「大連」より偉いかもしれない)。少し、複雑だがこのプログラムはこのようになっている。

次は、あるグループを構成していた人たちの名前を入力とした。<$>もファンクタの一種だが、配列での適応を可能にしてくれる。

*Main> getName count ("Mike","Omuraji","Brooks")
4
*Main> getName count <$> smap
[6,4,7,5]
*Main> getEven even' "Taro"
True
*Main> getEven even' <$> smap'
[True,True,False,False]

データ型\(Reader\)は関数を表現しているので、関数型(Function Type)とも呼ばれる。

圏での表現を書き換えると下図のように表すこともできる。
f:id:bitterharvest:20170305160721p:plain
この図から、\(\mathcal{C} \times \mathcal{D}=\mathcal{D}\)であることから、デカルト積になっていることもわかる。

2)反関手

それでは先ほどの文字数を求める問題にもう一度戻ることにしよう。

【問題】さらに別の地域\(E\)があって、そこでは文字数が偶数であるかどうかを判断していたとする。

取り敢えず\(C,E\)を圏にして図を示すことにしよう。
f:id:bitterharvest:20170305160738p:plain
ここで、\(f\)は\(A\)から\(B\)に写像する。それにもかかわらず、矢印の方向は\(F(B)\)から\(F(A)\)である。同様に\(g\)は\(B\)から\(C\)に写像するが、矢印の方向は\(F(C)\)から\(F(B)\)である。このように、ドメイン側の圏\(C\)の全ての射に対して、コドメイン側の圏\(E\)ではその方向が逆になるものを反関手(\(Contravariant\)あるいは\(Cofunctor\))と呼ぶ。

方向が逆向きになることを説明する。今回も前回と同じように、射を利用して、関手を張ることとする。前回は\(Reader\)という関手であった。これは\( new type \)を利用してデータ型を定義したが、その時のデータ型は\(Reader \ r \ a = Reader \ r \rightarrow a\)であった。
その時、\(r\)の方は固定して\(a\)の方が変われるようにした。\(Reader \ r \ a\)は、\(r\)を入力とし、\(a\)を出力とすると考えることができる。従って、データ型の\(Reader \ r \ a\)とフィールドで定義した\(r \rightarrow a\)とは方向が同じと見なせる。

次に、これから説明しようとするものは、反関手\(Writer \ c\)で張られる。後で示すが、そのデータ型は、\(Writer \ c \ a = Writer \ a \rightarrow c\)である。これは、前者\(Reader\)が射の入力を固定したのに対し、後者\(Writer \)は射の出力を固定するためである。このため、\(Writer \ c \ a\)は\(c\)を入力とし、\(a\)を出力とするようにふるまう。これに対して\(Writer \ a \rightarrow c\)は逆である。このため、方向はお互いに逆になる。

さて、本題に移ろう。ここで求めたいのは、\(F(C)\)から\(F(A)\)への射である。下図のようになる。
f:id:bitterharvest:20170305160757p:plain

Haskellでの表記に変えると以下のようになる。
f:id:bitterharvest:20170305160813p:plain

プログラムは以下のようになる。

{-# LANGUAGE InstanceSigs #-}
class Contravariant f where 
  contramap :: (a -> b) -> f b -> f a

newtype Writer c a = Writer { getEven :: a -> c }

instance Contravariant (Writer c) where
  contramap :: (a -> b) -> Writer c b -> Writer c a
  contramap f (Writer g) = Writer (g.f)

even' = contramap (length :: String -> Int) (Writer even)

smap' =["Takuya","Goro","Hiroaki","Singo"]

前と同じように実行してみよう。予想通りの動きになっている。

*Main> getEven even' "Taro"
True
*Main> getEven even' <$> smap'
[True,True,False,False]

\(Reader\)の場合と同じようにこれも圏の積になるが、反関手なので、\(C^{op} \times E \rightarrow E \)と記す。\(\mathcal{C}^{op}\)は\(\mathcal{C}\)の全ての矢印を逆にした圏を表す。

次回はいよいよ関手の最後、プロファンクタのお出ましだ。

秦野市桜土手古墳公園

旅行

小田急線を利用して秦野市にある古墳を見に行った。最寄り駅は渋沢である。北口に出てまっすぐに丹沢の方に向かって歩く。島津製作所日産自動車などの工場街の中にあるのが桜土手古墳公園だ。
f:id:bitterharvest:20170303163122j:plain

中に入るとすぐにこんもりと盛り上がった小さな丘がある。古墳だ。
f:id:bitterharvest:20170303163313j:plain
近づいてみるとこのような説明書きがある。
f:id:bitterharvest:20170303163407j:plain

それぞれの古墳について築造された時期が記されていなかったが、ウィキペディアで調べてみると、7世紀後半を中心に6世紀末から8世紀初頭に作られたとのことだ。35基の古墳が確認されているそうで、公園内にはそのうちの6基が保存されている。

展示館に古墳時代ジオラマがあった。すべてが円墳である。
f:id:bitterharvest:20170303164343j:plain

公園の中は古墳を取り巻くように散歩道が作られているのでそれに沿って歩く。古墳の中には木が生えているものもある。
f:id:bitterharvest:20170303165924j:plain
この古墳には次のような説明があった。径が15.6mあるそうだ。
f:id:bitterharvest:20170303170015j:plain

しばらく行くと復元された古墳に出会う。
f:id:bitterharvest:20170303170159j:plain
1号古墳を復元したものだ。周りは葺石で覆われ、そして、2段になっている。お墓は横穴式石室である。石室の入り口は
f:id:bitterharvest:20170303170742j:plain
石室の中から外側を覗くと
f:id:bitterharvest:20170303170848j:plain
公園事務所の人が掃除をしている姿も見ることができる。
横穴式の石室の説明は、
f:id:bitterharvest:20170303171049j:plain

石室の中ではなく墳丘の上部から、割られた大きな須恵器の甕が発見されたそうである。埋葬儀式のときに割られたものと考えられている。
f:id:bitterharvest:20170303171345j:plain
手前の大きな甕がそれである。穴が空いている部分が、割るために何かをぶつけた場所と考えられている。甕を割ることで死者がもたらす災いから免れたいなどと願ったのであろうと葬祭儀式の意義を見つけながら眺めた。

お墓を作っている場面を想定したジオラマもあった。
f:id:bitterharvest:20170303171634j:plain

墓の復元にはフォークリフトなどを用いて30日程度かかったそうである。当時の人たちはどれだけの日数をかけたのであろうか。また、築造中の事故も多かったのではなどと思いを巡らしながら、お腹もすいてきたこともあって古墳公園を後にした。

関手―余積をファンクタで実現する

プログラマーのための圏論 (圏論とHaskell)

6.8 余積をファンクタで実現する

前回の記事では関手を利用しての積と余積を定義する中で\(Identity\)を用いたが、その詳しい説明はしなかった。そこで、ここでは、まず、データ型\(Identity\)の定義から話を始めよう。関手\(Identity\)の互換図は下図のようになる。
f:id:bitterharvest:20170303080859p:plain
これを参考にしてHaskellで\(Identity\)のデータ型とファンクタを実現すると次のようになる。

data Identity a = Identity a deriving (Eq, Show, Read) 

instance Functor Identity where
  fmap f (Identity a) = Identity (f a)

終対象への写像に似ている関数で、一つの値\(c\)に写像する定数関数\(const\)と呼ばれるものがある。これを下図のように関手として利用してみよう。
f:id:bitterharvest:20170306141445p:plain
\(Const\)のデータ型とファンクタは次のようになる。

data Const c a = Const c deriving (Eq, Show, Read)

instance Functor (Const c) where
  fmap f (Const c) = Const c

少し利用してみよう。

*Main> a = Identity 4
*Main> fmap (*3) a
Identity 12
*Main> fmap (+6) a
Identity 10
*Main> b = Const 3
*Main> fmap (*3) b
Const 3
*Main> fmap (+6) b
Const 3

今得た二つの互換図を左右を逆にして重ねてみよう。
f:id:bitterharvest:20170306141459p:plain
この互換図は定数\(Const \ c\)と値\(Identity \ a\)との余積と見ることができる。しかも、余積はファンクタとしての\(Identity\)と\(Const\)により実現されている。

それでは、\(Const \ c\)を\( ( ) \)で置き換えてみよう。
f:id:bitterharvest:20170306141520p:plain
これも余積である。Haskellは余積を\(Either\)で表していたので、これは\(Either \ (Const \ ()) \ (Identity \ a)\)と書くことができる。

これは何かに似ていないだろうか。\(Maybe\)は値を持たないか値を持つかのいずれかであった。値を持たない場合には\(Nothing\)で表し、持つ場合には\(Just \ a\)で表した。そこで、これを今得た\(Either\)に当てはめてみよう。\(Nothing\)を\(Const \ ( )\)と、\(Just \ a\)を\(Identity \ a\)と考えてみよう。相互に表現法が違うだけで同じものであることが分かる。そこで、\(Either \ (Const \ ()) \ (Identity \ a)\)をタイプを用いて次のように\(Maybe'\)で言い換えてみる。

type Maybe' a = Either (Const () a) (Identity a)

少し利用してみよう。変数のデータ型を定めながらの利用になるが以下の様である。

*Main> a = Identity (3 :: Integer)
*Main> b = Right a :: Maybe' Integer
*Main> c = Const () :: Const () Integer
*Main> d = Left c :: Maybe' Integer
*Main> :t a
a :: Identity Integer
*Main> a
Identity 3
*Main> b
Right (Identity 3)
*Main> c
Const ()
*Main> d
Left (Const ())
*Main> :t a
a :: Identity Integer
*Main> :t b
b :: Maybe' Integer
*Main> :t c
c :: Const () Integer
*Main> :t d
d :: Maybe' Integer
*Main> :i a
a :: Identity Integer 	-- Defined at <interactive>:9:1
*Main> :i b
b :: Maybe' Integer 	-- Defined at <interactive>:10:1
*Main> :i c
c :: Const () Integer 	-- Defined at <interactive>:11:1
*Main> :i d
d :: Maybe' Integer 	-- Defined at <interactive>:12:1

このことからも、\(Maybe\)と\(Either\)は同じ概念を表していることが分かる。沢山のファンクタについて説明してきたが、次は反関手の話をする。

関手ー積と余積

プログラマーのための圏論 (圏論とHaskell)

6.7 関手ー積と余積

前回の記事で関手のおさらいをした。一段と理解が深まったことと思う。今回は、再び積と余積について論じよう。前々回では、双関手としての積と余積について述べたが、ここは、この話ではない。

もう一度、積と余積の定義に戻って、そこから関手の世界へと入ることにしよう。

デカルト積は圏論では積の圏として定義され、その互換図は下図のようになっていた。
f:id:bitterharvest:20170228140259p:plain

積の圏には対象\(C\)、射\(p,q\)、対象\(A,B\)が存在し、さらに、一意的な関数\(m=(f, g)\)が存在して、その他の対象\(C'\)に対して、\((f,g): C' \rightarrow C\)となる。
即ち、
1) 積と呼ばれる対象が一つ存在する。これを\(C\)とする。
2) \(C\)には投影(Projection)と呼ばれる二つの射\(p,q\)が存在する。これらは\(C\)をそれぞれ\(A,B\)に投射する。
3) \(C\)以外の任意の対象\(C'\)は\(A,B\)へ投影する射\(p',q'\)を持つ。そして、ただ一つの射\( (f, g) \)が存在し、これは\(p'=p \circ f,q'= q \circ g\)を満たす。

\(C\)が上記を満たす時、これは\(A,B\)の積と呼ばれ\(C=A \times B\)と記される。

これをHaskellで表現する。大文字で表されている対象が、小文字で表される型変数に変わることに注意すると次の図のようになる。
f:id:bitterharvest:20170228140336p:plain

ところで、\(B\)を終対象\(T\)で置き換えよう。次のようになる。
f:id:bitterharvest:20170228140410p:plain

ここで、\(unit\)は終対象への射とする。この結果、\(C\)から\(T\)への射は一意に定まる。同様に、\(C'\)から\(T\)への射も一意に定まる。従って、\(g=unit\)となり、一意に定まる。同様に、\(f\)は\(C\)から\(A\)への射として与えられたものであるため、\(f,g\)は一意に定まる、このため、この図は圏の積となっている。

これをHaskellで描いてみよう。
f:id:bitterharvest:20170228140451p:plain

ところで、積といっているので、算術での掛け算と考えて、\(C=A \times T\)と\(C=A' \times T\)にある\(T\)を1に替えてみよう(\(T\)は一つという意味で\(Unit\)と呼ばれることがある。一つを顕在化し1とする)。互換図は次のようになる。
f:id:bitterharvest:20170228140538p:plain

さらに、\(A \times 1\)は\(A\)と考えてよいだろうから次の互換図を得る。ここで、\( (f,unit) \)は\(f\)となることに注意しよう。
f:id:bitterharvest:20170228140711p:plain

それでは、それぞれの対象は別々の圏\(\mathcal{C,D,E}\)に存在しているとしよう。そして、それらは関手\(Identity,Unit\)により結ばれているものとする。
f:id:bitterharvest:20170228140758p:plain

対象間はデータ型\(Identity,Unit\)で、関数間は\(fmap\)で写像されることを考慮に入れて、Haskellで実装すると以下のようになる(なお、\(Identity\)とその\(fmap\)の実装については次回で述べる)。
f:id:bitterharvest:20170228140846p:plain

さて元々あった積の互換図を重ねてみる。
f:id:bitterharvest:20170228140924p:plain

この図から、\( (a,( ) )\)と\(a\)は同型写像であることが分かる(\( (a,( ) )\)と\(a\)の間の写像エピ射でありモノ射であることを証明すればよい)。即ち、同値というわけではないけれど、同型である。圏論では同型という概念は非常に重要である。それは自然な形で変換できることに起因している。そして、圏論では自然変換を重宝に利用する。

また、余積に対しても同様な互換図を得る。
f:id:bitterharvest:20170228141035p:plain

ここで得た積と余積の概念を発展させるとテンソル積(Tensor Product)の世界へと進むことができる。

市ヶ尾の横穴墓群と古墳群を訪れる

旅行

東京の冬は、寒い寒いと挨拶するときに常套句としてかわすが、本当は過ごしやすい。20年以上も前になるが、隣に住んでいたドイツ人が、東京の冬は素晴らしいといっていた。ドイツの冬はどんよりと曇っていて、夜の帳が下りるのも早いそうだ。

今日は快適な冬の一日、晴天に恵まれ風一つない穏やかな日だったので、近くの古墳時代の遺跡を訪ねてみた。

きっかけをくれたのは、高田寛太さんの『海の向こうから見た倭国』である。
f:id:bitterharvest:20170225160222j:plain
Amazonの宣伝を見て面白そうなので予約購入した本だ。電子版の販売の日(24日)はいつものように朝早く目を覚ました。昨夜の読みかけで枕元にKindleが置いてあったので、もう配布されているかなと期待して開いてみたところ、すでに読める状態になっていた。予想通りなかなか面白い本で、用事の合間を縫いながらではあったが、その日の夕方までには読み終えた。

3世紀前半から6世紀前半までの古墳時代倭国と佳那、百済新羅高句麗の政治的・経済的・文化的交流関係を古墳や副葬品を通して論述している。現在のそれぞれの国という枠組みでこの時代を見てはいけない、朝鮮半島と日本列島の海岸線に沿った流域が一つの文化圏をなしていると思えるほどに豊かな関係にあった、などなどを明らかにしてくれる。優れた本だと思う。

この本を読む前に、森下章司さんの『古墳の古代史』を読んだ。
f:id:bitterharvest:20170225160347j:plain
この本は前方後円墳が発生した背景を中国そして朝鮮半島との相互作用の中から引き出そうと意欲的な試みをしている。ダイアモンドではないけれど、原始社会を考えるときは文化人類学的な視点が必要なのではないかと感じていた時だったので、森下さんの「渦巻」という用語は大変面白かった。この用語は、各地域での社会の集団化と階層化が進む中で、有力者・支配者が生まれ、さらには王や大王へと進展していくということを表している。ダイアモンドも踏襲していた新進化論の流れの中にあるものだ。分かりやすい議論だと思う。

さて、今日訪れた古墳を紹介しよう。訪れた場所は横浜市都筑区市ヶ尾である。ここには、市ヶ尾横穴古墳群と稲荷前古墳群がある。近くを谷本川が流れ、二つの古墳群は対峙する丘の上にそれぞれある。

横穴古墳群は6世紀後半から7世紀後半の古墳時代末期に作られた。農民の中でも階層化が進み、その中の有力な家族がここに埋葬されていると考えられている。古墳群は、A,B二つの群からできている。

A群の墓はこのような感じ。この左右にも同じような墓がある。
f:id:bitterharvest:20170225173035j:plain

横穴はこのような状態になっている。
f:id:bitterharvest:20170225173154j:plain
墓に近付いてみる。
f:id:bitterharvest:20170225173248j:plain
中に入ってみる。壁画が描かれていれば素晴らしいのだが、さすがにそのようなものはない。
f:id:bitterharvest:20170225173320j:plain
別の墓の中に入って外側を見る。
f:id:bitterharvest:20170225173415j:plain

B群の墓も同じような感じである。
f:id:bitterharvest:20170225173515j:plain

墓からの景色はとても素晴らしいようだ。
f:id:bitterharvest:20170225173618j:plain

道路に出て、市ヶ尾小学校越しに写真を撮ってみる。先ほどの絵の様には見事ではないが、丹沢山塊がかすんで見える。
f:id:bitterharvest:20170225173758j:plain

市ヶ尾横穴古墳群から稲荷前古墳群へと向かう途中で、梅が満開だった。
f:id:bitterharvest:20170225174036j:plain

稲荷前古墳群は4世紀後半から7世紀にかけてのこの地域の首長とそれに連なる人々の墓地と考えられている。ここには、古墳の博物館といわれるほどに色々なタイプ(前方後円墳前方後方墳、円墳、方墳)が作られていた。現在は、前方後方墳と方墳二基が残されている。

正方形をした二つの墳丘で構成された前方後方墳を横から見ると
f:id:bitterharvest:20170225165318j:plain
てっぺんに上って見ると
f:id:bitterharvest:20170225165401j:plain
また、てっぺんから付近の景色を見ると
f:id:bitterharvest:20170225165455j:plain

この墳丘からは、底部に孔をあけた壷型土器や器台などが8個体発見されていて、これらの遺物から4世代後期に構築したと考えられている。この墓は、全長37.5m、後方部幅15.5m、前方部幅14.0、くびれ部幅10.0~11.5mである。
f:id:bitterharvest:20170225180453j:plain

前方後方墳は東日本に特徴的にみられる碁制である。その理由については諸説存在する。その中の一つに、倭国と対立していた狗奴国の系譜であるという見方がある。もし、そうだとすると、市ヶ尾も狗奴国と関係のあった地域となり、面白さが増す。

このすぐそばにある方墳では、小学生が子犬と遊んでいた。
f:id:bitterharvest:20170225170511j:plain
この墓は、先ほどの墓よりは新しい時期に作られたことが分かっている。

反対側にももう一つ方墳があった。
f:id:bitterharvest:20170225181249j:plain
これは先に説明した前方後方墳と同様に大量の盛土で作られたことが分かっているそうである。

市ヶ尾横穴古墳群は市が尾駅から10分、稲荷前古墳群は市ヶ尾横穴古墳群から20分ぐらいなのだが、遺跡への入り路が分からずに余分に歩いたこともあり、通算で1万歩を越えた。週末の良い運動になった。

関手―Haskellで関手をどのように理解したらよいか

プログラマーのための圏論 (圏論とHaskell)

6.6 Haskellで関手をどのように理解したらよいか

圏論の中で重要な概念の一つは関手(Functor)だ。そして、Haskellでも最も便利な道具の一つはファンクタである。数回の記事の中で、いくつかの例を挙げながら、圏論での関手を説明してきた。また、それとのつながりの中で、Haskellでのファンクタの使い方についても説明してきた。だいぶ慣れてきたとは思うが、次のステップに行くために、ここでもう一度原点に立ち戻って関手とは何だったのか、ファンクタとは何だったのかをもう一度振り返ることにする。

まず、圏とはという話からしてみよう。圏は構造を持った世界である。構造は簡単に言ってしまうと点の集まりとその間を矢印で結んだものである。数学の用語を用いると点は対象であり、矢印は射である。点と矢印はとても抽象化された世界である。その実例はいろいろなものを考えることができる。

点は個々のものであっても構わないし、集まりであっても構わない。例えば、小学校での学級という世界を考えるときは、点は一人一人の生徒になるであろう。しかし、小学校という世界を考えるときは、点はそれぞれの学級になるであろう。対象が学級となった時は、それを構成している要素である個々の生徒については考えないということになる。さらに進んで、横浜市の小学校という世界になれば、点は小学校ということになり、学級でさえ無視されることとなる。

矢印は点の間の関係を表す。点が学級の場合であればどのような矢印が考えられるであろうか。朝礼の時の並び順は二人の児童の関係を表しているので矢印として利用することができそうだ。同じような意味で成績順なども矢印として利用できそうだ。しかし、圏では二つの矢印は合成できるという約束になっている。このため、二つの点の関係を表しているものでも矢印として利用できないものも存在する。例えば、好きや嫌いを表すような関係は難しい。A君がB君を好きで、B君がC君を好きだとしても、A君がC君を好きだとは限らない。往々にして嫌いなことがある(圏論では矢印はつなげられるのでA君はC君が好きでないと破綻してしまう)。このため、圏論を実際の場面に応用しようとした時、工夫をしないとうまく表せないものもある。

世界を点と矢印で構成したら、二つの圏の構成を比べてみたいと自然に思うようになるだろう。例えば、学級の世界と大人社会の世界を比較したいと思うだろう。学級での児童間での上下関係と大人社会での権力構造とを比較してみようと思うだろう。どうしたらできるだろうか。一つの考え方は、子供の上下関係を大人の権力構造に移すことだろう。うまく移すことができれば、学級でのある構造が大人社会にも内在しているということを発見するであろう。このような役割を担ってくれるのが関手である。

f:id:bitterharvest:20170216082517p:plain

関手をビジュアルに示したのが、上図である。図には二つの圏\(\mathcal{C,D}\)がある。それぞれの圏で、点で表されたのが対象であり、矢印で表されたのが射である。従って、\(\mathcal{C}\)では、点として表されている\(A,B,C\)が対象であり、矢印として表されている\(f,g\)が射である。また、\(f\)と\(g\)を結合した矢印\(g \circ f\)も射である。この他に自身への射、恒等射\(id_A,id_B,id_C\)が存在する。

\(\mathcal{C}\)の構造を移したのが、右側の\(\mathcal{D}\)である。こちらには\(\mathcal{C}\)の構造を移したものしか表示していない。このため、この他にも点や矢印は存在しても構わないものとする。

\(\mathcal{C}\)の構造を\(\mathcal{D}\)に写したものが関手\(F\)である。従って、\(A,B,C\)は\(F(A),F(B),F(C)\)に移される。また、\(f,g,g \circ f\)は\(F(f),F(g),F(g \circ f)\)に移される。さらに、関手には次のようは次のような約束を求めている。結合た射を関手で写像したものは、それぞれの射を関手で写像しそれを結合したものと同値である、即ち、\(F(g \circ f)=F(g) \circ F(f)\)である。即ち、関手で写像する前に結合しても関手で写像した後で結合したとしても同じであるという約束をしている。これは恒等射についても同じである。

関手の定義には、写像(射)を写像するという概念が入り込むので、最初はとっつきにくきもする。しかし、射を写像の集合と見なせば、これまで馴染んできた集合の写像の概念と同じになるのですんなりと受け入れられるようになる(圏では射の集合は\({\rm Hom}(A,B)\)で表す。これは、対象\(A\)から対象\(B\)への射の集合と読む)。

Haskellで関手をどのように利用したらよいのだろうか。Haskellを使っていて便利だなと思うのは、データ型を自由に設定できることだ。プログラムはある応用分野に向けて書くのが普通だ。会計のシステムを作りたいとか、量子力学の問題を解きたいとか、ゲームを作ってみたいとか、それぞれ目的としているところがあると思う。そして、それぞれの応用分野には、それぞれ独自の用語がある。あるいは、それぞれの用語がその世界を規定しているといってもよいと思う。プログラムを書くとき、それぞれの用語を用いて、会計システムであれば会計の用語や約束事を用いて、プログラムを記述できれば読みやすいプログラムを実現することができる。

そのように用意されたプログラミング言語ドメイン固有言語(Domain Specific Language)というが、応用分野ごとにこのような言語を用意するのではたまらない。Haskellの良さは、応用分野に向けたデータ型を開発者が定義することで、ドメイン固有言語が容易に用意できることだ。先ほどらいの関手という概念を用いるならば、Haskellが用意している汎用的な世界を、新たに定義したデータ型が関手として働くことによって、応用分野に移してくれる。このため、開発者はHaskellのプログラミング手法を用いて、ドメイン固有言語が与えられているような感覚で、自然な姿で特定の分野に向けたプログラムを書くことができる。

Haskellでの関手を実装するためのプロトタイプを下図に示す。
f:id:bitterharvest:20170225113706p:plain
Haskellでは射は関数である。また、対象はデータ型と呼ばれる。Haskellのプログラムでは、関数の入力と出力の関係を型シグネチャで表す。入力と出力のそれぞれの値はあるデータ型に属している。しかし、そのデータ型はいくつかの可能性がある場合がある(例えば、加算であれば、整数であることもあるし、分数であることもあるし、小数であることもある)。そこで、可能性がいくつかある場合には変数と見なして小文字で表す(これを型変数という)。このため、圏では対象を大文字で表すのが通例となっているが、Haskellで記述するときは、小文字で表す。

圏論では関手によって写像される先は\(F(A),F(f)\)のように、\(F\)を用いて表していた。しかし、Haskellでは、対象と射の写像を別々に表す。対象はデータ型によって移され、射はクラス(この場合はファンクタを定めているクラス)をインスタンス化することで実現される。図に示したように、前者は

data Type_Constructor = Data_Constructor ..

で、後者は

instance Functor Type_Constructor where
  fmap f = ...

となる。

このテンプレートを用いてMaybeを実装したのが下図である。
f:id:bitterharvest:20170225113720p:plain

この上図でMaybeが型コンストラクタ、NothingとJustがデータコンストラクタである。Maybeの横にあるaを型引数と呼ぶが、aが属する型をMaybeというデータ型の世界に移したのが、ここでの記述である。


それでは、Maybeを定義することで、どのような応用分野が提供されたのであろうか。Maybeが利用される範囲が広すぎて具体的に述べることは難しいのだが、計算の世界で値が定まらなかったときにエラーが生じないような世界を提供したということになるであろうか。次回に話すが、余積の概念を実現したということだ。

関手ー双関手

プログラマーのための圏論 (圏論とHaskell)

6.5 双関手

1)関手としての積と余積

前々回の記事で、Haskellが用意している関手のリストを示した。

Prelude> :i Functor
class Functor (f :: * -> *) where
  fmap :: (a -> b) -> f a -> f b
  (<$) :: a -> f b -> f a
  {-# MINIMAL fmap #-}
  	-- Defined in ・eGHC.Base’
instance Functor (Either a) -- Defined in ‘Data.Either’
instance Functor [] -- Defined in ‘GHC.Base’
instance Functor Maybe -- Defined in ‘GHC.Base’
instance Functor IO -- Defined in ‘GHC.Base’
instance Functor ((->) r) -- Defined in ‘GHC.Base’
instance Functor ((,) a) -- Defined in ‘GHC.Base’

この中で、((->) r)については説明したが、((,) a)と(Either a)については説明しなかった。これらは、圏論での積と余積についてのところで説明した。その時は、一つの圏の中での二つの対象と一つの対象の普遍的な関りを説明する中で述べた。

それでは積の方から説明を始めよう。Haskellでは積は\((a,b)\)と書かれる。常套手段だが、カンマを中置関数と見なして、これを前置関数にすると\((,) \ a \ b\)と書くことができる。このようにすると、\((,) \)は型コンストラクタと見なすことができる。あるいは、一つのデータ型を作り出しているといってよいであろう。データを取り出す手段が、\((,) \)である(同じようなことは関数すべてにいえる。関数は型コンストラクタで、データを取り出す手段である)。

\((,)\)が型コンストラクタであることから、これは関手として利用することが可能である。その例を下図に示す。
f:id:bitterharvest:20170222104958p:plain
ここで、(,)は次のように関手として定義されている。

Instance Functor ((,) a ) where
  fmap (x,y) = (x, f y)

また、Eitherは次のように定義されている。

Instance Functor ((,) a ) where
  fmap (x,y) = (x, f y)

2)関手としての積と余積

関手はある圏からある圏(同じ圏でも構わない)への写像であった。それでは、ドメインが一つの圏ではなくて、二つの圏の場合はどうであろうか。その例を示そう。
f:id:bitterharvest:20170222105012p:plain
この図は、先に説明した積を一般化したものである。積のそれぞれは別々の圏に属す(図では\(\mathcal{C}\)と\(\mathcal{D}\)である)。それぞれから対象が選ばれ、それは別の圏へと写像される(図では\(\mathcal{E}\)である)。

一つの圏からではなく二つの圏(\(\mathcal{C,D}\))からひとつの圏(\(\mathcal{E}\))に写像しているような関手(\(F: \mathcal{C} \times \mathcal{D}\rightarrow \mathcal{E}\))を双関手(Bifunctor)という。これのHaskellでは次のように定義することができる。

class Bifunctor f where
  bifmap :: (a -> b) -> (a' -> b') -> (f a a' -> f b b')

積と余積はこのクラスのインスタンスとして定義することができる。下図には双関手と積の関係を示す。
f:id:bitterharvest:20170222104507p:plain

関手を学ぶ良い機会になるので、積と余積のインスタンスの作成は読者に任せる(双関手の実装はData.Bifunctorを調べると分かる)。

次回はモノイド圏についてである。

関手ー圏の圏

プログラマーのための圏論 (圏論とHaskell)

6.4 圏の圏

圏と圏とをつなぐ射は関手という特別な名前がついているが射であることに変わりはない。従って、二つの関手を合成することもできるはずだ。

図のように、三つの圏\({\mathcal C}\),\({\mathcal D}\),\({\mathcal E}\)を考えてみよう。\({\mathcal C}\)から\({\mathcal D}\)へは関手\(F\)で、\({\mathcal D}\)から\({\mathcal E}\)へは関手\(G\)で写像されているとする。そして、関手の合成\(G \circ F\)が存在するとしよう。
f:id:bitterharvest:20170221160425p:plain

また、\({\mathcal C}\),\({\mathcal D}\),\({\mathcal E}\)には自身を自身に写像する恒等な関手\(id_{\mathcal C}\),\(id_{\mathcal D}\),\(id_{\mathcal E}\)があるとしよう。

さらに結合律、単位律が成り立っているとする。

このような関手を射とし圏を対象にすると、次に示すように圏の条件を満たしていることが分かる。

1) 対象\({\mathcal C}\),\({\mathcal D}\),\({\mathcal E}\)を有する。
2) 射\(F,G\)を有する。
3) 射はドメインとコドメインを有する。即ち、\(F: {\mathcal C} \rightarrow {\mathcal D},G: {\mathcal D} \rightarrow {\mathcal E}\)
4) すべての対象に対して恒等射\(id_{\mathcal C}\),\(id_{\mathcal D}\),\(id_{\mathcal E}\)が存在する。
5) コドメインドメインが一致している射は合成でき、それも射となる。即ち、\(G \circ F\)

前回の記事で、リストを定義した。そこでは、リストはConsが何度も繰り返し現れ、リストの要素が見にくかった。Haskellでは構成要素とその順番がすぐにわかるように、リストを[a,b,c,… ]と表している。これは次のように定義されている。

data [ ] a = [ ] | a : [a]
instance Functor [ ] where
  fmap :: (a -> b) -> [a] -> [b]

このリストに対しては、最初の要素を取り出すheadと最初の要素を取り除いたリストを返すtailという関数が用意されている。

これを利用してみよう。

Prelude> let a = [1,2,3]
Prelude> head a 
1
Prelude> tail a
[2,3]
Prelude> tail . tail $ a
[3]
Prelude> tail . tail . tail $ a
[]
Prelude> tail . tail . tail . tail $ a
*** Exception: Prelude.tail: empty list
Prelude> head . tail . tail $ a
3
Prelude> head . tail . tail . tail $ a
*** Exception: Prelude.head: empty list

空のリストにheadとtailを施すとエラーとなる。これを避けるために、次の関数を用意しよう。

safeTail :: [a] -> Maybe [a]
safeTail [] = Nothing
safeTail (x:xs) = Just xs

safeHead :: [a] -> Maybe a
safeHead [] = Nothing
safeHead (x:xs) = Just x

この関数は、関手[ ]の後に、関手Maybeを施したもので、関手を結合したものである。
それでは利用してみよう。

*Main> let a = [1,2,3]
*Main> tail a 
[2,3]
*Main> tail .tail $ a 
[3]
*Main> tail .tail . tail $ a 
[]
*Main> tail .tail . tail . tail $ a 
*** Exception: Prelude.tail: empty list
*Main> safeTail .tail . tail . tail $ a 
Nothing
*Main> head a
1
*Main> head . tail $ a
2
*Main> head . tail . tail $ a
3
*Main> head . tail . tail . tail $ a
*** Exception: Prelude.head: empty list
*Main> safeHead . tail . tail . tail $ a
Nothing
*Main> 

\({\mathcal C}\)の射\(f\)は\(F(f)\)で\({\mathcal D}\)の射\(g\)に写像されているとする。さらに、\(g\)は\(G(g)\)で\({\mathcal E}\)の射\(h\)に写像されているものとする。

この時、\(G \ circ F (f) = G (F (f))\)となる。

それでは、Haskellでのfmapはどのようになるであろうか。下図を参考にしながら求めてみよう。
f:id:bitterharvest:20170221160859p:plain

g=fmap f
h=fmap g

より、

h=fmap (fmap f)
 = (fmap . fmap) f

となる。

それでは、少し実行してみよう。fを(+3)にして確認する。

Prelude> f = (*3)
Prelude> h = (fmap .fmap) f
Prelude> m = Just [1,2,3]
Prelude> h m
Just [3,6,9]

それでは、fを2乗する関数にして確認してみよう。

Prelude> f x = x * x
Prelude> h m
Just [3,6,9]
Prelude> h = (fmap . fmap) f
Prelude> m = Just [1,2,3]
Prelude> h m
Just [1,4,9]

次は双関手(Bifunctor)について述べる。

関手ー一般化

プログラマーのための圏論 (圏論とHaskell)

6.3 一般化

Maybeを利用して関手を説明したが、その他にもいろいろな関手を考えることができる。それらは(Maybeで説明した)fmapの実装が異なるだけだ。Javaを知っている人であればインターフェースを用いて実装したらと考えるだろう。Haskellにもオブジェクト指向と同じ概念のものが用意されている。Haskellでは、関手はクラスで一般化し、個々の実体はそのインスタンスで表現できる。

それでは実際に示してみよう。次のようになる。

Class Functor f where
  fmap :: (a -> b) -> (f a -> f b)

上記のプログラムで、fが関手である。Haskellでは型コンストラクタとなる。
なお、GHCでの定義を見ると次のようになっている。

Prelude> :i Functor
class Functor (f :: * -> *) where
  fmap :: (a -> b) -> f a -> f b

f aとf bがカッコでくくられていないが、これをカーリー化すると(f a -> f b)になるので、表現は異なるが内容は同じである。

これを用いると、Maybeはクラスをインスタンス化し、次のように実装できる。

data Maybe a = Nothing | Just a deriving (Eq, Show, Read)
instance Functor Maybe where
  fmap _ Nothing = Nothing
  fmap f x = Just (f x)

これまで、fmap f Nothing = Nothingと書いてきたが、どのようなfが来たとしてもNothingを出力するので、ここではfの代わりに_を用いた。
プログラムを実行してみよう(実装されているMaybeとぶつかるようであれば、Maybe’, Just’, Nothing’のように’をつけて実装し、実行して欲しい)。

*Main> fmap (+3) (Just 5)
Just 8
*Main> fmap (+3) Nothing
Nothing

それではリストはどうであろうか。Maybeを参考にしながら実装しよう。

data List a = Nil | Cons a (List a) deriving (Eq, Show, Read)
instance Functor List where
  fmap _ Nil = Nil
  fmap f (Cons h t) = Cons (f h) (fmap f t)

上のプログラムで、Cons h tと書いたが、hはリストの最初の要素、tはこれを取り除いたリストである。

プログラムを実行してみよう。

*Main> fmap (+3) (Cons 3 (Cons 4 (Cons 5 Nil)))
Cons 6 (Cons 7 (Cons 8 Nil))

Haskellが用意しているFunctorのインスタンスを調べてみよう(厳密にはGHCが用意しているインスタンス)。

Prelude> :i Functor
class Functor (f :: * -> *) where
  fmap :: (a -> b) -> f a -> f b
  (<$) :: a -> f b -> f a
  {-# MINIMAL fmap #-}
  	-- Defined in ・eGHC.Base’
instance Functor (Either a) -- Defined in ‘Data.Either’
instance Functor [] -- Defined in ‘GHC.Base’
instance Functor Maybe -- Defined in ‘GHC.Base’
instance Functor IO -- Defined in ‘GHC.Base’
instance Functor ((->) r) -- Defined in ‘GHC.Base’
instance Functor ((,) a) -- Defined in ‘GHC.Base’

上記に示すような結果を得たことと思う。
ところで下から2行目に見慣れないものがある。((->) r)なのだが、これはリーダーと呼ばれる。それではこのリーダーについて説明しよう。

Haskellでは、関数は\(a \rightarrow b\)と記述される。\(a\)が入力で\(b\)が出力である。ところで、\( \rightarrow \)を\(+\)や\(\times\)などと同じように中置関数と考えると、これを前置関数に変えることで\( (\rightarrow) \ a \ b \)と表すことができる。

そこで、\( (\rightarrow) \ a \ b \)は、\(a\)を\(b\)に変換してくれる型コンストラクタと解釈することが可能となる。従って、

type Reader a = (->) a

と表すことが可能となる。
あるいは、両辺から\(a\)を取り除いて

type Reader = (->)

と表しても構わない。これで、\( (\rightarrow) \)は型コンストラクタとなった。ここでは、それを\(Reader\)というシノニムで置き換えている。

ところで、次の図を考えよう。
f:id:bitterharvest:20170218180104p:plain
図で左側は関数\(f:\)でそのドメインは\(a\)でありコドメインは\(b\)である。今、これら\(a,b\)を、右側に示すように、\(r\)をドメインにし、そのコドメインに持ち上げてしまおう。\(a\)を\(g:r \rightarrow a\)に写像する関数は、\(Reader \ r \ a\)と表すことができる。

それでは、\(b\)を\(r \rightarrow b\)に移す関数はどうなるであろうか。\(b\)を関手\(Reader \ r\)を用いて、\(r \rightarrow b\)に写像する。そして、\(r \rightarrow b\)は射である。関手を射に写像するときは\(fmap\)を用いていた。そこで、\(fmap \ (Reader \ r) \)と考えられる。

これでよさそうなのだが、何となくすっきりとしない。そこで、Haskellでの互換図ではなく、圏論での互換図で表してみることにしよう。
f:id:bitterharvest:20170220104235p:plain

上記の互換図で、\({\rm Hom}(R,A)\)は、対象\(R\)から\(A\)への射の集合である。また、\({\rm Hom}(R,\_)\)は\(R\)をドメインとする射の集合である。\(A\)から射の集合\({\rm Hom}(R,A)\)への射の集合は\({\rm Hom}(R,\_)\)となる。

次に、\(R\)から\(B\)への写像を考えてみよう。これは、\(\mathcal {D}\)のところの互換図を用いればよい。(上側の)\(R\)から\(A\)を経由して\(B\)にいたる射の集合を求めると\({\rm Hom}(R,A) \times {\rm Hom}(A,B)\)となる。同じように、(上側の)\(R\)から(下側の)\(R\)を経由して\(B\)にいたる射の集合を求めると\({\rm Hom}(R,R) \times {\rm Hom}(R,B)={\rm Hom}(R,B)\)となる。これが先に求めたものと等しいので、\({\rm Hom}(R,B)={\rm Hom}(R,A) \times {\rm Hom}(A,B)\)となる。

そこで、\(B\)から\({\rm Hom}(R,B)\)への射の集合は、今求めた\({\rm Hom}(R,B)={\rm Hom}(R,A) \times {\rm Hom}(A,B)\)から\(B\)を\(\_\)に代えればよいので、\({\rm Hom}(R,\_)={\rm Hom}(R,A) \times {\rm Hom}(A,\_)\)となる。

少し長くなったが、\(fmap \ (Reader \ r) \)でよいことが判明した。

従って、\(fmap\)のリーダーに対する実装は次のようになる。

type Reader = (->)
instance Functor (Reader r) where
  fmap :: (a -> b) -> (r -> a) -> (r -> b)
  fmap f g = f . g

ここで、f.g は(.) f gと表すことができ左右の辺からf,gを消去すると最終的には次のようになる。

type Reader = (->)
instance Functor (Reader r) where
  fmap :: (a -> b) -> (r -> a) -> (r -> b)
  fmap= ( . )

上記のプログラムをロードするとUse TypeSynonymInstancesとエラーが出る。そこで、これを用いて再度ロードするとファンクタが二重定義であるというエラーが出る。これは、Haskellが(->)のファンクタを用意しているためである。従って、Haskellがあらかじめ用意しているものをここでは用いる。Haskellではどのようになっているかをまず、見てみよう。データ型の定義は次のようになっている。

Prelude> :i (->)
data (->) t1 t2 	-- Defined in ‘GHC.Prim’

しかし、GHC.Primを参照してもこのデータ型の定義は見当たらない。ファイクコードだそうだ。これは表示のためだけに使われているそうである。
しかし、ファンクタの方はちゃんと定義されている。Data.Functorを見ると次のようになっている。

instance Functor ((->) r) where
    fmap = (.)

システムが用意しているものを実際に使うとこんな感じになる。あまり面白くはない。

Prelude> ((+3) . (*4)) 5
23
Prelude> ((+3) . (+4)) 6
13

次回は、圏から圏を作ることを説明する。

関手ー関手であることの証明

プログラマーのための圏論 (圏論とHaskell)

6.2 関手の証明

かつてバークレイの大学院生だった頃に指導教授からプログラムの正当性を研究テーマにしてみないかと誘いを受けたことがある。当時のプログラミング言語と言えばFortlanで、構造がぐしゃぐしゃなプログラムを検証することなど不可能だと直感的に感じて断った経験がある。

関数型言語を使えるようになった今日ではプログラムの検証は随分と簡単になった。今回の記事で紹介するのもその一つである。Maybeが関手であること、即ち、構造を保持していることを証明しよう。

圏の定義を確認しておこう。
1) 対象\(A,B,C,..\)を有する。
2) 射\(f,g,h,..\)を有する。
3) 射はドメインとコドメインを有する。これらは対象である。
4) すべての対象に対して恒等射が存在する。
5) コドメインドメインが一致している射は合成でき、それも射となる。
さらに、圏は次の二つの法則を満たさなければならない。
①  結合律。
②  単位律。

さらに、関手についても確認しておこう。圏論での関手の互換図は次のようである。
f:id:bitterharvest:20170217084834p:plain

この図で重要なところは、構造を保持しているところで、それらは、
\begin{eqnarray}
F(id_A)=id_{F(A)} \\
F(id_B)=id_{F(B)} \\
F(id_C)=id_{F(C)} \\
F(g \circ f) = F(g) \circ F(f)
\end{eqnarray}
である。

Haskellで、関手を定義するときは、上記が成り立っているかどうかを確認しなければならない。プログラムの方は検証をしてくれないので、検証は開発者の責任となる。

それでは、Maybeが構造を保持しているかどうかを証明することにしよう。
Maybeの互換図は次のようになっていた。
f:id:bitterharvest:20170217090107p:plain
証明すべき項目は以下のとおりである。
\begin{eqnarray}
fmap \ id_a = id_{Maybe \ a} \\
fmap \ id_b = id_{Maybe \ b} \\
fmap \ id_c = id_{Maybe \ c} \\
fmap \ (g \circ f) = fmap \ g \circ fmap \ f
\end{eqnarray}
である。

それでは証明に移ろう。fmapは次のように定義していた。

fmap :: (a -> b) -> (f a -> f b)
fmap f Nothing = Nothing
fmap f (Just x) = Just (f x)

である。

ここで、先ほどから使用している\(a,b,c\)は型変数である。前の記事では言葉で説明したが、数学的に記述すると次のようになる。対象の集まりを\(\mathcal {O} = {A,B,C,…}\)とする。型シグネチャのところで\((a -> ...)\)と現れるが、このときの\(a\)は\(\forall a,b,c \in \mathcal {O} \)の意味である。\(\forall\)は全称記号で「任意の」という意味である。即ち、\(a\)は、\(\mathcal {O}\)の要素\(A,B,C,..\)のどれに対してもということになる。

そこで、\(fmap \ id_a = id_{Maybe \ a}\)を証明することとしよう。いまidを次のように定義する。

id :: a -> a
id x = x

上の定義のfをidで置き換えると

fmap id Nothing = Nothing
fmap id (Just x) = Just (id x)

idの定義より以下が成り立つ。

id Nothing = Nothing

CやJavaなどの逐次型プログラミング言語では=は代入式であるが、純関数型言語Haskellでは=は等価、即ち==である。プログラムで確認してみよう。

Prelude> :t id
id :: a -> a
Prelude> id 3 == 3
True
Prelude> 3 == id 3
True
Prelude> id (Just 5) == Just 5
True
Prelude> Just 5 == id (Just 5)
True

従って、左辺を右辺で、右辺を左辺で置き換えることが可能である。そこで、Nothingをid Nothingで置き換えると、

fmap id Nothing = Nothing = id Nothing
fmap id (Just x) = Just (id x)

つぎに、2番目の式についても変形してみよう。

id x = x

より、

fmap id Nothing = Nothing = id Nothing
fmap id (Just x) = Just x

また、

id (Just x) = Just x

より、Just xをid (Just x)で置き換えると次のようになる。

fmap id Nothing = Nothing = id Nothing
fmap id (Just x) = id (Just x)

それでは次の\(fmap \ (g \circ f) = fmap \ g \circ fmap \ f\)を証明しよう。

fmap (g . f) Nothing = Nothing
fmap (g . f) (Just x) = Just ((g . f) x)

原理は先ほどと同じなので、式の変形だけを示そう。最初の式は、

fmap (g . f) Nothing = Nothing
                     = fmap g Nothing
                     = fmap g (fmap f Nothing)
                     = ((fmap g) . (fmap f)) Nothing

最後の式は、

fmap (g . f) (Just x) = Just ((g . f) x)
                      = Just (g (f x))
                      = fmap g (Just (f x))
                      = fmap g (fmap f (Just x))
                      = ((fmap g) . (fmap f)) (Just x)

これにより、Maybeが関手の条件を満たしていることが証明できた。

次回は、fmapを一般化する。

関手ー定義

プログラマーのための圏論 (圏論とHaskell)

6.関手

関手は圏論の中で最も重要な概念である。圏論では自然変換(Natural Transformation)が重要であるが、これの根幹をなすのが関手である。

6.1 関手の定義

圏論は数学的な構造を対象としての点と対象を結ぶ射としての矢印で表している。二つの圏があった時に、片方の構造を他方のそれに写像するのが関手である(注意:集合はいわゆる写像を有しないので、恒等射のみを有する圏である。このような圏は離散圏(Discrete Category)と呼ばれる)。

例を挙げて説明しよう。今、二つの圏\(\mathcal{C}\)と\(\mathcal{D}\)があり、前者は対象\(A,B\)と射\(f:A \rightarrow B\)と恒等射\(id_A,id_B\)で構成されているとする。関手\(F\)は前者の構造を後者に写像する。すなわち、図に示すように \(\\\)

\(A,B\)を\(F (A),F (B)\)に、\(\\\)
\(f:A \rightarrow B\)を\(F (f): F (A) \rightarrow F (B)\)に、\(\\\)
\(id_A,id_B\)を\(F (id_A),F (id_B)\)に写像する。
f:id:bitterharvest:20170216082500p:plain
この時、\(\mathcal{D}\)での対象\(F (A)\)と\(F (B)\)に対する恒等射\(id_{F(A)}\)と\(id_{F(B)}\)はそれぞれ\(F (id_A)\)と\(F (id_B)\)であることに注意して欲しい。

射\(f\)を関手\(F\)で写像するということが理解しにくいかと思う。\(A\)から\(B\)への射は一つとは限らない。複数あっても構わない。そこで、これらを集合と見なすことができる。そこで、\(A\)から\(B\)への射の集合を\({\rm HOM}(A,B)\)と記述する。もし、圏を明記する必要があるときは、\({\rm HOM}\)に添え字で圏の名前を付す。例えば、\({\rm HOM}_\mathcal{C} (A,B)\)とする。このようにすると\(F (f): {\rm HOM}_\mathcal{C} (A,B) \rightarrow {\rm HOM}_\mathcal{D} (F (A),F (B))\)となる。これは集合から集合への写像なので、通常の関数の概念と同じになるので、理解しやすいと思う。

集合から集合への写像なので、単射(Injective)であるのか全射(Surjective)であるのかが気になるが、関手はこれらの性質を問わない。単射であってもそうでなくても構わない。即ち1対1対応である必要はない。また、全射であってもそうでなくても構わない。即ち、写像される側のすべての要素に写像される必要はない。但し、関手が単射であるとき忠実(Faithful)関手といい、全射であるとき充満(Full)関手という。

圏の構造の一つの特徴は、射の結合である。そこで結合を伴う圏の関手を考えることにしよう。圏\(\mathcal{C}\)は対象\(A,B,C\)と射\(f:A \rightarrow B, g:B \rightarrow C \)と恒等射\(id_A,id_B,id_C \)で構成されているとする。射は結合できるので、\(g \circ f:A \rightarrow C \)が存在する。この構造を、図に示すように、関手\(F\)で圏\(\mathcal{D}\)に写像することを考えよう。
f:id:bitterharvest:20170216082517p:plain
\(A,B,C\)は\(F (A),F (B),F (C)\)に、 \(\\\)
\(f:A \rightarrow B\)と\(g:B \rightarrow C \)は\(F (f): F (A) \rightarrow F (B)\)と\( F (g): F (B) \rightarrow F (C) \)に、 \(\\\)
\(id_A\)と\(id_B\)と\(id_C\)は\(F (id_A)\)と\(F (id_B)\)と\(F (id_C) \)にそれぞれ写像される。

また、\(g \circ f:A \rightarrow C \)は\(F ( (g \circ f) ): F (A) \rightarrow F (C) \)に写像される。一方、\(F (f)\)と\(F (g)\)は結合できるので、これは\(F (g) \circ F (f): F (A) \rightarrow F (C) \)となる。圏論では、構造を保持する必要があるので、\(F (g \circ f)= F (g) \circ F (f)\)となる。

関手のいくつかの例を挙げてみよう。

最初の例はシングルトンだけから成り立つ圏からの関手である。これは相手側の対象を一つ選択する件である。
f:id:bitterharvest:20170216082535p:plain
次の例は、定関手(Constant Functor)と呼ばれるものである。すべての対象が一つの対象に写像される。また、すべての対象が恒等射に写像される。
f:id:bitterharvest:20170216085305p:plain
最後の例は自己関手(Endofunctor)と呼ばれる。プログラミング言語もこの例の一つである。

それではHaskellのプログラムで関手を使ってみよう。Haskellでは対象は型としてあらわされる。また、型シグネチャを用いて、入力されるデータの型や出力されるデータの型を示す。この時、型はその時の状況によって決まることが多いので、通常は、型そのもので表さず、型変数というものを用いる。実際に関数を利用するときに、型変数が型にバインディングされる。

Maybeという型を考えることにする。これは次のように定義する。

data Maybe a = Nothing | Just a

最初の図をHaskellの流儀で表したものが次の図である。
f:id:bitterharvest:20170217081652p:plain
この図では、\(F\)は対象に対しては\(Maybe\)を、射に対しては\(fmap\)を用いている。また、対象は型変数となるので小文字で書いてある。それでは、関手を定義してみよう。

fmap :: (a -> b) -> (Maybe a -> Maybe b)
fmap f Nothing = Nothing
fmap f (Just x) = Just (f x)

プログラムを作って実行してみよう。Maybeは用意されているので、これとの混同を避けるために、新しく定義するMaybeには句読点をつけて定義しよう。即ち次のようにする。

data Maybe' a = Nothing' | Just' a deriving (Eq, Show, Read)

fmap' :: (a -> b) -> (Maybe' a -> Maybe' b)
fmap' f Nothing' = Nothing'
fmap' f (Just' x) = Just' (f x) 

実行してみよう。

Prelude> :load "maybe.hs"
[1 of 1] Compiling Main             ( maybe.hs, interpreted )
Ok, modules loaded: Main.
*Main> fmap' (+3) (Just' 4)
Just' 7
*Main> fmap' (++ "!!") (Just' "Happy")
Just' "Happy!!"

Maybeという関手を定義したが、これが関手であるためには、構造を保持していなければならない。次の記事では構造が保たれていることを示すことにしよう。

圏論での積と余積―代数的データ型

プログラマーのための圏論 (圏論とHaskell)

5.6 代数的データ型

引き続き、Bartosz Milewskiの動画を元に、話を進める。

1) 乗算(Multiply)

デカルト積の圏について、前々回の記事で説明したが、積と名前がついているので、四則演算での乗算とかかわりがありそうである。
乗算\(\times\)は、交換律(Commutative Property)、結合律(Associative Property)、単位元(Identity Element)の存在、ゼロの存在(Property of Zero)という性質を持つ。

デカルト積の圏にもこれらの性質を持たすことができれば、このような性質を持った圏と乗算の圏は同じ構造の圏になりそうだ。そこで、これらの性質を持たせるように工夫してみよう。
デカルト積の圏で\((a,b)\)と表されるものは、乗算では\(a \times b \)と表されるものとする。
次は交換律である。値の順序を入れ替えても結果は同じという性質なので、デカルト積の圏の方には、\(mswap\)という射を用意する。即ち、
\begin{eqnarray}
mswap \ p = (snd \ p, fst \ p)
\end{eqnarray}

次は結合律である。計算の順番によらないという性質なので、デカルト積の圏の方には、\(massoc,massoc\_inv\)という射を用意する。即ち、
\begin{eqnarray}
massoc \ ( (x,y),z) = (x, (y,z) ) \\
massoc\_inv \ ( x,(y,z) ) = ( (x, y ),z )
\end{eqnarray}

また、デカルト積の圏では1は()に対応させることとする。従って、単位元に対する演算\(a \times 1 = a\)と\(a =a \times 1\)は、\(munit, munit\_inv\)で表すと次のようになる。
\begin{eqnarray}
munit \ (x,() )= x \\
munit\_inv \ x = (x,( ) )
\end{eqnarray}

さらに、0は\(Void\)に対応させることとする。演算\(a \times 0 = 0\)は、\(mzero\)で表すと次のようになる。
\begin{eqnarray}
mzero :: (a,Void ) \rightarrow Void
\end{eqnarray}
ただし、型コンストラクタ\(Void\)は次に示すように値コンストラクタを有しない。このため、関数は値コンストラクタを用いて定義されるので、シグネチャは定義できるが、その関数は定義できない(前後が逆になるが、型コンストラクタ、値コンストラクタについてはすぐ後で説明する)。

Prelude> import Data.Void
Prelude Data.Void> :i Void
data Void 	-- Defined in ‘Data.Void’

これまでの説明をまとめたのが、以下の表である。

規則積の圏(Haskell)乗算
解釈\((a,b)\)\(a \times b \)
交換律\(mswap :: (a, b) \rightarrow (b, a) \\ mswap \ p = (snd \ p, fst \ p)\)\(a \times b = b \times a \)
結合律\(massoc :: ( (a,b),c) \rightarrow (a, (b,c) ) \\ massoc \ ( (x,y),z) = (x, (y,z) ) \)\((a \times b) \times c = a \times (b \times c) \)
\(massoc\_inv :: ( a,(b,c) ) \rightarrow ( (a, b),c ) \\ massoc\_inv \ ( x,(y,z) ) = ( (x, y ),z ) \)\(a \times (b \times c) = (a \times b) \times c \)
単位元\(munit :: (a,() ) \rightarrow a \\ munit \ (x,() )= x\)\(a \times 1 = a \)
\(munit\_inv :: a \rightarrow (a,() ) \\ munit\_inv \ x = (x,( ) )\)\(a = a \times 1 \)
ゼロ\(mzero :: (a,Void ) \rightarrow Void \)\(a \times 0 = 0 \)

これをHaskellのプログラムとして実装してみよう。

import Data.Void

mswap :: (a,b) -> (b,a)
mswap p = (snd p, fst p)

massoc :: ((a,b),c) -> (a,(b,c))
massoc ((x,y),z) = (x,(y,z))

munit :: (a,()) -> a
munit (x,()) = x

munit_inv :: a -> (a,())
munit_inv x = (x,())

--mzero :: (a, Void) -> Void

少し、利用してみよう。

Prelude> :load "product.hs"
[1 of 1] Compiling Main             ( product.hs, interpreted )
Ok, modules loaded: Main.
*Main> mswap (3,4)
(4,3)
*Main> massoc ((3,4),5)
(3,(4,5))
*Main> massoc_inv (6,(7,8))
((6,7),8)
*Main> munit (4,())
4
*Main> munit_inv 5
(5,())

2) 加算(Sum)

次は余積の圏だ。余積は和と書かれることもあるので、加算と関係があるはずだ。
余積の圏は\(Either \ a \ b \)と記述していたが、これを\(a+b\)と思うことにしよう。+の左側にはaがあって、右側にはbがあると思うことにする。このようにすると、
加算が有する、交換律、結合律、単位元の存在などの性質は乗算の時と同じように、余積の圏に持たせることができる。

交換律は射\(sswap\)で表すことにすると次のようになる。\(mswap\)とは異なり単純な関数では済まない。左側\(Left\)の値が来た場合と右側\(Right\)の値が来た場合に応じて、計算の仕方を変える必要がある。
\begin{eqnarray}
sswap \ (Left \ x) = Right \ x \\
sswap \ (Right \ x) = left \ x
\end{eqnarray}

次は交換律である。交換律では3個の値を使うことになるので、対(ペア)のデータ型だけでは結果を表すことができない。そこで、新しいデータ型を用意する。

data Tripple a c b= Left' a | Middle' c | Right' b deriving (Eq, Show, Read)

これを用いると結合律の射\(asspc, assoc\_inv \)は次のように定義できる。
\begin{eqnarray}
sassoc (Left \ x) = Left' \ x \\
sassoc (Right \ (Left \ x) ) = Middle' \ x \\
sassoc (Right \ (Right \ x) ) = Right' \ x \\
sassoc\_inv (Left \ (Left \ x) ) = Left' \ x \\
sassoc\_inv (Left \ (Right \ x) ) = Middle' \ x \\
sassoc\_inv (Right \ x) = Right' \ x
\end{eqnarray}

加算の時の単位元は0である。余積の圏でも0をVoidで表すことにする。単位元に関連する演算\(sunit,sunit\_inv\)は、シグネチャだけになり、次のようになる。
\begin{eqnarray}
sunit :: Either \ a \ Void \rightarrow a \\
sunit\_inv :: a \rightarrow Either \ a \ Void
\end{eqnarray}

\(Either \ a \ Void\)の解釈だが、左側からはaという値が取り出せる。しかし、右側からは何も出てこない。従って、二つを足し合わせると、aになるというものだ。

これらを表にまとめると次のようになる。

規則余積の圏(Haskell)乗算
解釈\(Either \ a \ b\)\(a + b \)
交換律\(sswap :: Either \ a \ b \rightarrow Either \ b \ a \\ sswap \ (Left \ x) = Right \ x \\ sswap \ (Right \ x) = left \ x \)\(a + b = b + a \)
結合律\(sassoc :: Either \ a \ (Either \ c \ b) \rightarrow Tripple \ a \ c \ b \\
sassoc (Left \ x) = Left' \ x \\
sassoc (Right \ (Left \ x) ) = Middle' \ x \\
sassoc (Right \ (Right \ x) ) = Right' \ x\)
\((a + c) + b = a + (c + b) \)
\(sassoc\_inv :: Either \ (Either \ a \ c) \ b \rightarrow Tripple \ a \ c \ b \\
sassoc\_inv (Left \ (Left \ x) ) = Left' \ x \\
sassoc\_inv (Left \ (Right \ x) ) = Middle' \ x \\
sassoc\_inv (Right \ x) = Right' \ x \)
\(a + (c + b) = (a + c) + b \)
単位元\(sunit :: Either \ a \ Void \rightarrow a\)\(a + 0 = a \)
\(sunit\_inv :: a \rightarrow Either \ a \ Void \)\(a = a + 0 \)

Haskellのプログラムで記述してみよう。次のようになる。

import Data.Void

data Tripple a c b= Left' a | Middle' c | Right' b deriving (Eq, Show, Read)
 
sswap :: Either a b -> Either b a
sswap (Left x) = Right x
sswap (Right x) = Left x

sassoc :: Either a (Either c b) -> Tripple a c b
sassoc (Left x) = Left' x
sassoc (Right (Left x)) = Middle' x
sassoc (Right (Right x)) = Right' x 

sassoc_inv :: Either (Either a c) b -> Tripple a c b
sassoc_inv (Left (Left x)) = Left' x
sassoc_inv (Left (Right x)) = Middle' x 
sassoc_inv (Right x) = Right' x

--sunit :: Either a Void -> a
--sunit_inv :: a -> Either a Void

実行してみよう。

Prelude> :load "coproduct.hs"
[1 of 1] Compiling Main             ( coproduct.hs, interpreted )
Ok, modules loaded: Main.
*Main> let a = Left 3
*Main> let b = Right 4
*Main> sswap a
Right 3
*Main> sswap b
Left 4
*Main> let c = Right (Left 5)
*Main> let d = Right (Right 6)
*Main> sassoc a
Left' 3
*Main> sassoc c
Middle' 5
*Main> sassoc d
Right' 6
*Main> let e = Left (Left 7)
*Main> let f = Left (Right 8)
*Main> sassoc_inv e
Left' 7
*Main> sassoc_inv f
Middle' 8
*Main> sassoc_inv b
Right' 4

3) 分配律(Distributive Property)

加算と乗算が出てきたので、分配律についても確認しよう。これは\(a \times ( b + c) = a \times b + a \times c \)である。従って、()と\(Either\)を用いて次のように表すことができる。

規則積・余積の圏(Haskell)乗算と加算
分配律\(distr :: (a, Either \ b \ c) \rightarrow Either \ (a, b) \ (a, c) \\ distr \ (x, Left \ y) = Left \ (x, y) \\ distr \ (x, Right \ y) = Right \ (x, y) \)\(a \times ( b + c) = a \times b + a \times c \)

プログラムで示すと以下のようになる。

distr :: (a, Either b c) -> Either (a, b) (a, c)
distr (x, Left y) = Left (x, y)
distr (x, Right y) = Right (x, y)

実行してみよう

*Main> let a = 3
*Main> let b = Left 4
*Main> let c = Right 5
*Main> distr (a, b)
Left (3,4)
*Main> distr (a, c)
Right (3,5)

4) Haskellのデータ型の定義

Haskellでは、プログラマが新しいデータ型を作成することを許している。dataというキーワードの後に型コンストラクタを書く。その後、=を書き、それに続けて値コンストラクタを記述する。例えば、\(x,y\)座標の点を表したいときは、

Prelude> data Point = P Float Float

とする。\(a=(3.1, 2.5)\)および\(b=(5.6, -2.4)\)を作りたいのであれば次のようにする。

Prelude> let a = P 3.1 2.5
Prelude> let b = P 5.6 (-2.4)
Prelude> :t a
a :: Point
Prelude> :t b
b :: Point

あるいはレコードを用いて次のようにも定義できる。

Prelude> data Point = P {x::Float, y::Float} deriving (Eq, Show, Read)
Prelude> let a = P {x=3.1, y=2.5}
Prelude> let b = P {x=5.6, y=(-2.4)}
Prelude> :t a
a :: Point
Prelude> :t b
b :: Point

5) 代数方程式からのデータ型の定義

さて、今回のメインディッシュである代数的データ型の話に移ろう。

\(l(a) = 1 + a \times l(a) \)という代数方程式を考えよう。

これは、\(l(a) = \frac{1}{1-a} \)となるので、
\(l(a) = \sum_{i=0}^{\infty} a^i = 1 + a + a^2 + a^3 + a^4...\)
を得る(これは良く知られた公式であるが、実際に求めたければ、割り算をするとよい)。

これは、加算と乗算の形で表されているが、まず、aのべき乗のところを、1が()になることに注意して、タプルに代えてみよう。
\(l(a) = () + a + (a,a) + (a,a,a) + (a,a,a,a) + ...\)
次に、+の部分を\(Either\)で変えてみよう。
\(l(a) = Either \ () \ (Either \ a \ (Either \ (a,a) \ (Either \ (a,a,a) \ (Either \ (a,a,a,a)....\)
なんと、上の式は全てのタプルを表している(但し、後で説明するが、構成要素のデータ型は同じである)。

ところで、上の式で用いられている\(a\)について若干説明する。ここでの\(a\)は型変数と呼ばれるものである。データ型には、\(Int, Float, Char, Tuple\)など、あるいは自身で作ったものもあるが、型変数は、データ型を値とする変数である。従って、\(a=Int\)であれば、\((a,a,a)\)は\((Int,Int,Int)\)となり、整数を三つ組みとするタプルである。また、\(a=String\)であれば、文字列を三つ組みとするタプルである。

さて、\(l(a) = 1 + a \times l(a) \)は型変数\(a\)で作られるデータ型の構造を示す代数方程式と思うことにしよう。左辺の方はデータ型を示し、右辺の方はデータ型の作り方を示しているものとする。
\(l(a)\)は型変数を\(a\)を有するデータ型Listとしよう。即ち、Listは型コンストラクタである。

data List a

右辺の\(+\)は\(Either\)の英語での意味、即ちどちらかであるということにする。そして、記号は、\(|\)を用いる。また、1と\(a \times l(a)\)はタプルで取りあえず表してみよう。即ち、()と\( (a, l(a) )\)とにする。さて、タプルを新しいコンストラクタで置き換えることにする。()は値コンストラクタ\( N il \)で、また、\( (a, l(a) )\)は値コンストラクタ\(Cons\)で置き換える。このようにすると、後者の方は \(Cons \ a \ List(a) \)で表すことができる。即ち、代数方程式\(l(a) = 1 + a \times l(a) \)は、次のデータ型で置き換えることができる。

data List a = Nil | Cons a (List a)

上記のデータ型は、代数方程式から導き出されている。そこで、このようなデータ型を、特に、代数的データ型と呼ぶ。上記のデータ型は、また、良く知られているリストの定義である。下図に示すように、リストの定義が代数方程式から導き出される。何とも面白い変換だと思う。
f:id:bitterharvest:20170201092537p:plain

圏論では、同じ構造の圏であれば、一方の圏の性質を他方の圏を用いて調べることができる。この役割をしてくれるのが関手(Functor)である。これについては次回で述べる。