このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

参照用 記事

さまざまなモナド類似物とベックの分配法則

モナドとコモナド、それらを組み合わせたもの、条件の一部を取り除いたものなどを、モナド類似物monad-like entity〉と呼ぶことにします。今までに、さまざまなモナド類似物に出会ってはいるのですが、それらを統一的に理解することがなかなか出来ませんでした。

最近になって多少は進展がみられて、昔の疑問が解けたりしています。今日は、そんな話。

内容:

バーの論文

ベックの分配法則〈Beck's distributive law〉に関して、マイケル・バー〈Michael Barr〉の短い論文があります。

たった5ページですが、示唆に富む内容で、いくつかの方向に発想を広げるヒントになります。

この論文を書いたバーの動機は、線形論理に出てくる自然変換 δA,B,C:A\otimes(B\oplusC) → (A\otimesB)\oplusC が、ベックの分配法則として説明出来ないか? というものです。結果的に、線形論理のδはベックの分配法則の事例になっています。そのことを示すためにバーは、分配法則を一般化しています。

現在、よく知られている分配法則のタイプは:

  1. 2つのモナドのあいだの分配法則
  2. 2つのコモナドのあいだの分配法則
  3. モナドとコモナドのあいだの分配法則(混合分配法則〈mixed distributive law〉)

バーは、モナドでもコモナドでもない単なる自己関手のあいだに分配法則を定義して、ベックの持ち上げ定理が何の条件もなしに成立することを証明しています。

2011年に僕は、動機はまったく違うのですが、ほぼ同じ問題を考えていました。

今読み返して、すじ(方向性)は悪くないと思いますが、詰めが甘く、モヤッとしたままでした。バーのアイデアを使うと、モヤモヤに決着が付きそうです。

2011年のモヤモヤ

双代数と双モノイド」に曰く:

Cを固定して、F, Gが2つの自己関手(F = G でもかまいません)として、(A, a:F(A)→A) がF代数、(A, b:A→G(A)) がG余代数だとします。βが β::FG⇒GF:CC という自然変換とします。ここで「FG」は、関手の反図式順の結合「Gの後にF」を意味するとします。僕は図式順が好きですが、ここでは慣例に従い反図式順を使います。

F代数とG余代数の組み合わせ (A, a, b) がFGβ双代数だとは、次の五角形が可換図式となることです。

「FGβ双代数」という名称はともかくとして、設定と定義はこれで合ってます(と、現時点では断言できる)。しかし、確信が持てないので、最後の段落にモヤッとしたことを書いています。

最後に気なることを: 双代数法則に出てくるβはどっから来るのでしょうか? βの条件として次があります。

  1. F(b);βA:F(A)→GF(A) が、F(A)上のG余代数余演算となる。
  2. βA;G(a):FG(A)→G(A) が、G(A)上のF代数演算となる。

この条件でどこまでβが決まるのかは(僕には)よく分かりません。ベックの分配法則と類似の状況になっているようには思えますが。

「βの正体や特徴付けが分からない」けど「ベックの分配法則っぽい」とは書いています。「っぽい」ではなくて、βはまさにベックの分配法則そのものです(ただし、混合分配法則)。僕の歯切れが悪いのは、単なる自己関手 F, G に対して「ベックの分配法則」なんて言っていいのか? そんなものに意味があるのか? と、戸惑い躊躇していたからです。

バーは、単なる自己関手でもベックの分配法則を考えてもいいと喝破し、モナドの分配法則の場合と類似の結果が(ある程度は)成立することを示しています。

モナド類似物の分類

バーの結果は、戸惑いと躊躇を振り払ってしまえば、かなり簡単な話です。広い範囲のモナド類似物に対してアイレンベルク/ムーア構成が有効なんだ、という観察が基本になります。

ここで、モナド類似物に呼び名がないので困ってしまいます。集合ベースの代数系との類似性から命名をすることにします -- 次のような集合ベースの代数系はよく知られています。

代数系 一言説明
マグマ 何の法則も仮定しない
半群 結合律が成立する
モノイド 結合律と単位律が成立する
コモノイド 余結合律と余単位律が成立する
半環 2つのモノイド演算があり、分配律が成立する

これらの集合ベースの代数系と似た関手ベースの代数系を、XXX-like monad と呼ぶことにします。"XXX-like"を「XXX様」で表すことにします。

モナド類似物 一言説明
マグマ様モナド 何の法則も仮定しない
半群モナド 結合律が成立する
モノイド様モナド 結合律と単位律が成立する
コモノイド様モナド 余結合律と余単位律が成立する
半環様モナド 2つのモノイド演算があり、分配律が成立する

モノイド様モナドは通常のモナドで、コモノイド様モナドはコモナドです。そして、半環様モナドが「ベックの分配法則、ベック分配系、複合モナド」で述べたベック分配系になります。

これらのモナド類似物に対して、アイレンベルク/ムーア構成が定義できます。つまり、モナド類似物が与えられると、そのアイレンベルク/ムーア圏が作れます。アイレンベルク/ムーア圏の対象を何と呼ぶか? またしても呼び名がない。

アイレンベルク/ムーア圏の対象の大分類としては、演算が1つのときは代数〈algebra〉か余代数〈coalgebra〉、演算が2つのときはそれらの組み合わせになります。例えば:

  1. モノイド様モナド〈通常のモナド〉 (F, η, μ) のアイレンベルク/ムーア圏の対象は、代数 a:F(A)→A in C
  2. コモノイド様モナド〈コモナド〉 (G, ε, Δ) のアイレンベルク/ムーア圏の対象は、余代数 b:A→G(A) in C
  3. 半環様モナド〈ベック分配系〉 ((M, η, μ), (A, ζ, α), δ) のアイレンベルク/ムーア圏の対象は、A上の2つの代数 m:M(A)→A in C, a:A(A)→A in C

代数/余代数は基本的大分類なので、個々のモナドアイレンベルク/ムーア圏の対象はさらに呼び分ける必要があります。例えば:

  1. マグマ様モナドアイレンベルク/ムーア圏の対象は、アイレンベルク/ムーア・マグマ
  2. 半群モナドアイレンベルク/ムーア圏の対象は、アイレンベルク/ムーア・半群
  3. モノイド様モナドアイレンベルク/ムーア圏の対象は、アイレンベルク/ムーア・モノイド
  4. コモノイド様モナドアイレンベルク/ムーア圏の対象は、アイレンベルク/ムーア・コモノイド
  5. 半環様モナドアイレンベルク/ムーア圏の対象は、アイレンベルク/ムーア・半環

ベックの分配法則、ベック分配系、複合モナド」では、アイレンベルク/ムーア・モノイドを1演算代数〈1-operation algebra〉、アイレンベルク/ムーア・半環を2演算分配代数〈2-operation distributive algebra〉と呼んでいます。注意すべきは、半群/モノイド/コモノイド/半環などが、ほんとにそのような代数系を意味するのではなくて、単なる比喩的な呼び名だ、ということです。

マグマレベルの議論

ベックは、分配法則によってモナドを“持ち上げる”ことが出来ることを示しました。この持ち上げ〈lifting〉には、モナド構造はなくてもよく、単なる自己関手であっても持ち上げは可能です。誰がそれに気付いたのかは知りませんが、冒頭に紹介したバーの論文には明確に書いてあります。

双代数と双モノイド」と同じ状況設定をします。F, G は圏C上の自己関手とします。次のように定義します。

  • A∈|C| に対して、F(A)→A in C を、Fのアイレンベルク/ムーア・マグマ〈Eilenberg-Moore magma〉、または単にF-マグマ〈F-magma〉と呼ぶ。
  • A∈|C| に対して、A→G(A) in C を、Fのアイレンベルク/ムーア・コマグマ〈Eilenberg-Moore comagma〉、または単にG-コマグマ〈F-comagma〉と呼ぶ。
  • 自然変換 β::G*F⇒F*G:CC を、Gに対するFの分配法則〈distributive law of F over G〉と呼ぶ。
  • A∈|C| に対して、F-マグマ F(A)→A とG-コマグマ A→G(A) の構造と、分配法則 β::G*F⇒F*G があり、冒頭に引用した可換図式を満たすとき(すぐ後で再論)、(F, G, β)-双マグマ〈(F, G, β)-bimagma〉と呼ぶ。

代数系何の法則もないので、代数/余代数/双代数の代わりに、マグマ/コマグマ/双マグマという言葉を使っています。マグマ/コマグマ/双マグマの準同型射を常識的に定義すれば圏になります。それらの圏を次のように書きます。

  • C上のF-マグマの圏: Mag(C, F)
  • C上のG-コマグマの圏: Comag(C, G)
  • C上の(F, G, β)-双マグマの圏: Bimag(C, (F, G, β))

(a:F(A)→A, b:A→G(B)) が双マグマである条件は、次の五角形図式が可換になることです。

可換図式より絵(ストリング図)にしたほうが分かりやすいでしょう。

絵の見方に関しては、「ベックの分配法則、ベック分配系、複合モナド // ベック分配系」の絵の周辺にちょっと書いてあります。

以上のセッティングで、次が成立します。

  • Comag(Mag(C, F), G↑β) \stackrel{\sim}{=} Bimag(C, (F, G, β))
  • Mag(Comag(C, G), F↑β) \stackrel{\sim}{=} Bimag(C, (F, G, β))

ここで:

  • G↑βは、G:CC を Mag(C, F) 上の自己関手に持ち上げたもの。
  • \stackrel{\sim}{=} は圏同型(圏同値より強い)。
  • F↑βは、F:CC を Comag(C, G) 上の自己関手に持ち上げたもの。

上の圏同型は、「ベックの分配法則、ベック分配系、複合モナド」と同様な絵(ストリング図)の計算をすれば、比較的容易に出ます。具体的な計算は今日は割愛します。

おわりに

単位や乗法を持たない単なる自己関手でも、そのアイレンベルク/ムーア圏(今の場合は、マグマ/コマグマ/双マグマの圏)を定義できます。また、ベックの分配法則が、自己関手のアイレンベルク/ムーア圏への持ち上げを誘導します。そして、前節に述べたような持ち上げ定理が成立します。

これで話はだいぶスッキリしたのですが、標準的なモナド以外に、さまざまなモナド類似物があるので、それらを系統的に記述して命名する手段がないと辛いな、と感じましたね。なんとかせねば。