問題タブ [catamorphism]

n-ary Tree データ構造をフォールドしたいと思います。（折り畳みはLinqのAggregateとも呼ばれます）
私はなんとか実用的な解決策を思いつきました：

getChildren特定のノードの子を取得する方法を定義する func です。リーフ ノードの空の IEnumerable を返す必要があります。
はaggregator、現在のノードとその子の結果を使用してノードを処理する方法を定義します。

解決策は機能しているようですが、いくつかの問題があります。

• アルゴリズムは再帰的であり、深いツリーのスタックを吹き飛ばします。
  スタックオーバーフローを防ぐために関数を書き直すにはどうすればよいですか?

• アルゴリズムは怠惰ですが、一種のものです。
  たとえば、子ノードaggregatorの結果のみを使用する場合、ツリーの一番左のブランチのみがトラバースされます。Enumerable.FirstただしEnumerable.Last、計算には一番右の分岐のみが必要ですが、ツリー全体がトラバースされます。
  アルゴリズムを本当に遅延させるにはどうすればよいですか?

F# ソリューションは歓迎しますが、C# を優先します。

この記事を書いた後、私はお金を口に出すことに決め、私の以前のプロジェクトを使用するように変換し始めました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は修正され、データ型を再帰的に構築する方法を記述するためにファンクターが使用されます。

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

Churchエンコーディングのリストにパッケージcataから使えるようにしたいです。recursion-schemes

便宜上二等式を使いましたが、気にしません。newtype必要に応じてを追加したり、GADT を使用したりしてください。

Church エンコーディングの考え方は広く知られており、単純です。

基本的に「未指定の抽象」consでありnil、「通常の」コンストラクターの代わりに使用されます。私はすべてがこの方法でエンコードできると信じています（Maybe、ツリーなど）。

List1が実際に通常のリストと同型であることを示すのは簡単です:

したがって、その基本ファンクターはリストのファンクターと同じであり、それを実装projectしてからの機構を使用できるはずrecursion-schemesです。

でもできなかったので、「どうしたらいいの？」というのが私の質問です。通常のリストの場合は、パターン マッチのみを実行できます。

関数のパターン マッチができないため、フォールドを使用してリストを分解する必要があります。project通常のリストの折り畳みベースを書くことができます：

ただし、教会でエンコードされたリストには適用できませんでした。

cata次の署名があります。

リストで使用するには、次のものが必要です。

1. を使用してリストの基本ファンクタ型を宣言するにはtype family instance Base (ListC a) = ListF a
2. 実装するinstance Recursive (List a) where project = ...

私は両方のステップで失敗します。

http://blog.sumtypeofway.com/recursion-schemes-part-2/の一部を読んだ (および実装した) 後 でも、関数の型がどのようにcata機能するのか疑問に思っています。cata関数は次のように定義されます。

のようなものがありTerm Exprます。開梱後、Expr (Term Expr). 代数 ( f) は、たとえば として定義されf :: Expr Int -> Intます。以下を簡単に呼び出すことができることはわかっています。

私はまた想像することができます：

しかし、次のことはうまくいかないと思います：

ただし、cata関数でどのように機能するかはまだわかりませExpr (Term Expr)んExpr a。値が機能することは理解していますが、型がわかりません。ツリーの葉で何が起こるのでしょうか? これは確かにmystery...

編集：理解できないことをより明確に述べようとします。

精神的には、次のcataように機能するようです。

• fmap f葉に適用します。
• これで、持っているノードをExpr Int呼び出して、上に行くことができます。fmap f

私が申請しているので、明らかにこのようには機能しませんfmap (cata f)。ただし、最終的に関数は引数として (リーフで)f呼び出されます。Expr IntこのタイプExpr (Term Expr)は以前のものからどのように作られたのですか？