問題タブ [recursion-schemes]

私はカタモルフィズムについて学ぼうとしています。ウィキペディアの記事と、 Inside F#ブログの F#に関する一連のトピックの最初の 2 つの投稿を読みました。

これがフォールドの一般化であることは理解しています (つまり、値のリストを別のリストに含めて、多くの値の構造を 1 つの値にマッピングします)。そして、fold-list と fold-tree が標準的な例だと思います。

これは、LINQ のAggregate演算子またはその他の高次メソッドを使用して、C# で実行できることを示すことができますか?

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

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

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

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

言うまでもなく、Haskell の標準的な構造は

素晴らしく、非常に便利です。

Agdaで同様のものを定義しようとしています（完全を期すために記載します）

fは厳密に正であるとは限らないため、失敗します。これは理にかなっています。適切に選択することで、この構造から簡単に矛盾を得ることができます。

私の質問は次のとおりです。Agda で再帰スキームをエンコードする希望はありますか? それは行われましたか？何が必要ですか？

関数型プログラミングや PLT サークルで「coalgebras」という用語を何度か耳にしたことがあります。特に、オブジェクト、コモナド、レンズなどに関する議論の場合はそうです。この用語をグーグルで検索すると、これらの構造の数学的な説明を提供するページが表示されますが、これは私にはほとんど理解できません。プログラミングのコンテキストでコールゲブラが何を意味するのか、その重要性は何か、オブジェクトやコモナドとどのように関係するのか、誰か説明してもらえますか?

Hackage ライブラリのアナモフィズムを使用して壊れたfilter関数を実装しました。recursion-schemes

filterこの関数は:の忠実な実装ではありませんxfilter odd [1..5]が、機能xfilter odd [0,0]しません。で明示的な再帰を使用して「再試行」を実装しようとしたphi後、それをパラモーフィズムで再実装したため、次のように終了しましたana . para。

これで問題ありませんが、再試行を明示的に表現しphi、外部で実行しようとしました。

Rightは「新しい要素を生成する」ことをLeft意味し、「新しいシードで再試行する」ことを意味します。

の署名はphi、リストに特化したアポモーフィズムの最初の引数にかなり似ているように見え始めました。

([a] -> Either [a] [a]対[a] -> Prim [a] [a] (Either [a] [a])

だから、アポモルフィズムやその他の一般化された展開を使用してフィルタリングを実装することは可能ですか、ana . paraそれとも私が期待できる最高のものですか?

折り畳みを使用できることは知っていますが、問題は特に展開に関するものです。

この記事を書いた後、私はお金を口に出すことに決め、私の以前のプロジェクトを使用するように変換し始めましたrecursion-schemes。

問題のデータ構造は遅延 kdtreeです。明示的および暗黙的な再帰の実装を見てください。

これは、主に次の行に沿った単純な変換です。

に

シバン全体のベンチマークを行ったところ、このバージョンは通常のバージョンよりも約 2 倍遅いことがわかりました (実行KDTreeF全体をここで見つけてください)。

Fixここで私を遅くしているのは、追加のラッパーだけですか? そして、これに対して私にできることはありますか？

警告:

• 現時点では、これは (V3 Double) に特化しています。
• これは、アナモフィズム アプリケーションのカタ - アフターです。ハイロモーフィズムは kdtree には適していません。
• cata (fmap foo algebra)数回使用しています。これは良い習慣ですか？
• エドワーズrecursion-schemesパッケージを使用しています。

編集1：

これは関連していますか？https://ghc.haskell.org/trac/ghc/wiki/NewtypeWrappersnewtype Fix f = Fix (f (Fix f))「無料」 じゃない？

編集2：

別の一連のベンチマークを実行しました。今回はツリーの構築と分解をテストしました。ベンチマークはこちら: https://dl.dropboxusercontent.com/u/2359191/2014-05-15-kdtree-bench-03.html

Core の出力は、中間データ構造が完全に削除されていないことを示しており、現在は線形検索が優勢であることは驚くべきことではありませんが、KDTreeFs は s よりわずかに高速ですKDTree。あまり関係ありませんが。

この質問に対する答えは、Scala の Option での fold メソッドがカタモフィズムであることを示唆しています。ウィキペディアによると、カタモフィズムは「初期代数から他の代数への固有の準同型写像です。この概念は、関数型プログラミングに折り畳みとして適用されています」。それは公平に思えますが、 F-algebrasのカテゴリの初期オブジェクトとしての初期代数に私を導きます。

したがって、Option の折り畳みが本当にカタモフィズムである場合、Option が最初のオブジェクトである F 代数の圏を作成するために、ファンクター F が必要です。このファンクターが何であるかわかりません。

タイプのリストの場合A、ファンクタFはF[X] = 1 + A * Xです。List は再帰的なデータ型であるため、これは理にかなっています。したがって、上記の if Xis List[A]then は、型のリストがA空のリスト ( 1)、または ( ) anと a+のペア ( ) のいずれかであると読み取ります。しかし Option は再帰的ではありません。(Nothing または an )になります。したがって、ファンクターがどこにあるのかわかりません。*AList[A]Option[A]1 + AA

明確にするために、 Option は にかかるという点で既にファンクターであることを認識していますAがOption[A]、リストに対して行われることは異なり、Aは修正され、データ型を再帰的に構築する方法を記述するためにファンクターが使用されます。

関連する注意事項として、カタモルフィズムでない場合は、おそらく混乱を招くため、襞と呼ぶべきではありません。