[解決済み】プログラミングの文脈で「calgebra」とはどういう意味ですか?
質問
関数型プログラミングや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つの関数(名前は
f
と
g
) のように、1つだけ作成することができます。
both ∷ τ → (a, b)
both x = (f x, g x)
タイプ
(a, a)
は素直にファンクターなので、F-CALの概念に確実に合致します。この特別なトリックを使うと、たくさんの異なる関数、つまりOOPではメソッドを、型
τ → f τ
.
この型の要素は
C
を表します。
内部
の状態です。オブジェクトに読み取り可能なプロパティがある場合、それらは状態に依存できる必要があります。これを行うための最も明白な方法は、それらを
C
. したがって、長さのプロパティが必要な場合 (例.
object.length
という関数があります。
C → Int
.
引数を取り、状態を変更できるメソッドが欲しい。これを実現するためには、すべての引数を受け取って新しい
C
. ここで
setPosition
メソッドで
x
と
y
の座標を指定します。
object.setPosition(1, 2)
. このようになります。
C → ((Int, Int) → C)
.
ここで重要なのは、オブジェクトのメソッドやプロパティは、オブジェクト自身を第1引数として取るということです。これはちょうど
self
Pythonのパラメータや暗黙の
this
は、他の多くの言語で使用されています。連立方程式は,基本的に
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
と
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つの代数関数にする必要があります。これは単純なタプルを使って行うことができます。
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
という事実を証明しただけの関数です。
M
は
Functor
. つまり、モナドとは、単なるファンクタで
に
の演算を行います。
return
と
join
.
ファンクターはそれ自体がカテゴリを形成し、ファンクター間のモルヒズムはいわゆる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 → f
と
Identity → f
. 見覚えはありませんか?これはモノイドにとても似ていて、モノイドは単にある型の
τ
という操作で
τ × τ → τ
と
() → τ
.
つまり、モナドはモノイドと同じで、型を持つ代わりにファンクタを持つということです。カテゴリーが違うだけで、同じような代数なんです。(私の知る限り、A monad is just a monoid in the category of endofunctors"というフレーズはここから来ています。)
さて、この2つの操作です。
f ∘ f → f
と
Identity → f
. 対応する代数を得るには、矢印を反転させればよい。これによって、2つの新しい演算が得られる。
f → f ∘ f
と
f → Identity
. 上記のように型変数を追加することで、これらを Haskell の型に変換することができ、次のようになります。
∀α. f α → f (f α)
と
∀α. f α → α
. これはコモナドの定義と同じように見える。
class Functor f ⇒ Comonad f where
coreturn ∷ f α → α
cojoin ∷ f α → f (f α)
ということは、コモナドというのは 連立方程式 を、エンドファンクターのカテゴリーで表現しています。
関連
-
[解決済み] Spark - Sparkでパーセンタイルを計算する方法は?
-
[解決済み] ScalaのバージョンをScala本体から取得するにはどうしたらいいですか?
-
[解決済み] 末尾再帰とは何ですか?
-
[解決済み] JavaScriptには、与えられた範囲内の範囲を生成する "range() "のようなメソッドがありますか?
-
[解決済み] (関数型)リアクティブプログラミングとは?
-
[解決済み] クロージャ」と「ラムダ」の違いは何ですか?
-
[解決済み] Hindley-Milnerのどの部分が理解できないのでしょうか?
-
[解決済み] モナドはエンドファンクタのカテゴリではただのモノイドですが、何か問題でも?
-
[解決済み】関数型プログラミングはGoFデザインパターンに取って代わるか?
-
[解決済み】Scalaのyieldとは何ですか?
最新
-
nginxです。[emerg] 0.0.0.0:80 への bind() に失敗しました (98: アドレスは既に使用中です)
-
htmlページでギリシャ文字を使うには
-
ピュアhtml+cssでの要素読み込み効果
-
純粋なhtml + cssで五輪を実現するサンプルコード
-
ナビゲーションバー・ドロップダウンメニューのHTML+CSSサンプルコード
-
タイピング効果を実現するピュアhtml+css
-
htmlの選択ボックスのプレースホルダー作成に関する質問
-
html css3 伸縮しない 画像表示効果
-
トップナビゲーションバーメニュー作成用HTML+CSS
-
html+css 実装 サイバーパンク風ボタン
おすすめ
-
[解決済み] Scala underscore - ERROR: 展開された関数のパラメータ型が見つかりません。
-
[解決済み] expr() での lit() の使用について
-
[解決済み] 実行時に変数の型を取得したい
-
[解決済み] scalaのforeachループ
-
[解決済み] MapのmapValuesとtransformの違いについて
-
[解決済み] Spark - CSVファイルをDataFrameとして読み込む?
-
[解決済み] self-typesとtrait subclassの違いは何ですか?
-
[解決済み】Scala 2.8のコレクション・ライブラリは「歴史上最も長い遺書」のケースか?[クローズド] Scala
-
[解決済み】コマンドラインパラメータを解析する最良の方法?[クローズド]
-
[解決済み】Scala 2.8における<:<、<%<、=:=の意味と、それらのドキュメントはどこにあるのか?