問題タブ [catamorphism]

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

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

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

次の状況で何が起こっているのかを考えていたとき、私はちょうどトニー・モリスの変容に関する優れた演習をポタリングしていました...

このメソッドを次のように呼び出してみましょう。

型推論器が の型を or に決定するかどうか疑問に思ってい_ => trueましA => BooleanたAny => Boolean。Function1入力パラメーターが反変であるため、次の両方が問題なくコンパイルされます。

問題は、型推論器が 1 番と 2 番のどちらを思いつくかということです。

「ブール値がfalseでない場合」または「リストが空でない場合はそれを使用し、そうでない場合は別のものを使用する」というパターンをプログラムしていることに気付くことがあります。

「たぶん」関数がたぶんあるものであるBoolとListの関数を探しています。いずれかがあります？

更新：リストケースの一般化としてブールケースを使用するつもりでした。たとえば、Data.TextをTとして使用する場合：

私はそのようなボイラープレートコードを減らすことを目指しています。

このSOの質問に関連するカタモルフィズムを理解することを楽しみにしています:)

Real World Haskell チュートリアルの最初の部分しか練習していません。だから、多分私は今あまりにも多くを求めるつもりです, もしそうなら, 私が学ぶべき概念を教えてください.

以下に、カタモルフィズムのウィキペディアのコード サンプルを引用します。

以下のfoldTree、ツリーをトラバースする方法、この他のSOの質問と回答と比較して、ツリーのn-aryツリートラバーサルをトラバースすることについてのあなたの意見を知りたいです。(バイナリかどうかは別として、以下のカタモルフィズムはn分木を扱うように書けると思います)

私が理解していることをコメントに入れました。修正していただけると幸いです。いくつかのことを明確にしてください。

この時点で私は多くの困難を抱えています.射の葉はどの葉にも適用されると推測しているようですが,このコードを実際に使用するには,foldTreeに定義されたTreeAlgebra,定義された射の葉を持つTreeAlgebraを供給する必要があります.何かをするために？
しかし、この場合、foldTree コードでは {f = leaf} を期待し、その逆ではありません

あなたからの明確化は大歓迎です。

今のところ、夢はまだ続きます。Haskell の概念を学ぶたびに、私はより魅力的になります。それでも、カタモルフィズムに関する以前の質問に対するこの貴重な@luquiの回答に完全に取り組んでいないので、問題が解決するまで戻ってきます。ウィキペディアのこのサンプル コードについてで、BINARY ツリーのカタモルフィズムを扱っています。

それにもかかわらず、 NON BINARYツリーにカタモルフィズムを実装しようとしましたが、いくつかの問題に直面しています。

-- その最新行は "map g [y]" で ghc を喜ばせません

-- そして、この最新の sumTree は ghc でも間違っています

C++ 演算子の > と + と同じように > と + が表示されます。だから私は、オブジェクトを実装するオブジェクトを与えることなく、ghcが私に怒っていることを理解していません >/+ かどうか。

次に、パターン マッチングのガイドのように見える => (-> ??? とは異なる) と @ の意味について、私は完全に漠然としていることを認めなければなりません。

このコードをどのように修正しますか?

そして最新の質問ですが、C++ で複合パターンがたまたま私にとって最も重要だったので、私もこれをやろうとしています。そして明らかに、Haskell では 1 ～ 2 行でほぼ記述できることがわかります (これは私にとって本当に驚くべきことです)。

しかし、コンポジションのリーフ コンストラクターとコンポジット コンストラクターがある種の同じインターフェイスを持つ可能性があるという事実を、どのように表現しますか? (データは可変ではないため、適切な言葉ではないことは承知していますが、私の懸念/目標を推測して理解していただければ幸いです)

これはコンパイル エラーの合計です。

編集 したがって、これは非バイナリカタモルフィズムの最終バージョンです

以下の有効な回答によると、C++ インターフェイス契約に相当する Haskell を求めていたのは、型クラスの制約のようです。

したがって、デザイン パターン Composite は、Composition a を構築するときに型クラスの制約を適用することによって実現されます。おそらく、新しい特殊なデータを定義する必要があります。しかし、それを行う前に型クラスを学ぶ必要があります:-)

Scalazは、、、などのさまざまなADTにちなんで名付けられたメソッドを提供します。foldこのBooleanメソッドは、基本的に、その特定のADTのすべての可能なケースに対応する関数を取ります。つまり、以下に示すパターンマッチです。Option[_]Validation[_, _]Either[_, _]

と同等です：

いくつかの例：

同時に、Traversable[_]タイプに同じ名前の操作があり、コレクションをトラバースしてその要素に対して特定の操作を実行し、結果値を累積します。例えば、

これらの2つの操作が同じ名前（fold/ catamorphism）で識別されるのはなぜですか？私は2つの間に類似点/関係を見ることはできません。私は何が欠けていますか？

典型的なアカデミックな例は、リストを合計することです。実用性に光を当てる折り畳みの使用の実例はありますか?

http://research.microsoft.com/en-us/um/people/emeijer/Papers/meijer94more.pdfの 3 ページから:

カタモルフィズムが合成下で閉じているというのは一般に真実ではない

カタモルフィズムはどのような条件下でカタモルフィズムに合成されますか? より具体的には（ステートメントを正しく理解していると仮定して）：

それぞれに 2 つの基底関手FandGと フォールドがあるとします: foldF :: (F a -> a) -> (μF -> a)and foldG :: (G a -> a) -> (μG -> a).

ここで、2 つの代数a :: F μG -> μGとがあるとしb :: G X -> Xます。

組成(foldG b) . (foldF a) :: μF -> Xがカタモルフィズムになるのはいつですか?

編集: dblhelix の拡張された回答に基づいて、推測があります。それは、自然な変換outG . a :: F μG -> G μGのコンポーネントである必要があります。これが正しいかどうかはわかりません。(編集 2: colah が指摘するように、これで十分ですが、必須ではありません。)μGη :: F a -> G a

編集 3: Haskell-Cafe の Wren Thornton は次のように付け加えています。適切に関連するカテゴリの自然な変換; したがって、適切に関連するカテゴリが常に存在するかどうか、および「適切に関連する」が何を意味するかを形式化できるかどうかに問題を委ねます。」

一般的な方法でカタモルフィズム/アナモルフィズムを操作するというアイデアは本当に気に入っていますが、パフォーマンスに重大な欠点があるように思えます。

カテゴリカルな方法でツリー構造を操作したいとします。つまり、一般的なカタモルフィズム関数を使用してさまざまな折り畳みを記述します。

これで、次のような関数を書くことができます:

残念ながら、このアプローチには重大な欠点があります。計算中に、 のTreeT Intすべてのレベルで の新しいインスタンスが作成され、fmapによってすぐに消費されgます。古典的な定義と比較して

depth1常に遅くなり、GC に不要な負荷がかかります。解決策の 1 つは、ハイロモーフィズムを使用して、作成ツリーとフォールディング ツリーを組み合わせることです。しかし、多くの場合、それをしたくありません。ツリーをある場所で作成し、後で折り畳むために別の場所に渡したい場合があります。または、異なるカタモルフィズムで数回フォルダーに入れます。

GHC を最適化する方法はありdepth1ますか? インライン化してから内部で融合/伐採するようなものcatam gですか? g . fmap ...

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

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

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

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

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