日記 (2019 年 11 月 16 日)

Haskell を勉強していると、 ちょくちょく catamorphism とか anamorphism のようなギリシャ語の接頭辞が付いた morphism を見かける。 これらの概念についてそろそろちゃんと理解したくなってきたので、 分かったことをまとめようと思う。 ちなみに、 私は圏論が好きなので、 プログラミング言語論的な視点よりも圏論的な視点の方を優先する。

この日記の読者層はよく分からないが、 圏論について詳しくないのであれば、 圏とは集合全体を集めたものだと思い、 関手とは集合に対して別の集合を対応付けるような規則だと思って構わない。 さらに、 圏の対象を集合と読み替え、 圏の射は写像と読み替えて良い。

本題に入る。 問題となっている射を理解するには、 まず自己関手上の代数について知っておく必要がある。 これは、 以下で定義される概念である。

上記の定義において、 F-代数とその間の射は圏を成す。 この圏は、 以降 AlgF(󰒚) で表すことにする。

代数の中で特に重要なのが、 以下で定義される始代数である。 これは、 プログラミングで用いられる様々なデータ構造を表現することができるものである。

定義から分かるように、 F-始代数とは単に AlgF(󰒚) の始対象のことである。

さて、 以上の準備のもと、 最初の疑問だった catamorphism が定義できる。 ここだけ英単語になるのも少し気持ち悪いので、 勝手に日本語訳を当てることにする。

イメージを掴むため、 1 つ例を挙げておこう。 圏として Set を考え、 ある集合 V を固定し、 FV: Set ⟶ Set A ⟼ 1+V×A とおく。 すると、 FV-代数とは、 集合 A と写像 α:1+V×A→A の組 (A,α) である。 ここで、 余積の普遍性によって、 写像 α は 2 つの写像 α0:1→A, αc:V×A→A の組と同一視できる。 さらに、 写像 α0 は A の元 a0∈A と同一視できる。 以上のことから、 FV-代数とは、 集合 A とその元 a0∈A と写像 αc:V×A→A の組 (A,a0,αc) とも思うことができる。

さて、 それでは FV-始代数とはどのようなものだろうか。 これは実は V の元から成る有限リスト全体の集合になる。 すなわち、 S:={⟨v1,⋯,vn⟩∣vi∈V,n≥0} とおき、 s0 を 0 個の元から成るリスト ⟨⟩ とし、 σc はリストへの値の追加 σc: V×S ⟶ S (v,⟨v1,⋯,vn⟩) ⟼ ⟨v,v1,⋯,vn⟩ であるとすると、 (S,s0,σc) は FV-始代数になる。 実際、 別の FV-始代数 (A,a0,αc) があったとすると、 写像 f:S→A を帰納的に f(⟨⟩) := a0 f(⟨v1,⋯,vn⟩) := αc(v1,f(⟨v2,⋯,vn⟩)) と定めれば、 f は FV-代数の唯一の射となることが分かる。 すなわち、 f=cata(A,a0,αc) である。

FV-始代数についてもう少し詳しく見てみよう。 これは、 いわば FV が定める構造に関して、 次のような意味で 「自由に」 生成されたデータ構造であると見なすことができる。 FV-代数とは、 集合 A の他に元 a0∈A と写像 αc:V×A→A が定まっているものであった。 ここで、 A がどのような集合であるか全く知らない状態から、 A の元を得るにはどうしたら良いかを考えてみる。 まず、 a0 という元はすでに定まっているので、 A の元として a0 が得られた。 次に、 写像 αc:V×A→A があるので、 V の元 v1 があれば、 先程得られた a0 と組み合わせて、 αc(v1,a0) という新しい A の元が得られる。 すると、 さらに V の元 v2 があれば、 ここから αc(v2,αc(v1,a0)) というまた新しい A の元が得られ、 以降これを続けることで次々と A の元が得られる。 このようにして再帰的に得られるものだけをそれぞれ区別しつつ集めた集合が、 まさに FV-代数 S である。 すなわち、 始代数というのは、 自己関手が定める構造だけを使って再帰的に (同じ意味だが帰納的に) 得られる元を区別しつつ集めたものと捉えられる。

次に、 FV-代数の下方射について詳しく見てみる。 繰り返すが、 FV-代数の構成要素は、 集合 A とその元 a0∈A と写像 αc:V×A→A であった。 これはまさに、 リストの畳み込みを行う関数 (Haskell では foldr, Ruby では inject) に渡す引数である。 そして、 上の定義を見ると分かるように、 cata(A,a0,αc) がまさにその畳み込み関数になっている。 すなわち、 代数の下方射とは、 代数によって再帰的に定められたデータ構造に対して畳み込みを行うような関数を表現していると捉えられる。

さて、 今度は代数の双対概念である余代数と終余代数を考える。 単に圏論的双対をとるだけだが、 念のため定義を書き下しておく。

F-余代数とその間の射が成す圏は、 以降 CoalgF(󰒚) で表すことにする。

例として、 先程挙げた FV を再び考える。 FV-余代数とは、 集合 C と写像 γ:C→1+V×C の組 (C,γ) である。 この写像 γ は、 各元 c∈C に対して、 特殊なケースとして 1 の唯一の元を対応させるか、 そうでなければ V と C の元の組 (v,c󰎘) を対応させるものである。

FV-終余代数は、 V の元から成る有限もしくは無限リスト (リストよりストリームと言った方が正確かもしれない) 全体の集合になる。 つまり、 T:={⟨v1,v2,⋯⟩∣vi∈V,vi たちは有限個でも無限個でも良い} とおき、 1 の唯一の元を ⋆ で表すことにして、 τ はリストの先頭と残りを取り出す操作 τ: T ⟶ 1+V×T ⟨v1,v2,⋯⟩ ⟼ { ⋆ (リストが空のとき) (v1,⟨v2,⋯⟩) (リストが空でないとき)♡ であるとすると、 (T,τ) は FV-終余代数になる。 実際、 別の FV-余代数 (C,γ) があったとすると、 写像 h:C→T であって、 h(c)={ ⟨⟩ (γ(c)=⋆) ⟨v,h(c󰎘)⟩ (γ(c)=:(v,c󰎘)) を満たすものが作れ、 これが FV-余代数の唯一の射となることが分かる。 すなわち、 h=ana(C,γ) である。

FV-終余代数について詳しく見よう。 FV-余代数とは、 集合 C の他に写像 γ:C→1+V×C が定まっているものであった。 この写像によって、 ある C の元 c があると、 γ によって ⋆ が返ってこない限りは、 V の元 v1 と新たな C の元 c1 が得られる。 この c󰎘 を使えば、 再び ⋆ が返ってこない限りは、 さらに V の元 v2 と新たな C の元 c2 が得られ、 この操作は (もしかしたら無限に) 続けることができる。 この操作を行うごとに毎回 V の元が得られるので、 これらのデータを使ってまた別の計算をすることができる。 つまり、 代数を考えるときは FV は代数の元の 「作り方」 を定めていたのに対し、 余代数を考えるときは FV は余代数の元の 「使い方」 を定めていると捉えることができる。 この捉え方をすれば、 終余代数というのは、 自己関手によって定まる元の使い方が保証されるようにできるだけ元を集めたものと見なすことができる。

ということで、 FV は余代数の元の使い方を定めていると思えるわけだが、 余代数に定まる射 γ が、 まさにこの使い方に沿って実際に元を使えるようにしているものである。 実際、 上の式 ♡ を見ると、 リストが空かどうかで場合分けし、 空でなければ先頭の元と残りのリストに分割しているわけだが、 これは Haskell などにおけるリストのパターンマッチと全く同じ形である。 すなわち、 余代数の射はパターンマッチさせる関数と見なせるのである。

次に、 FV-余代数の上方射について見る。 すでに述べたように、 FV-余代数があると、 そこに定まっている射 γ を繰り返し使うことで、 データを次々と取り出すことができる。 このように取り出したデータを順に集めて (無限長かもしれない) 列にするのが ana(C,γ) である。 Haskell には unfoldr という名前で全く同じ処理をする関数が用意されている。 このことから、 余代数の上方射は、 その余代数が定めるデータを取り出す関数によって取り出されるものを順にデータ構造に収める役割をもつものであると捉えられる。

以上、 下方射と上方射の定義と気持ちをまとめてみた。 次回があれば、 リスト以外の具体例や Haskell における実装なども勉強してまとめたいと思う。