Clever Geek Handbook

プログラマーのためのカテゴリー理論。指に

こんにちは同僚。真面目な、学術文献







への私たちの揺るぎない関心を発展させて、私たちはカテゴリーの理論に到達しました。バルトシュMilevskyの有名なプレゼンテーションでこのトピックは、すでにしている現れHabréにし、今ではそのような指標の自慢することができます： それはすべてのより快適な、我々は比較的新鮮な材料を見つけることができたということで優れているとし、カテゴリーの理論に可能な導入などの短いと同時にお楽しみいただけます（2020年1月）を、。このトピックに興味を持ってもらえることを願っています。











親愛なる読者であるあなたと私が同様の問題に直面した場合、あなたはかつて「一体何がモナドなのか」という質問に苦しめられました。それからあなたはこの質問をググって、抽象的な数学のウサギの穴をこっそりと滑り落ち、functors、monoids、categoriesに巻き込まれました彼らがあなたをここに連れてきた質問をすでに忘れていることに気付くまで。機能的なプログラミング言語をこれまでに見たことがない場合、この経験は非常に圧倒される可能性がありますが、心配しないでください！私はあなたのために密な数学の多くのページを研究し、このトピックに関する何時間もの講義を見てきました。そこで、その必要性を節約するために、ここでトピックを要約し、カテゴリ理論を適用して、今すぐ機能的なスタイルで考える（そしてコードを書く）方法を示します。



この記事は、機能プログラミングの分野で自分自身を「初心者」と見なし、Scala、Haskell、または他の同様の言語を使い始めたばかりの人を対象としています。この記事を読んだ後は、カテゴリー理論の基礎を解釈し、その原則を「現場で」特定することにもう少し自信が持てるようになります。また、理論数学を試したことがある場合は、ここで触れている概念について直接言及することは控えてください。原則として、ここに書かれているよりもはるかに多くのことが言えますが、好奇心旺盛なプログラマーにとってはこの記事で十分です。



基礎



では、カテゴリとは正確には何であり、それはプログラミングとどのように関連していますか？プログラミングで使用される多くの概念と同様に、カテゴリは非常に単純なもので、派手な名前が付いています。これは、いくつかの追加の制限がある、ラベル付きの有向グラフです。カテゴリ内の各ノードは「オブジェクト」と呼ばれ、その各エッジは「モーフィズム」と呼ばれます。







ご想像のとおり、すべての有向グラフがカテゴリであるとは限りません。グラフをカテゴリと見なすには、いくつかの追加の基準を満たす必要があります。次の図では、各オブジェクトがそれ自体を指すモーフィズムを持っていることに注意してください。これは同一の形態であり、各オブジェクトは、グラフがカテゴリと見なされるようになっている必要があります。次に、オブジェクトがその通知A射有するf指示をB、および同様に、オブジェクトにBは。をg指すモーフィズムがありCます。以下からのパスがあるのでAへBとからBにはC、当然のパスが存在するAのC権利は、？これは、射のためのように、必ずしも連想組成物を行わなければならない射のための次の要求の種類でありf: A = > B 、そしてg: B = > C射がありますh = g(f): A = > C。



これらの計算はすでに少し抽象的なように見えるかもしれないので、この定義を満たし、Scalaで書かれた例を見てみましょう。 



trait Rock
trait Sand
trait Glass
def crush(rock: Rock): Sand
def heat(sand: Sand): Glass


この例では、関係が少し簡単になると思います。石を砂に消すのは物体を物体rockに変える形態であり、sandガラスを砂から精錬するのは物体を物体sandに変える形態ですglass。この場合、これらの関係の構成は間違いなく次のようになります。 



val glass: Glass = heat(crush(rock))


Predefどのオブジェクトに対しても同じオブジェクトを返す関数を作成することは難しくないため、 ID関数（Scalaで定義）もあります。したがって、このシステムは、かなり単純なものではありますが、カテゴリです。



カテゴリに精通している







ここで、カテゴリー理論の用語をもう少し深く掘り下げて、マグマと呼ばれるカテゴリーから始めます。この基本的な概念にまだ慣れていない場合は、マグマは単なるバイナリ操作、つまり2つの値に対する操作であり、その結果として新しい値が取得されることを説明します。詳細に立ち入らないために、ここではすべてのバイナリ操作のセットが実際にカテゴリであることを証明することはしませんが、詳細に興味がある人は、BartoszMilevskyによる次の記事を読むことをお勧めします。加算から乗算までのすべての算術は、マグマカテゴリによって統合されたサブカテゴリに属します（図を参照）。



ここでは、次の継承順序が適用されます。



  • 1.マグマ：すべてのバイナリ操作
  • 2.セミグループ：連想的であるすべてのバイナリ操作
  • o : .
  • 3. : ,
  • o : , (aka )


したがって、前の例に戻ると、加算と乗算はどちらもモノイドです。これらは連想的(a + (b + c) = (a + b) + c)であり、単一の要素（ax 1 = 1 xa = a）を持っているためです。この図の最後の円には、セミグループやモノイドとは異なる埋め込み原則が適用される可能性のある準グループが含まれています。準グループは、可逆的なバイナリ操作です。この特性を説明するのはそれほど簡単ではないので、このトピックに捧げられたMarkSimanによる一連の記事を参照してください。二項演算は可逆任意の値に対する場合aとb、そのような値があるxとy、その変換を可能にするaにb..。私はそれがトリッキーに聞こえることを知っています。明確にするために、次の減算の例を見てみましょう。 



val x = a - b
val y = a + b
assert(a - x == b)
assert(y - a == b)


注意：それy自体は減算に参加しませんが、例は引き続きカウントされます。カテゴリ内のオブジェクトは抽象化されており、ほとんど何でもかまいません。この場合には、いずれかのことが重要であるaとbそれが発生することができ、これらの文が本当残ります。



コンテキスト内のタイプ



特定の分野に関係なく、タイプのトピックは、プログラミングにおけるデータタイプの意味を理解している人には明確である必要があります。整数、ブール、浮動小数点などはすべてタイプですが、理想的なプラトンタイプを言葉でどのように説明しますか？一連のブログ投稿に変わった彼の著書「プログラマーのためのカテゴリー理論」の中で、Milevskyはタイプを単に「値のセット」として説明しています。たとえば、ブール値は、値「true」と「false」（false）を含む有限のセットです。 charはすべての数字文字の有限のセットであり、stringはcharの無限のセットです。



問題は、カテゴリー理論では、セットから離れて、オブジェクトと形態の観点から考える傾向があることです。しかし、型が単にセットであるという事実は避けられません。幸いなことに、これらのセットのカテゴリ理論には場所があります。これは、オブジェクトが抽象化されており、何でも表すことができるためです。したがって、オブジェクトはセットであると言う権利があり、さらに、Scalaプログラムをカテゴリと見なします。ここで、タイプはオブジェクトであり、関数はモーフィズムです。これは多くの人にとって痛々しいほど明白に思えるかもしれません。結局のところ、Scalaではオブジェクトの処理に慣れていますが、それを明示的に指摘する価値があります。



Javaなどのオブジェクト指向の言語を使用したことがある場合は、おそらく汎用型の概念に精通しているでしょう。これらは次のようなものですLinkedListまたは、Scalaの場合、Option[T]ここでTは、ある構造に格納されている基になるデータタイプを表します。最初のタイプの構造が保持されるように、あるタイプから別のタイプへのマッピングを作成したい場合はどうなりますか？構造を維持するためのカテゴリ間のマッピングとして定義される、ファンクタの世界へようこそ。プログラミングでは、通常、カテゴリをそれ自体にマップするのに役立つ、エンドファンクターと呼ばれるファンクターのサブカテゴリを操作する必要があります。ですから、私がファンクターについて話すとき、私はエンドファンクターを意味すると言います。



ファンクターの例として、Option[T]石、砂、ガラスについて言及した前の例と併せて、Scalaタイプを見てみましょう。 



val rockOpt: Option[Rock] = Some(rock)


上に、Rock前に定義したタイプがありますが、でラップされていOptionます。これは一般的なタイプであり（さらに、これについては以下で詳しく説明します）、オブジェクトが探している特定のエンティティであるか、他の言語Noneと比較できることを示していnullます。



ファンクターを使用しなかった場合、関数crush()をRockに適用する方法を想像できます。if これにOptionは、その状況を処理するためにオペレーターに頼る必要がありNoneます。 



var sandOpt: Option[Sand] = None
if(rockOpt != None) {
  sandOpt = Some(crush(rockOpt.get))
}


これはサイドトラックと言えるかもしれませんが、varは使用しないでください。このようなコードはScalaではいくつかの理由で不適切です。繰り返しますが、トピックに戻ります。JavaまたはC＃では、これは問題にはなりません。自分の値が期待したタイプであるかどうかを確認し、それを使ってやりたいことを何でもします。しかし、ファンクターの力で、すべてが機能でもう少しエレガントに行うことができますmap()： 



val sandOpt: Option[Sand] = rockOpt.map(crush)


ブーム、1行で完了です。三元演算子などを使用して、最初の例を1行にまとめることは可能ですが、それほど簡潔には成功しませんでした。この例は、その単純さにおいて本当に素晴らしいです。ここで起こっていることmap()は次のとおりです。関数を受け取り、その関数を（数学的な意味で）それ自体にマップします。構造がされてOption保存さが、今ではどちらか含まれているSand、またはNone、その代わりのRockかNone。これは次のように説明できます。







すべてがどれほど美しく並んでいるか、すべてのオブジェクトと形態が両方のシステムで保持されていることに注目してください。したがって、中央のモルフィズムは、からTへのマッピングを表す関数Option[T]です。



一緒



これで、最終的に元の質問「モナドとは何ですか」に戻ることができますか？グーグルしようとすると盲目的につまずく可能性のある答えがあり、次のように聞こえます。モナドはエンドファンクターのカテゴリーの単なるモノイドであり、その後に「何が問題なのか」という非常に皮肉な発言が続くことがよくあります。原則として、このように彼らはこのトピックのすべてがどれほど難しいかを冗談めかして見せようとしますが、実際、すべてがそれほど怖いわけではありません-結局のところ、私たちはこのフレーズが何を意味するのかをすでに理解しています。もう一度一歩ずつ進んでいきましょう。



まず、モノイドは連想バイナリ操作であり、それぞれにニュートラル（単一）要素が含まれていることがわかります。第二に、エンドファンクターを使用すると、構造を維持しながら、カテゴリーをそれ自体にマップできることがわかります。したがって、モナドは、関数を受け入れてそれ自体にマッピングするためのメソッドを維持する、ある種のラッパータイプです（上記の一般的なタイプの例のように）。List-これはモナドでありOption（上記で検討したもののように）、モナドであり、誰かがあなたにそれを言うかもしれずFuture、モナドでもあります。例： 



val l: List[Int] = List(1, 2, 3)
def f(i: Int) = List(i, i*2, i*3)
println(l.flatMap(f)) // : List(1, 2, 3, 2, 4, 6, 3, 6, 9)


一見シンプルですね。少なくとも、そのような概念の使用法が一見完全に明確でなくても、ここですべてを把握することは難しくないという感覚があるはずです。


More articles:


All Articles