bitterharvest’s diary

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

プログラマーのための圏論 (初級編:圏論と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…

関手ー圏の圏

6.4 圏の圏 圏と圏とをつなぐ射は関手という特別な名前がついているが射であることに変わりはない。従って、二つの関手を合成することもできるはずだ。図のように、三つの圏\({\mathcal C}\),\({\mathcal D}\),\({\mathcal E}\)を考えてみよう。\({\mathc…

関手ー一般化

6.3 一般化 \(Maybe\)を利用して関手を説明したが、その他にもいろいろな関手を考えることができる。それらは(\(Maybe\)で説明した)\(fmap\)の実装が異なるだけだ。Javaを知っている人であればインターフェースを用いて実装したらと考えるだろう。Haskell…

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

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

関手ー定義

6.関手 関手は圏論の中で最も重要な概念である。圏論では自然変換(natural transformation)が重要であるが、これの根幹をなすのが関手である。 6.1 関手の定義 圏論は数学的な構造を対象としての点と対象を結ぶ射としての矢印で表している。二つの圏が…

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

5.6 代数的データ型 引き続き、Bartosz Milewskiの動画を元に、話を進める。 1) 乗算(Multiply) デカルト積の圏について、前々回の記事で説明したが、積と名前がついているので、四則演算での乗算とかかわりがありそうである。 乗算\(\times\)は、交換律(…

圏論での積と余積―余積

5.5 余積 オーストラリアオープンテニス2017は、昨日、男子決勝戦が行われた。テニス界のレジェンドといわれるフェデラーとナダルが決勝で争うこととなり、これ以上、楽しませてくれる組合せはなかった。 グランドスラムの優勝回数で、二人は歴代の1位と2…

圏論での積と余積―デカルト積

5.4 積の圏 1)デカルト積 デカルト積(Cartesian product)は、直積集合、直積、積集合などと呼ばれたりする。これは集合の集まりに対して、それぞれの集合からひとつずつ元を取り出して組にしたものである。 例えば、二つの集合\(A,B\)に対し、それらの…

圏論での積と余積―双対という概念

5.3 双対という概念 普遍性(universal property)は圏論の中では重要な概念である。前回は、始対象と終対象について論じた。対象という言葉は、何かの集まりを表したものであり、抽象的な概念である。対象は、集合であるかもしれないし、グラフのノードの…

圏論での積と余積―終対象と始対象

今年最後に読む本を定めて、28日に市の図書館から網野義彦著『日本の歴史のよみなおし(全)』と山本淳子著『源氏物語の時代 ― 一条天皇と后たちのものがたり』を借りた。『日本の歴史のよみなおし』は、中世の時代を中心にいくつかのテーマに沿って横断的に説…

モナドを音楽の力を借りてアナログ的に説明する

4.8 モナドを関手(ファンクタ)を用いずに説明する 数学の本を読んでいると、1ページを読むのに数時間もかかることが往々にして起きる。特に、定理があってその証明が書かれているときがそうだ。純粋な数学的用語で書かれているときは、その背後にある概念…

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

『プログラマのための圏論』はこれまでの分をまとめてPDFファイルにしました。参考にしてください。

プログラムでの圏の構成を完成させる

4.7 C++プログラムから圏を作成する(続き) 前回の記事で、曜日を進めるプログラムの開発状況を手順を追いながら、説明した。このプログラムは、曜日を進める関数\(increase\)と遅らせる関数\(decrease\)から出発した。最初に作った関数は、値をどこにも記…

C++のプログラムも圏に変えてしまおう

4.7 C++プログラムから圏を作成する いろいろな圏を見てきたので、ここでは、プログラマーにとっては大事なプログラムを圏として構成することを考えよう。 1)曜日を進めるプログラム ここで、作成するプログラムを曜日を進めたり遅らせたりするプログラ…

二項演算子からモノイド圏を作る

前回の記事は、ホモトピー論まで含まれていたので、とても高度な数学的概念が含まれていた。それにもめげず、沢山の人が記事を読んでくださったようで、感謝している。今回は現実の世界に戻して、二項演算子の世界を圏にすることを考えよう。 4.6 二項演…

様々な関係から圏を作成してみよう

4.様々な圏の作成 圏に馴染むためにいくつかの例を挙げることにしよう。 4.1 空圏 圏の中でもっとも単純な圏は、対象も射も持たない。このため、恒等射も存在しないことになる。これは空圏(圏0)と呼ばれる。その構成を挙げておこう。 1) 対象:なし 2) …

集合から圏論へ:ミクロな世界からの宇宙への旅立ち(2)

3.2 集合の要素を射に 集合の世界は要素を中心に考えるが、圏論の世界は射を中心に考える。そこで、集合を考えるとき、その要素を射に変えるものが必要となる。 その役割を果たしてくれるのが、一つだけの要素からなる集合である。この集合はシングルトン…

集合から圏論へ:ミクロな世界からの宇宙への旅立ち(1)

3.集合の世界から圏論の世界へ ごちゃごちゃしたミクロの世界をかなぐり捨てて雄大なマクロの世界(宇宙)へ旅立つことにしよう。数学でのミクロな世界は集合で、雄大な宇宙は圏論である。集合は、要素の集まりとして定義される。また、集合を論じるときは…

射は閉じている:どれだけ合成しても大丈夫

2.4 合成 1)圏の構成要素 ここでは、これから説明する合成も含めて、圏を構成する要素についてまとめておこう。圏は次の構成要素から成り立つ。 1) 対象\(A,B,C,..\)を有する。 2) 射\(f,g,h,..\)を有する 3) 射はドメインとコドメインを有する。なお、…

自己を表現する恒等射

2.3 恒等射 恒等射は自らを自らに写す射だ。これだけのことなので、今回の記事は簡単に済ますつもりでいた。しかし、沢山ある射の中で恒等射を特別に圏の定義の中に含める必要がなぜあったのだろうか。恒等射は英語ではidentity(あるいはidentity morphis…

圏論は射から

2.2 射 圏論の中で一番重要な役割を担うのは射(arrowあるいはmorphism)である。射は対象を対象へと移す(写像という用語を使ったときは「写す」といったほうがよさそうだが、射は矢を射るという意味で用いているので「移す」という漢字を使う)。射は、他…

境を明確にする対象

2.圏の定義 圏論の核となる圏の定義はとても単純である。抽象化は、細かいことを切り捨て、本質となている部分を取り出していく作業である。別の言い方をすると、数学の様々な分野での固有な部分を切り捨て、それらに共通する部分を抜きだすことである。圏…

なぜHaskell、なぜ圏論なのか

1.初めに これまで、さまざまな言語でプログラミングしてきたが、一番満足しているのはHaskellである。なぜという問いに一言で答えるならば、バグが入りにくい、あるいは、プログラムが信用できるということだろう。 この記事の前に、量子力学の世界をHask…