1. ホーム
  2. スカラ

[解決済み】プログラミングの文脈で「calgebra」とはどういう意味ですか?

2022-05-02 17:36:51

質問

関数型プログラミングやPLTの世界で、特にオブジェクト、コモナド、レンズなどについての議論の際に、「coalgebras」という言葉を何度か耳にしたことがあります。この用語をググると、これらの構造を数学的に説明したページが表示されますが、私にはほとんど理解不能です。どなたか、プログラミングの文脈におけるコールゲブラの意味、その意義、そしてオブジェクトやコモナドとの関係を説明していただけませんか?

どのように解決するのですか?

アルジェブラ

の考え方を理解するところから始めるといいと思います。 代数 . これは群、環、モノイドなどの代数的構造を一般化したものに過ぎない。ほとんどの場合、これらのものは集合の観点から紹介されるが、我々は友人同士なので、代わりにHaskellの型について話すことにする。(ギリシャ文字を使わないわけにはいきません。何でもクールに見せてくれますからね!)

では、代数とは何かというと、それは単なる型である。 τ と、いくつかの関数と恒等式があります。これらの関数は、異なる数の引数をとる。 τ を生成し τ のように見える。 (τ, τ,…, τ) → τ . また、identity"の要素を持つことができます。 τ のように、いくつかの関数で特別な振る舞いをします。

その最も単純な例がモノイドである。モノイドとは、任意の型 τ を持つ関数で mappend ∷ (τ, τ) → τ とアイデンティティ mzero ∷ τ . 他の例としては、群(これはモノイドに似ていますが、さらに invert ∷ τ → τ 関数)、環、格子など。

すべての関数は τ が、異なるアリティを持つことができる。これらは次のように書き出すことができます。 τⁿ → τ ここで τⁿ のタプルにマップされます。 n τ . このように、アイデンティティを次のように考えるのは理にかなっています。 τ⁰ → τ ここで τ⁰ は、単に空のタプル () . つまり,代数という概念は単純化され,ある型にいくつかの関数が追加されたものに過ぎない。

代数とは、数学の一般的なパターンをコードと同じようにquot;factored"したものに過ぎないのです。前述したモノイド、群、格子など、興味深いものがすべて同じようなパターンに従っていることに人々は気付き、それを抽象化したのである。この方法の利点は、プログラミングと同じで、再利用可能な証明を作り、ある種の推論を容易にすることである。

F-アルゲブラ

しかし、因数分解はまだ終わっていない。これまでのところ、私たちはたくさんの関数 τⁿ → τ . 実は、これらを1つの関数にまとめるという巧妙なトリックができるのです。特に、モノイドについて見てみましょう。 mappend ∷ (τ, τ) → τmempty ∷ () → τ . これらを 1 つの関数にするには、sum 型を使用します。 Either . このような感じになります。

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

この変換を繰り返し使って、実際に すべて τⁿ → τ 関数を1つにまとめました。 任意の 代数学 (実際には、任意の数の関数に対してこれを行うことができます。 a → τ , b → τ などは 任意の a, b,… .)

これによって、代数を型として語ることができるようになります τ を持つ。 シングル の関数があります。 Either を1つの τ . モノイドの場合、この混乱は Either (τ, τ) () グループ(これは余分な τ → τ の操作)であれば、それは Either (Either (τ, τ) τ) () . 構造が違えば型も違うんです。では、これらの型に共通することは何でしょうか?最も明白なのは、これらはすべて積の和、つまり代数的なデータ型に過ぎないということだ。例えば、モノイドの場合、次のようなモノイド引数型を作ることができます。 任意の monoid τ:

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 τ → τ

これはよくquot;F-algebra"と呼ばれるが、それはファンクターである F . もし型付けを部分的に適用することができれば,次のようなものを定義することができます. class Monoid = Algebra MonoidArgument .

Coalgebras

さて,代数とは何か,そしてそれが通常の代数的構造を一般化したものであることをよく理解してもらえたと思う。では、F-coalgebraとは何だろうか?F-coalgebraは代数のquot;dual;quot;であることを意味する。上の定義では矢印が1つしかないので、それを反転させる。

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

と、これだけです! さて、この結論は少し軽薄に見えるかもしれません(へっ)。それは、あなたに しかし、それがどのように役に立つのか、なぜ私たちがそれを気にするのかについては、何の洞察も与えてはくれません。この点については、良い例を見つけたり、思いついたりしたら、もう少し詳しく説明します :P.

クラスとオブジェクト

少し読んでみて、クラスとオブジェクトを表現するためにcolgebrasを使用する方法について良いアイデアを得たと思います。私たちは C は、クラス内のオブジェクトのすべての可能な内部状態を含むものです。 C は、オブジェクトのメソッドとプロパティを指定する。

代数の例で示したように、もし私たちが a → τb → τ に対して、任意の a, b,… を使用すると、それらをすべて1つの関数にまとめることができます。 Either という和の型があります。という型の関数の束を組み合わせるという、二重の概念"notice"があります。 τ → a , τ → b といった具合です。これは、和型の双対である積型を使って行うことができます。つまり、上の2つの関数(名前は fg ) のように、1つだけ作成することができます。

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

タイプ (a, a) は素直にファンクターなので、F-CALの概念に確実に合致します。この特別なトリックを使うと、たくさんの異なる関数、つまりOOPではメソッドを、型 τ → f τ .

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

引数を取り、状態を変更できるメソッドが欲しい。これを実現するためには、すべての引数を受け取って新しい C . ここで setPosition メソッドで xy の座標を指定します。 object.setPosition(1, 2) . このようになります。 C → ((Int, Int) → C) .

ここで重要なのは、オブジェクトのメソッドやプロパティは、オブジェクト自身を第1引数として取るということです。これはちょうど self Pythonのパラメータや暗黙の this は、他の多くの言語で使用されています。連立方程式は,基本的に self というパラメータがあります。 CC → 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つの IntString . (これは私たちのタイプ 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つの代数関数にする必要があります。これは単純なタプルを使って行うことができます。

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

タイプ ((Int, Int), String, (Int, Int) → c) -について 任意の c -はファンクタなので coop は、私たちが望むような形になります。 Functor f ⇒ C → f C .

これを考えると C とともに coop は、上であげたクラスを指定する連立方程式を形成します。これと同じ手法で、オブジェクトが持つべきメソッドやプロパティをいくつでも指定できることがおわかりいただけると思います。

このように、クラスを扱うのに代数的推論を使うことができます。例えば、クラス間の変換を表現するために、quot;F-coalgebra homomorphism"の概念を持ち込むことができます。これは、構造を保存する代数間の変換を意味する、恐ろしい響きのある用語です。これによって、クラスを他のクラスにマッピングすることを考えるのがずっと簡単になります。

要するに、F-coalgebraは、クラスを表すために、プロパティとメソッドの束を持ち、それらがすべて self パラメータには、各オブジェクトの内部状態が格納されています。

その他のカテゴリー

これまで、Haskellの型として代数と石炭圏について話してきました。代数は単なる型です τ という関数と f τ → τ であり、連立方程式は単なる型である τ という関数と τ → f τ .

しかし、これらのアイデアをHaskellに結びつけるものは何もありません。 それ自体 . 実際、型やHaskell関数ではなく、集合や数学関数で紹介されるのが普通です。実際、これらの概念を一般化すると 任意の カテゴリを作成します。

あるカテゴリに対してF代数を定義することができます。 C . まず、ファンクター F : C → C -つまり エンドファンクション . (すべてのHaskell Functor のエンドファンクションです。 Hask → Hask .) この場合、代数は単なるオブジェクトである A から C をモルヒズムとする F A → A . 連立方程式も同じですが A → F A .

他のカテゴリーを考えることで、何が得られるのでしょうか。それは、同じアイデアを異なる文脈で使えることです。例えばモナド。Haskellではモナドはある型 M ∷ ★ → ★ という3つの演算があります。

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

map という事実を証明しただけの関数です。 MFunctor . つまり、モナドとは、単なるファンクタで の演算を行います。 returnjoin .

ファンクターはそれ自体がカテゴリを形成し、ファンクター間のモルヒズムはいわゆるquot;自然変換"と呼ばれるものです。自然変換とは、あるファンクタをその構造を保ったまま別のファンクタに変換する方法に過ぎません。 ここで この考え方を説明した素晴らしい記事があります。この記事では 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 → fIdentity → f . 見覚えはありませんか?これはモノイドにとても似ていて、モノイドは単にある型の τ という操作で τ × τ → τ() → τ .

つまり、モナドはモノイドと同じで、型を持つ代わりにファンクタを持つということです。カテゴリーが違うだけで、同じような代数なんです。(私の知る限り、A monad is just a monoid in the category of endofunctors"というフレーズはここから来ています。)

さて、この2つの操作です。 f ∘ f → fIdentity → f . 対応する代数を得るには、矢印を反転させればよい。これによって、2つの新しい演算が得られる。 f → f ∘ ff → Identity . 上記のように型変数を追加することで、これらを Haskell の型に変換することができ、次のようになります。 ∀α. f α → f (f α)∀α. f α → α . これはコモナドの定義と同じように見える。

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

ということは、コモナドというのは 連立方程式 を、エンドファンクターのカテゴリーで表現しています。