bitterharvest’s diary

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

プログラマーのための圏論 (初級編:圏論とHaskell)

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

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

モナドの応用

最後に ノーベル経済学賞を受賞したダニエル・カーネマン教授が一般読者向けに著述した『ファスト&スロー』を読んだ。本のタイトルからは内容はつかみにくい。副題は「あなたの意志はどのように決まるか?」となっているので、脳科学の本かなと思い違いして…

モノイドーモノイド圏での記述

13.4 モノイド圏での記述 前回の記事で、二項演算を表すための小さい圏の圏(category of small categories)を次のように表した。 この図において、\(f,g\)や\(M(f),M(g)\)などは小さい圏の圏の構成要素には含まれていないので、これを省略することにしよ…

モノイドー小さい圏の圏での記述

13.3 小さい圏の圏での記述 これまで、算数で最初に学んだ加算・乗算に代表されるモノイドと呼ばれる二項演算を、圏論でどのように記述したらよいのかについて話を進めてきた。即ち、アセンブラ言語でのように処理を具体的に記述するのではなく、高級言…

モノイドー代数学から圏論へ

13.2 代数学から圏論へ モノイドになれたところで、モノイドを代数学での定義から始めて圏論での定義へと段々に抽象化してみよう。丁度、プログラミングで、アセンブリ言語での記述から高級言語での記述に変えていくことに相当する。 1) 代数学での定…

モノイドーHaskellでの表現

13.モノイド モノイド圏は、集合の要素を射に、二項演算子を射の合成に、そして、単位元を恒等射にし、結合律、単位律が成り立っているものをいう。例えば、整数の乗算の場合には、 1) 対象:シングルトン(通常星印で表される) 2) 射:整数 3) ドメイン、…

モナドと自然変換

12.圏論でのモナド Haskellでのモナドについて論じてきたが、モナドは圏論の中の一つの圏でもある。そこで、ここではモナドが圏となるための条件を求めて見よう。圏論においては自然変換は重要な役割をなすが、モナドは自然変換が主要な枠組みとなってい…

通常のプログラムをHaskellで記述する(5)

子供の頃に喉から手が出るほどに欲しかったものを多くの人は覚えているだろう。それも自分の小遣いでは到底手が届かないほど高値のものを切望したのではないだろうか。デパートと言われるものが全盛だった頃、おもちゃ売り場は何とも楽しい場所だった。その…

通常のプログラムをHaskellで記述する(4)

プログラムを書いているときに記憶力を疑うことが多い。プログラミングの経験が豊富なのだから、何も参考にすることなく、画面にプログラムを打ち込んでいけるのだろうと思われることも多いし、自分でもそう思っている。しかし、いざプログラムを打ち込む段…

通常のプログラムをHaskellで記述する(3)

11.3 状態を表現するための準備をする Haskellで状態を表すための準備をしよう。入力\(a\) を受けてその結果得られた状態\(s\)をタプル\( (a, s) \)であらわすことにしよう。Hskellでプログラムを書くときは、しっかりと腰を据えて考えることが必要であ…

通常のプログラムをHaskellで記述する(2)

最近、進化心理学の本を立て続けに読んだが、その中で最も優れていると感じたのは、ジョシュア・グリーン(Joshua Green)の『モラル・トライブズ』であった。 グリーンは高校生のとき、弁論部に属していたそうだ。対抗戦の弁論大会で、彼は「功利主義(utilita…

通常のプログラムをHaskellで記述する(1)

11.通常のプログラムをHaskellで記述する モナドの大きな目的は手続き型プログラミング言語で書かれたプログラムを副作用のない純関数型のプログラムで記述できるようにすることである。通常のプログラミング言語は多くの場合手続きが他である。これには…

Haskellの難関モナドを突破するために掘り下げて学ぶ(4)

10.4 モナドを別の方法で定義する 前の記事でモナドを定義するときに\(>>=\)という関数を用いた。この関数の型シグネチャは次のようになっていた。 (>>=) :: \ m a -> (a -> m b) -> m b ここで、\(m\)を関手と考えてみよう。関手\(F\)は下図のように定…

Haskellの難関モナドを突破するために掘り下げて学ぶ(3)

10.3 プログラムの合成 前々回の記事で紹介した二つのプログラムを決後するフィッシュ・オペレータをHaskellで実現することを考えよう。二つのプログラムを合成するとは、下図を実現することである。 上図では二つのプログラム\(f,g\)がある。それぞれの…

Haskellの難関モナドを突破するために掘り下げて学ぶ(2)

10.2 集合と冪集合 数学は全く異なるものの間の中に共通する性質を見出し新しい概念を引き出すことを得意とする学問だ。ここでも、後でまさかと思うことを説明するのだが、その準備のために集合について少し説明しておこう。集合は要素の集まりと最初は…

Haskellの難関モナドを突破するために掘り下げて学ぶ(1)

10.モナドを掘り下げよう 圏論についての説明は前回の記事で一応終了した。しかし、ある事項についてはもう少し詳しく知りたいということがあるだろう。そのうちの一つはモナドだと思う。モナドは慣れてくるととても便利な道具なのだが、そこまでに行き着…

関手圏

9.関手圏 9.1 小さな圏の圏 圏は、対象と射で構成されていた。そこで、対象を圏とし、射を関手とする圏を考えることができる。しかし、この圏を作るにあたっては少し制約を設けている。これは圏から圏を作るということになるので、集合の集合を考えると…

自然変換

8. 自然変換 圏論の話もそろそろ終わりに近づいてきた。これまでの話の中で重要であった話題は、圏そのものと、関手である。圏は計算の構造を示し、関手は構造を維持しての圏から圏への射を与えてくれる。今回は、この二つの概念に劣らないほどに重要な自…

写像対象-カリー=ハワード同型対応

7.9 カリー=ハワード同型対応 世の中には、言い方は違っているのだが、同じことを言っているということが往々にしてある。前回の記事で、型定理と圏論は一対一に対応づけできると説明したが、その例の一つである。さらに、もう一つ対応するものがある。…

写像対象-型定理(続き)

7.8 具体例 指数対象\(A^{B+C} = A^B \times A^C\)は、Haskellの型シグネチャで表すと、 \begin{eqnarray} Either \ b \ c \rightarrow a \sim (b \rightarrow a, c \rightarrow a) \end{eqnarray} となることを前回の記事で説明した。それでは、この型シ…

写像対象-型定理

7.7 型定理(Type Theory) 型定理という言葉に戸惑う人も多いことと思う。日本語版のウィキペディアで型理論を検索するとあまりにも短い記述にがっかりするだろう。得られる情報も余りない。しかし、さすがに英語版の方には詳しく書いてある。その記述の中…

写像対象-指数対象

7.6 指数対象 写像対象には別の表現法がある。また、こちらの方がよく知られてもいる。それは指数対象と呼ばれる。対象\(A\)から対象\(B\)への射の集まり\(A \Rightarrow B\)を写像対象と呼んだ。同じように射の集まりなのだが、ドメイン\(A\)を肩に、コ…

写像対象-Haskellで表現する

7.3 写像対象とは ここでは写像対象を定義することにしよう。前回の記事で写像対象を説明するための図として下図を提示した。 上図で、\(Z\)は最善の表現であるとすると、これは\(A\)から\(B\)への可能な写像を重なることなくすべてを含むような関数の集…

写像対象―入門

しばらく休みを頂いたが、この間、古代史の関係の書物を読み漁った。特に、松木武彦さんの本が気に入った。 『美の考古学:古代人は何に魅せられてきたか』と『旧石器・縄文・弥生・古墳時代 列島創世記』を、また、共著だが『弥生時代って、どんな時代だっ…

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

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

関手ープロファンクタ

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

関手―反関手

6.9 反関手 以前に、\(Reader\)と呼ばれる関手について説明したことがある。二つの射を得て一つの射を出力するという分かりにくい関手だったのではと想像している。圏論は、射を中心にして考えるので、射を射の入力や出力として利用するのは自然なのだが…

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

6.8 余積をファンクタで実現する 前回の記事では関手を利用しての積と余積を定義する中で\(Identity\)を用いたが、その詳しい説明はしなかった。そこで、ここでは、まず、データ型\(Identity\)の定義から話を始めよう。関手\(Identity\)の可換図式は下図…

関手ー積と余積

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

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

6.6 Haskellで関手をどのように理解したらよいか 圏論の中で重要な概念の一つは関手(functor)だ。そして、Haskellでも最も便利な道具の一つはファンクタである。数回の記事の中で、いくつかの例を挙げながら、圏論での関手を説明してきた。また、それとの…