86

多くのリンクをたどったり、圏論の教科書を開いたりする必要のない、再帰スキームと共帰スキーム (カタモルフィズム、アナモルフィズム、ハイロモルフィズムなど) の非常に単純で理解しやすい説明を探しています。私はこれらのスキームの多くを無意識のうちに再発明し、コーディングの過程で頭の中でそれらを「適用」したと確信しています (私たちの多くが持っていると確信しています)。使用が呼び出されます。(OK、嘘をつきました。私はそれらのいくつかについて読んだだけで、この質問を促しました。しかし、今日まで、私は手がかりがありませんでした。)

プログラミング コミュニティ内でのこれらの概念の普及は、たとえばウィキペディアだけでなく、他の場所でも、出くわす傾向のある禁止された説明や例によって妨げられてきたと思います。

それはまた、おそらく彼らの名前によって妨げられてきました. いくつかの代替の数学的な名前 (バナナや有刺鉄線についての何か?) があると思いますが、私が使用する再帰スキームのよりクールな名前が何であるかもわかりません。

二分木などの抽象的なデータ型ではなく、単純な実世界の問題を表すデータ型の例を使用すると役立つと思います。

4

3 に答える 3

49

非常に大まかに言えば、カタモルフィズムは をわずかに一般化したものであり、アナモルフィズムは をわずかにfold一般化したものです。unfold. (そしてハイロモーフィズムは展開とそれに続く折り畳みです。) 圏論との関係をより明確にするために、通常はより厳密な形式で提示されます。より密な形式により、データ (最初の代数の必然的に有限の積) と余データ (最終的な代数のおそらく無限の積) を区別できます。この区別により、フォールドが無限リストで呼び出されないことが保証されます。カタモルフィズムとアナモルフィズムが一般的に書かれる面白い方法のもう 1 つの理由は、(関手から生成された) F 代数と F 積分代数を操作することによって、それらをリストに対して一度ではなく、完全に一度に書くことができることです。二分木など。これは、なぜそれらがすべて同じものであるかを明確にするのに役立ちます。

しかし、純粋な直感の観点からは、カタとアナを還元と生産と考えることができ、それだけです。

編集：もう少し

メタモルフィズム (Gibbons) は、裏返しの hylo のようなものです。折り畳みの後に展開が続きます。したがって、これを使用してストリームを破棄し、潜在的に異なる構造を持つ新しいストリームを構築できます。

Ekmett は、文献のさまざまなスキームへの素敵な「フィールド ガイド」を投稿しました: http://comonad.com/reader/2009/recursion-schemes/

ただし、「直感的な」説明は簡単ですが、リンクされたコードはそうではありません。これらのいくつかに関するブログ投稿は、複雑/禁じられた側面で少しかもしれません.

そうは言っても、おそらく組織型を除いて、動物園の残りの部分は、ほとんどの場合、必ずしも直接考えたいと思うものではないと思います. hylo と meta を「理解」すれば、それらだけでほぼ何でも表現できます。通常、他のモーフィズムは制限が厳しくなります (ただし、「無料で」より多くのプロパティが得られます)。

于 2011-08-04T15:06:23.993 に答える
23

最もカテゴリ理論的な（ただし、「多くのリンクをクリック」することを回避できる「テリトリーマップ」を提供することに関連する）から、より単純でより自己完結型へのいくつかの参照：

  • 「バナナと有刺鉄線」の語彙に関する限り、これはMeijer、Fokkinga＆Pattersonの元の論文（および他の著者によるその続編）からのものであり、要約すると、あまりかわいい選択肢と同じように表記が重いです： 「名前」（バナナなど）は、それらが固定されている構造のASCII表記のグラフィカルな外観への単なるショートカットです。たとえば、カタモルフィズム（つまりフォールド）はで表され(| _ |)、括弧付きのパーは「バナナ」のように見えるため、この名前が付けられています。これは、最も頻繁に「不可侵」と呼ばれる紙であるため、私があなたである場合に最初に調べることはありません。

  • これらの再帰スキームの基本的なリファレンス（より正確には、これらの再帰スキームへのリレーショナルアプローチ）は、Bird＆de Moorのプログラミング代数です（この本は、オンデマンド印刷以外では利用できませんが、中古で入手できるコピーがあります） ＆それはライブラリにあるはずです）。それでも「アカデミック」である場合は、ポイントフリープログラミングのよりペースのある詳細な説明が含まれています。この本は、自己完結型の方法ではありますが、いくつかの圏論的な語彙を紹介しています。それでも、演習（論文にはない）は役に立ちます。

  • Lex Augustjeinによる射の並べ替えでは、さまざまなデータ構造で並べ替えアルゴリズムを使用して、再帰スキームを説明します。これは、構造上、ほとんど「ダミーの再帰スキーム」です。

    このプレゼンテーションでは、平均的なプログラマーにとって不必要に威圧的になりがちな圏論による通常のアプローチではなく、関数型プログラミングで役立つ再帰のパターンとして、さまざまな射を簡単な方法で紹介する機会が与えられます。

  • シンボルのないプレゼンテーションを作成するための別のアプローチは、ジェレミー・ギボンズの「プログラミングの楽しさにおける折り紙プログラミング」の章ですが、前の章と一部重複しています。その参考文献は、トピックの紹介のツアーを提供します。

    編集：ジェレミー・ギボンズは、この質問を読んだ後、本のWebページに本全体の参考文献へのリンクを追加したことを知らせてくれました。お楽しみください！

これらの最後の2つの参考文献は、（cata | ana | hylo | para）射の確かな説明にすぎないのではないかと思いますが、これで、より多くの表記が多い出版物に見られる代数的形式を破ることができます。私は、これらの4つ以外の（共）再帰スキームの厳密に非圏論的な説明を知りません。

于 2011-08-05T23:28:32.830 に答える
17

Tim Williams は昨夜、London Haskell User Group で、あなたが言及したそれぞれの動機付けとなる例を挙げて、再帰スキームについて素晴らしい講演を行いました。スライドをご覧ください:

http://www.timphilipwilliams.com/slides.html

スライドの最後には、すべての通常の容疑者 (レンズ、バナナ、有刺鉄線のアラカルトなど) への参照があり、「Origami Programming」をグーグルで検索することもできます。

アップロードすると、ビデオがここに表示されます。

http://www.youtube.com/user/LondonHaskell

編集問題のリンクのほとんどは、上記の huitseeker の回答にあります。

于 2013-03-28T16:56:17.813 に答える