プログラミングの文脈で「coalgebra」とはどういう意味ですか? 質問する

Question

代数

まず最初に、代数の概念を理解するところから始めるべきだと思います。代数とは、群、環、モノイドなどの代数構造を一般化したものです。ほとんどの場合、これらは集合の観点から紹介されますが、友人同士なので、代わりに Haskell の型についてお話しします。(ギリシャ文字を使わずにはいられません。ギリシャ文字を使うとすべてがかっこよく見えるからです。)

代数とは、τいくつかの関数と恒等式を持つ型にすぎません。これらの関数は、型の異なる数の引数を取りτ、を生成します。カリー化τされていない場合、これらはすべてのように見えます。また、関数の一部に対して特別な動作をする(τ, τ,…, τ) → τの要素である「恒等式」を持つこともできます。τ

最も単純な例はモノイドです。モノイドとは、τ関数mappend ∷ (τ, τ) → τと単位元を持つ型のことです。他の例としては、グループ (モノイドと似ていますが、関数が追加されています)、リング、格子などがmzero ∷ τあります。invert ∷ τ → τ

すべての関数は上で動作しますτが、異なる引数を持つことができます。これらはと記述できτⁿ → τ、ここではのτⁿタプルにマップされますn τ。このように、恒等式をとして考えることができます。ここでは単なる空のタプルです。したがって、代数の考え方を実際に簡略化できます。つまり、いくつかの関数を持つ型にすぎません。τ⁰ → ττ⁰()

代数は、コードの場合と同じように、数学における一般的なパターンを「因数分解」したものです。前述のモノイド、グループ、格子など、興味深いものがすべて同様のパターンに従っていることに気づいた人々は、それを抽象化しました。これを行う利点はプログラミングの場合と同じです。つまり、再利用可能な証明を作成し、特定の種類の推論を容易にします。

F-代数

しかし、因数分解はまだ終わりではありません。これまでに、関数がたくさんありますτⁿ → τ。実は、これらすべてを 1 つの関数に結合する巧妙なトリックがあります。特に、モノイドを見てみましょう。とがありますmappend ∷ (τ, τ) → τ。mempty ∷ () → τこれらを、和型を使って 1 つの関数に変換できますEither。次のようになります。

op ∷ Monoid τ ⇒ Either (τ, τ) () → τ
op (Left (a, b)) = mappend (a, b)
op (Right ())    = mempty

実際に、この変換を繰り返し使用して、任意の代数に対してすべての関数を 1 つに結合できます。(実際τⁿ → τ、任意の数の関数に対してこれを行うことができ、任意のに対しても同様に行うことができます。)a → τb → τ a, b,…

これにより、代数を、いくつかの混乱から単一のへの単一のτ関数を持つ型として扱うことができます。モノイドの場合、この混乱は次のようになります。グループ (追加の演算を持つ) の場合、これは次のようになります。構造ごとに異なる型になります。では、これらすべての型に共通するものは何でしょうか。最も明らかなのは、これらはすべて積の合計、つまり代数的データ型であるということです。たとえば、モノイドの場合、任意のモノイド τ で機能するモノイド引数型を作成できます。EitherτEither (τ, τ) ()τ → τEither (Either (τ, τ) τ) ()

data MonoidArgument τ = Mappend τ τ -- here τ τ is the same as (τ, τ)
                      | Mempty      -- here we can just leave the () out

グループ、リング、格子、その他すべての可能な構造に対しても同じことを行うことができます。

これらすべての型について他に何が特別なのでしょうか? そうです、それらはすべてですFunctors! 例:

instance Functor MonoidArgument where
  fmap f (Mappend τ τ) = Mappend (f τ) (f τ)
  fmap f Mempty        = Mempty

したがって、代数の考え方をさらに一般化することができます。これは、何らかの関数を持つ何らかのτ型にすぎません。実際、これを型クラスとして記述できます。f τ → τf

class Functor f ⇒ Algebra f τ where
  op ∷ f τ → τ

これは関数によって決定されるため、しばしば「F 代数」と呼ばれますF。型クラスを部分的に適用できれば、のようなものを定義できますclass Monoid = Algebra MonoidArgument。

余代数

さて、代数とは何か、そしてそれが通常の代数構造の単なる一般化であるということを、よく理解していただけたと思います。では、F 余代数とは何でしょうか。余代数は、代数の「双対」であることを意味します。つまり、代数を取り、矢印をいくつか反転します。上記の定義には矢印が 1 つしか見当たらないので、それを反転します。

class Functor f ⇒ CoAlgebra f τ where
  coop ∷ τ → f τ

以上です！この結論は、少し軽薄に思えるかもしれません（笑）。これは、コジェネバとは何かを説明していますが、それがどのように役立つのか、なぜ私たちが気にするのかについての洞察は実際には提供していません。良い例を 1 つまたは 2 つ見つけたり思いついたりしたら、すぐにそれについて説明します :P。

クラスとオブジェクト

少し調べてみたところ、クラスとオブジェクトを表すためにコアルゲーブラを使用する方法について、良いアイデアが浮かんだと思います。クラス内のオブジェクトのすべての可能な内部状態を含む型があり、クラス自体はオブジェクトのメソッドとプロパティを指定するCコアルゲーブラです。C

代数の例で示したように、任意のに対してa → τやのような関数が多数ある場合、和型を使ってそれらすべてを 1 つの関数に結合できます。双対の「概念」は、型の関数の多数を結合することです。これは、和型の双対、つまり積型を使って行うことができます。したがって、上記の 2 つの関数 (および ) を考えると、次のように 1 つの関数を作成できます。b → τa, b,…Eitherτ → aτ → bfg

both ∷ τ → (a, b)
both x = (f x, g x)

型は(a, a)直接的に関数子であるため、F 余代数の概念に確実に適合します。この特定のトリックにより、さまざまな関数 (または OOP の場合はメソッド) を型の単一の関数にパッケージ化できますτ → f τ。

型の要素は、オブジェクトの内部C状態を表します。オブジェクトに読み取り可能なプロパティがある場合は、そのプロパティは状態に依存している必要があります。これを行う最も明白な方法は、それらをの関数にすることです。したがって、長さプロパティ (例) が必要な場合は、関数を使用します。Cobject.lengthC → Int

引数を受け取って状態を変更できるメソッドが必要です。これを行うには、すべての引数を受け取って新しいを生成する必要があります。と座標を受け取るメソッドCを想像してみましょう。次のようになります。setPositionxyobject.setPosition(1, 2)C → ((Int, Int) → C)

ここで重要なパターンは、オブジェクトの「メソッド」と「プロパティ」がオブジェクト自体を最初の引数として受け取ることです。これは、selfPython のパラメータや他の多くの言語の暗黙のパラメータとまったく同じですthis。coalgebra は基本的に、selfパラメータを受け取る動作をカプセル化します。これが最初の引数CですC → F C。

positionそれでは、すべてをまとめてみましょう。プロパティ、nameプロパティ、関数を持つクラスを想像してみましょうsetPosition。

class C
  private
    x, y  : Int
    _name : String
  public
    name        : String
    position    : (Int, Int)
    setPosition : (Int, Int) → C

このクラスを表すには 2 つの部分が必要です。まず、オブジェクトの内部状態を表す必要があります。この場合、 2 つIntのと 1 つのが保持されるだけですString(これが型ですC)。次に、クラスを表す余代数を作成する必要があります。

data C = Obj { x, y  ∷ Int
             , _name ∷ String }

記述するプロパティは 2 つあります。これらは非常に簡単です。

position ∷ C → (Int, Int)
position self = (x self, y self)

name ∷ C → String
name self = _name self

ここで、位置を更新できるようにする必要があります。

setPosition ∷ C → (Int, Int) → C
setPosition self (newX, newY) = self { x = newX, y = newY }

これは、明示的な変数を持つ Python クラスのようなものですself。これで関数が多数用意できたのでself →、それらを 1 つの関数に結合して coalgebra を作成する必要があります。これは、単純なタプルで行うことができます。

coop ∷ C → ((Int, Int), String, (Int, Int) → C)
coop self = (position self, name self, setPosition self)

型((Int, Int), String, (Int, Int) → c)—for any c — は関数なので、coop必要な形式を持ちます: Functor f ⇒ C → f C。

これを踏まえて、C上coopで示したクラスを指定するコアルゴリズムを作成します。同じ手法を使用して、オブジェクトが持つ任意の数のメソッドとプロパティを指定できることがわかります。

これにより、クラスを扱うために余代数的推論を使用することができます。たとえば、「F 余代数準同型」という概念を導入して、クラス間の変換を表すことができます。これは、構造を保持する余代数間の変換を意味する、恐ろしい響きの用語です。これにより、クラスを他のクラスにマッピングすることについて考えることがはるかに簡単になります。

つまり、F 余代数は、self各オブジェクトの内部状態を含むパラメータに依存する一連のプロパティとメソッドを持つことでクラスを表します。

その他のカテゴリー

これまで、Haskell の型としての代数と余代数について説明してきました。代数は単なる関数τを持つ型でありf τ → τ、余代数は単なる関数を持つ型τですτ → f τ。

しかし、これらのアイデアは Haskell自体に特に結びつくものではありません。実際、これらは通常、型や Haskell 関数ではなく、集合や数学関数の観点から導入されます。実際、これらの概念はあらゆるカテゴリに一般化できます。

あるカテゴリに対して F 代数を定義できますC。まず、関数F : C → C、つまり自己関数が必要です。(すべての HaskellFunctorは、実際にはからの自己関数ですHask → Hask。) 次に、代数は、射を持つAからのオブジェクトにすぎません。余代数は、を除いて同じです。CF A → AA → F A

他のカテゴリを考慮することで何が得られるのでしょうか? そうですね、同じアイデアをさまざまなコンテキストで使用できます。たとえば、モナドです。Haskell では、モナドはM ∷ ★ → ★3 つの演算を持つ型です。

map      ∷ (α → β) → (M α → M β)
return   ∷ α → M α
join     ∷ M (M α) → M α

関数は、がであるmapという事実の単なる証明です。したがって、モナドはとという2 つの演算を持つ関数であると言えます。MFunctorreturnjoin

関数はそれ自体がカテゴリを形成し、関数間の射影はいわゆる「自然変換」です。自然変換とは、ある関数をその構造を維持しながら別の関数に変換する方法にすぎません。こちらはアイデアを説明するのに役立つ素晴らしい記事です。リスト専用のconcatについて説明しています。join

Haskell の関数では、2 つの関数の合成自体が関数になります。疑似コードでは、次のように記述できます。

instance (Functor f, Functor g) ⇒ Functor (f ∘ g) where
  fmap fun x = fmap (fmap fun) x

joinこれは、をからのマッピングとして考えるのに役立ちますf ∘ f → f。の型joinはです。直感的に、すべての型∀α. f (f α) → f αに有効な関数がの変換として考えられることがわかります。αf

returnは同様の変換です。その型はです∀α. α → f α。これは異なっているように見えます。最初のものαは関数「内」にありません。幸いなことに、恒等関数を追加することでこれを修正できます。∀α. Identity α → f α変換も同様returnですIdentity → f。

これで、モナドを、f演算およびを伴う関数に基づく単なる代数として考えることができますf ∘ f → f。これは見覚えがありませんか? これは、演算およびを伴う単なるIdentity → f型であるモノイドに非常に似ています。ττ × τ → τ() → τ

つまり、モナドはモノイドとまったく同じですが、型の代わりに関数子があります。これは同じ種類の代数ですが、カテゴリが異なります。(私の知る限り、「モナドは自己関数子のカテゴリ内のモノイドにすぎない」というフレーズはここから来ています。)

f ∘ f → fこれで、とという 2 つの演算ができましたIdentity → f。対応する余代数を得るには、矢印を反転するだけです。これにより、f → f ∘ fとという 2 つの新しい演算が得られます。f → Identity上記のように型変数を追加して、これらを Haskell 型に変換し、∀α. f α → f (f α)とを得ることができます∀α. f α → α。これは、コモナドの定義とまったく同じです。

class Functor f ⇒ Comonad f where
  coreturn ∷ f α → α
  cojoin   ∷ f α → f (f α)

したがって、コモナドは、自己関数のカテゴリ内の余代数です。

Answer 1

代数

まず最初に、代数の概念を理解するところから始めるべきだと思います。代数とは、群、環、モノイドなどの代数構造を一般化したものです。ほとんどの場合、これらは集合の観点から紹介されますが、友人同士なので、代わりに Haskell の型についてお話しします。(ギリシャ文字を使わずにはいられません。ギリシャ文字を使うとすべてがかっこよく見えるからです。)

代数とは、τいくつかの関数と恒等式を持つ型にすぎません。これらの関数は、型の異なる数の引数を取りτ、を生成します。カリー化τされていない場合、これらはすべてのように見えます。また、関数の一部に対して特別な動作をする(τ, τ,…, τ) → τの要素である「恒等式」を持つこともできます。τ

最も単純な例はモノイドです。モノイドとは、τ関数mappend ∷ (τ, τ) → τと単位元を持つ型のことです。他の例としては、グループ (モノイドと似ていますが、関数が追加されています)、リング、格子などがmzero ∷ τあります。invert ∷ τ → τ

すべての関数は上で動作しますτが、異なる引数を持つことができます。これらはと記述できτⁿ → τ、ここではのτⁿタプルにマップされますn τ。このように、恒等式をとして考えることができます。ここでは単なる空のタプルです。したがって、代数の考え方を実際に簡略化できます。つまり、いくつかの関数を持つ型にすぎません。τ⁰ → ττ⁰()

代数は、コードの場合と同じように、数学における一般的なパターンを「因数分解」したものです。前述のモノイド、グループ、格子など、興味深いものがすべて同様のパターンに従っていることに気づいた人々は、それを抽象化しました。これを行う利点はプログラミングの場合と同じです。つまり、再利用可能な証明を作成し、特定の種類の推論を容易にします。

F-代数

しかし、因数分解はまだ終わりではありません。これまでに、関数がたくさんありますτⁿ → τ。実は、これらすべてを 1 つの関数に結合する巧妙なトリックがあります。特に、モノイドを見てみましょう。とがありますmappend ∷ (τ, τ) → τ。mempty ∷ () → τこれらを、和型を使って 1 つの関数に変換できますEither。次のようになります。

op ∷ Monoid τ ⇒ Either (τ, τ) () → τ
op (Left (a, b)) = mappend (a, b)
op (Right ())    = mempty

実際に、この変換を繰り返し使用して、任意の代数に対してすべての関数を 1 つに結合できます。(実際τⁿ → τ、任意の数の関数に対してこれを行うことができ、任意のに対しても同様に行うことができます。)a → τb → τ a, b,…

これにより、代数を、いくつかの混乱から単一のへの単一のτ関数を持つ型として扱うことができます。モノイドの場合、この混乱は次のようになります。グループ (追加の演算を持つ) の場合、これは次のようになります。構造ごとに異なる型になります。では、これらすべての型に共通するものは何でしょうか。最も明らかなのは、これらはすべて積の合計、つまり代数的データ型であるということです。たとえば、モノイドの場合、任意のモノイド τ で機能するモノイド引数型を作成できます。EitherτEither (τ, τ) ()τ → τEither (Either (τ, τ) τ) ()

data MonoidArgument τ = Mappend τ τ -- here τ τ is the same as (τ, τ)
                      | Mempty      -- here we can just leave the () out

グループ、リング、格子、その他すべての可能な構造に対しても同じことを行うことができます。

これらすべての型について他に何が特別なのでしょうか? そうです、それらはすべてですFunctors! 例:

instance Functor MonoidArgument where
  fmap f (Mappend τ τ) = Mappend (f τ) (f τ)
  fmap f Mempty        = Mempty

したがって、代数の考え方をさらに一般化することができます。これは、何らかの関数を持つ何らかのτ型にすぎません。実際、これを型クラスとして記述できます。f τ → τf

class Functor f ⇒ Algebra f τ where
  op ∷ f τ → τ

これは関数によって決定されるため、しばしば「F 代数」と呼ばれますF。型クラスを部分的に適用できれば、のようなものを定義できますclass Monoid = Algebra MonoidArgument。

余代数

さて、代数とは何か、そしてそれが通常の代数構造の単なる一般化であるということを、よく理解していただけたと思います。では、F 余代数とは何でしょうか。余代数は、代数の「双対」であることを意味します。つまり、代数を取り、矢印をいくつか反転します。上記の定義には矢印が 1 つしか見当たらないので、それを反転します。

class Functor f ⇒ CoAlgebra f τ where
  coop ∷ τ → f τ

以上です！この結論は、少し軽薄に思えるかもしれません（笑）。これは、コジェネバとは何かを説明していますが、それがどのように役立つのか、なぜ私たちが気にするのかについての洞察は実際には提供していません。良い例を 1 つまたは 2 つ見つけたり思いついたりしたら、すぐにそれについて説明します :P。

クラスとオブジェクト

少し調べてみたところ、クラスとオブジェクトを表すためにコアルゲーブラを使用する方法について、良いアイデアが浮かんだと思います。クラス内のオブジェクトのすべての可能な内部状態を含む型があり、クラス自体はオブジェクトのメソッドとプロパティを指定するCコアルゲーブラです。C

代数の例で示したように、任意のに対してa → τやのような関数が多数ある場合、和型を使ってそれらすべてを 1 つの関数に結合できます。双対の「概念」は、型の関数の多数を結合することです。これは、和型の双対、つまり積型を使って行うことができます。したがって、上記の 2 つの関数 (および ) を考えると、次のように 1 つの関数を作成できます。b → τa, b,…Eitherτ → aτ → bfg

both ∷ τ → (a, b)
both x = (f x, g x)

型は(a, a)直接的に関数子であるため、F 余代数の概念に確実に適合します。この特定のトリックにより、さまざまな関数 (または OOP の場合はメソッド) を型の単一の関数にパッケージ化できますτ → f τ。

型の要素は、オブジェクトの内部C状態を表します。オブジェクトに読み取り可能なプロパティがある場合は、そのプロパティは状態に依存している必要があります。これを行う最も明白な方法は、それらをの関数にすることです。したがって、長さプロパティ (例) が必要な場合は、関数を使用します。Cobject.lengthC → Int

引数を受け取って状態を変更できるメソッドが必要です。これを行うには、すべての引数を受け取って新しいを生成する必要があります。と座標を受け取るメソッドCを想像してみましょう。次のようになります。setPositionxyobject.setPosition(1, 2)C → ((Int, Int) → C)

ここで重要なパターンは、オブジェクトの「メソッド」と「プロパティ」がオブジェクト自体を最初の引数として受け取ることです。これは、selfPython のパラメータや他の多くの言語の暗黙のパラメータとまったく同じですthis。coalgebra は基本的に、selfパラメータを受け取る動作をカプセル化します。これが最初の引数CですC → F C。

positionそれでは、すべてをまとめてみましょう。プロパティ、nameプロパティ、関数を持つクラスを想像してみましょうsetPosition。

class C
  private
    x, y  : Int
    _name : String
  public
    name        : String
    position    : (Int, Int)
    setPosition : (Int, Int) → C

このクラスを表すには 2 つの部分が必要です。まず、オブジェクトの内部状態を表す必要があります。この場合、 2 つIntのと 1 つのが保持されるだけですString(これが型ですC)。次に、クラスを表す余代数を作成する必要があります。

data C = Obj { x, y  ∷ Int
             , _name ∷ String }

記述するプロパティは 2 つあります。これらは非常に簡単です。

position ∷ C → (Int, Int)
position self = (x self, y self)

name ∷ C → String
name self = _name self

ここで、位置を更新できるようにする必要があります。

setPosition ∷ C → (Int, Int) → C
setPosition self (newX, newY) = self { x = newX, y = newY }

これは、明示的な変数を持つ Python クラスのようなものですself。これで関数が多数用意できたのでself →、それらを 1 つの関数に結合して coalgebra を作成する必要があります。これは、単純なタプルで行うことができます。

coop ∷ C → ((Int, Int), String, (Int, Int) → C)
coop self = (position self, name self, setPosition self)

型((Int, Int), String, (Int, Int) → c)—for any c — は関数なので、coop必要な形式を持ちます: Functor f ⇒ C → f C。

これを踏まえて、C上coopで示したクラスを指定するコアルゴリズムを作成します。同じ手法を使用して、オブジェクトが持つ任意の数のメソッドとプロパティを指定できることがわかります。

これにより、クラスを扱うために余代数的推論を使用することができます。たとえば、「F 余代数準同型」という概念を導入して、クラス間の変換を表すことができます。これは、構造を保持する余代数間の変換を意味する、恐ろしい響きの用語です。これにより、クラスを他のクラスにマッピングすることについて考えることがはるかに簡単になります。

つまり、F 余代数は、self各オブジェクトの内部状態を含むパラメータに依存する一連のプロパティとメソッドを持つことでクラスを表します。

その他のカテゴリー

これまで、Haskell の型としての代数と余代数について説明してきました。代数は単なる関数τを持つ型でありf τ → τ、余代数は単なる関数を持つ型τですτ → f τ。

しかし、これらのアイデアは Haskell自体に特に結びつくものではありません。実際、これらは通常、型や Haskell 関数ではなく、集合や数学関数の観点から導入されます。実際、これらの概念はあらゆるカテゴリに一般化できます。

あるカテゴリに対して F 代数を定義できますC。まず、関数F : C → C、つまり自己関数が必要です。(すべての HaskellFunctorは、実際にはからの自己関数ですHask → Hask。) 次に、代数は、射を持つAからのオブジェクトにすぎません。余代数は、を除いて同じです。CF A → AA → F A

他のカテゴリを考慮することで何が得られるのでしょうか? そうですね、同じアイデアをさまざまなコンテキストで使用できます。たとえば、モナドです。Haskell では、モナドはM ∷ ★ → ★3 つの演算を持つ型です。

map      ∷ (α → β) → (M α → M β)
return   ∷ α → M α
join     ∷ M (M α) → M α

関数は、がであるmapという事実の単なる証明です。したがって、モナドはとという2 つの演算を持つ関数であると言えます。MFunctorreturnjoin

関数はそれ自体がカテゴリを形成し、関数間の射影はいわゆる「自然変換」です。自然変換とは、ある関数をその構造を維持しながら別の関数に変換する方法にすぎません。こちらはアイデアを説明するのに役立つ素晴らしい記事です。リスト専用のconcatについて説明しています。join

Haskell の関数では、2 つの関数の合成自体が関数になります。疑似コードでは、次のように記述できます。

instance (Functor f, Functor g) ⇒ Functor (f ∘ g) where
  fmap fun x = fmap (fmap fun) x

joinこれは、をからのマッピングとして考えるのに役立ちますf ∘ f → f。の型joinはです。直感的に、すべての型∀α. f (f α) → f αに有効な関数がの変換として考えられることがわかります。αf

returnは同様の変換です。その型はです∀α. α → f α。これは異なっているように見えます。最初のものαは関数「内」にありません。幸いなことに、恒等関数を追加することでこれを修正できます。∀α. Identity α → f α変換も同様returnですIdentity → f。

これで、モナドを、f演算およびを伴う関数に基づく単なる代数として考えることができますf ∘ f → f。これは見覚えがありませんか? これは、演算およびを伴う単なるIdentity → f型であるモノイドに非常に似ています。ττ × τ → τ() → τ

つまり、モナドはモノイドとまったく同じですが、型の代わりに関数子があります。これは同じ種類の代数ですが、カテゴリが異なります。(私の知る限り、「モナドは自己関数子のカテゴリ内のモノイドにすぎない」というフレーズはここから来ています。)

f ∘ f → fこれで、とという 2 つの演算ができましたIdentity → f。対応する余代数を得るには、矢印を反転するだけです。これにより、f → f ∘ fとという 2 つの新しい演算が得られます。f → Identity上記のように型変数を追加して、これらを Haskell 型に変換し、∀α. f α → f (f α)とを得ることができます∀α. f α → α。これは、コモナドの定義とまったく同じです。

class Functor f ⇒ Comonad f where
  coreturn ∷ f α → α
  cojoin   ∷ f α → f (f α)

したがって、コモナドは、自己関数のカテゴリ内の余代数です。

プログラミングの文脈で「coalgebra」とはどういう意味ですか? 質問する

ベストアンサー1

代数

F-代数

余代数

クラスとオブジェクト

その他のカテゴリー

おすすめ記事