Webエンジニアでも圏論したい!

この記事の目標は、「型付きの純粋な関数は圏をなす」を理解することです。

始めていきましょう。

TypeScript で圏を作ろう

なじみある具体例から始めます。圏論はとりわけ抽象度が高いため、圏の定義を天下り的に書いても何を言っているのかわかりませんからね。

TypeScript をご存知でしょうか。静的な型付けができる JavaScript のスーパーセットです。こんなふうに型付けができます。

// number 型
const num: number = 10
// string 型
const str: string = 'aaa'
// number の配列型
const nums: number[] = [1, 2, 3]

それでは、練習がてら、純粋な関数 1 をいくつか適当に定義してみましょう。

const add10 = (num: number): number => num + 10
const len = (str: string): number => str.length
const wrap = (num: number): number[] => [num]
const reverse = (nums: number[]): number[] => nums.concat().reverse()

// それぞれの型には 'なにもしない' 関数が定義できる
const idNum = (x: number): number => x
const idStr = (x: string): string => x
const idNums = (x: number[]): number[] => x

型と関数を図にしてみた。

【型付きの純粋な関数の世界】 f:id:fuji_haruka:20170805140431j:plain

こんな感じで、いくらでも書くことができます。これは、型付きの純粋な関数の集合です。型付きの純粋な関数(とその型たち)の集合を C と呼ぶことにします。では、 C を観察してみましょう。

関数の世界 C には以下のような特徴が見られます。

  1. 関数を合成できる。
  2. 合成された関数はまた純粋である。
  3. 各型には恒等関数id('なにもしない'関数)が定義できる。

関数の合成については、たとえば lenadd10 を合成できます。

// 関数を合成する関数
const compose = (func1, func2) => (arg) => func1(func2(arg))

const lenPlus10 = compose(add10, len)
lenPlus10('aaa')
// -> 13

関数f, gの合成をf ∘ gと書きます。上の compose を使えば、 f ∘ gcompose(f, g) のことです。一般論として、関数の合成には次の性質があります。

  1. 結合則: 関数 f, g, h に対して、 f ∘ (g ∘ h) = (f ∘ g) ∘ h が成り立つ。
  2. 恒等関数の合成: 恒等関数 id に対して、 f ∘ id = id ∘ f = f が成り立つ。

だんだんと圏に近づいてまいりました。実際のところ、圏とは、関数の世界 C において一つ一つの型の詳細はいったん忘れて、上記のような関数の持っている性質を取り出して抽象化したものです。今見てきたものは、関数の世界 C が圏であることを確認した道筋になります。

圏の定義

C は、対象の集合 O と射の集合 A からなります 2

  • f ∈ A は 2 つの対象 X, Y ∈ O の情報を持っていて、 f: X -> Y と書きます。つまり、圏には dom 関数と cod 関数(それぞれ domain と codomain)が定義されていて、各射 f に対して dom(f) = Xcod(f) = Yが成り立ちます。
  • 射は合成できます。つまり、射の集合には演算 が定義されていて、射fgに対してf ∘ gも射になります。
  • 射の合成は結合則が成り立ちます: f ∘ (g ∘ h) = (f ∘ g) ∘ h
  • 各対象は恒等射が存在します。つまり対象 X に対して射 id: X -> X が存在して、f ∘ id = id ∘ f = fが成り立ちます。

以上が圏の定義です。

上の定義をよく見てみると、気づくことがあります。まず、射は「関数」とは限りません。射は、合成が定義された単なる矢印です。集合とその間の関数は圏の性質を満たしますが、圏は集合や関数の中身を気にしていません。

また、対象にいたっては演算も定義されていません。圏論が注目しているのは対象よりも射です。対象には直接的には言及せず、射の性質によって対象の構造を知ろうとしてます。このことをスローガン的に「要素を隠して矢印を語る」(『圏論の歩き方』P.19)と言うとしっくりきます。

さて、圏の定義をふまえて最初の例をもう一度見てみましょう。

【型付きの純粋な関数の圏】 f:id:fuji_haruka:20170805140431j:plain

ここでは、型が対象、関数が射になっています。合成や恒等射の例もすでに作りましたから、型付きの純粋な関数が圏になっていることが具体的に確認できましたね。

……だからどうした、という感があるかもしれません。確かにこれだけでは、何も特別なことは言っているようには思えません。しかし、一般論ですが、あるモノが圏という数学的構造を持っているとわかれば、それは圏として研究することができ、圏で成り立ついろいろな性質や定理がそのモノにも成り立つわけです。もしも圏に有用な定理があれば、そのモノにも応用できる。これが抽象化のメリットの一つだと思います。

そういう意味では圏の定義までで記事を終わらせるのは尻すぼみ感があるのですが、今日は力尽きたのでここまでにします。

ちなみに、「純粋な関数」という条件を取り外した「型付きの関数」は圏ではなくなります。() => Math.random()みたいな関数が混入したら、実行するたびに結果が異なるわけですから、そもそも関数としての同一性をどうやって定義すればよいかわかりませんからね。

こうしてみると、随所で「プログラムを書くときは純粋な関数が大事なんやで」と言われますが、それはプログラムの可読性が上がるからというだけではなく、純粋な関数だけを扱えば圏になるからという理由もあるんですね。


  1. 純粋な関数とは、同じ入力値を与えるたびに同じ出力が得られる関数のことです。関数に内部状態を持たず、また入力値の中身を書き換えません。

  2. 本当は、対象と射は「集合」に限りません。たとえば集合の圏 Sets は真のクラスです。ここでは簡単のため小さい圏だけを考えています。