問題タブ [catamorphism]

Bart de Smetがかなり前に書いた記事を読んでいました。-再帰.aspx

Aggregate 演算子に関して LINQ で他のすべてのカタモルフィック演算子を定義することは、読者への演習として残されています。 -シンプル: (
Long )
Count 、Sum、Average、Min、Max思考: First (OrDefault)、Last (OrDefault)、Single (OrDefault)

Single() 拡張メソッドを除いて、ほぼすべてに Aggregate catamorphism を使用することができました。また、Contains() や First() のようないくつかのケースでは、適切に書き直されていないため、Aggregate catamorphism を停止する方法がよくわかりません (いくつかの条件に一致するアイテムが見つかったときはいつでも)。指定されたシーケンス全体の残りを反復する代わりに。

要約すると:
- Aggregate を使用して Single() 拡張メソッドを書き直すには?
- 指定されたシーケンスの残りの反復を続行せずにアイテムが見つかったときにアイテムを返すために、LINQ Aggregate カタモルフィズムを停止する方法 (たとえば、AggregateContains() は、値に一致する最初のアイテムに対して true を返し、反復を停止する必要があります)。

最近、カタモルフィズムをやっと理解できた気がする。私は最近の回答でそれらについていくつか書きましたが、簡単に言うと、その型の値を再帰的にトラバースするプロセスを抽象化した型のカタモルフィズムであり、その型のパターン一致は、型が持つコンストラクターごとに 1 つの関数に具体化されます。 . この点または上記のリンクの私の回答の長いバージョンの修正を歓迎しますが、これは多かれ少なかれダウンしていると思います。それはこの質問の主題ではなく、いくつかの背景です。

カタモルフィズムに渡す関数が型のコンストラクターに正確に対応し、それらの関数の引数が同様にそれらのコンストラクターのフィールドの型に対応していることに気付くと、すべてが突然非常に機械的に感じられ、どこにあるのかわかりません代替実装のための小刻みの余地。

たとえば、私はこのばかげたタイプをでっち上げましたが、その構造が「意味する」ことについての実際の概念はなく、カタモルフィズムを導き出しました。この型の汎用的な折り畳みを定義できる方法は他にありません。

私の質問は、すべての型に一意のカタモルフィズムがありますか (引数の並べ替えまで)? それとも、反例がありますか: カタモルフィズムを定義できないタイプ、または 2 つの異なるが同等に合理的なカタモルフィズムが存在するタイプ? 反例がない場合 (つまり、型のカタモルフィズムが一意であり、自明に派生可能である場合)、GHC に、この厄介な作業を自動的に行うある種の型クラスを派生させることは可能ですか?

この F 代数 (前の質問で紹介) があり、それに効果的な代数を適用したいと考えています。必死の試行錯誤の末、機能するモナドカタモルフィズムをまとめることができました。アプリケーションに一般化できるのではないかと思います。そうでない場合は、なぜですか。

これは私が定義した方法ですTraversable：

これは単項カタモルフィズムです:

そして、これがどのように機能するかです：

私の考えは、次のように書き直すことができるということです。

残念ながら、ここではapplicative do-notation に関する論文にvalue依存してsubtreeおり、そのような場合、Applicative に desugar することはできません。これを回避する方法はないようです。ネストの深さから浮かび上がるモナドが必要です。

本当ですか？アプリケーション効果のみで折り畳めるのはフラットな構造のみであると結論付けてよいでしょうか?

ファンクターの不動点の抽象的な概念を理解したいと思いますが、Haskell での正確な実装とカタモルフィズムを理解するのにまだ苦労しています。

たとえば、「Category Theory for Programers」の書籍 -- 359 ページに従って、次の代数を定義するとします。

カタモルフィズムの定義により、次の関数を ListF の固定小数点 (リスト) に適用して、その長さを計算できます。

2 つの混乱があります。まず、Haskell コンパイラは List がListFの不動点であることをどのように認識していますか? 私は概念的にそれを知っていますが、コンパイラはどのように知っていますか、つまり、List とすべて同じである別の List' を定義した場合、コンパイラは List' が ListF の不動点でもあると自動的に推論しないと思いますそれ？（私は驚くだろう）。

第 2 に、cata lenAlg の再帰的な性質により、常にデータ コンストラクターの外側のレイヤーを unFix して、ファンクターの内側のレイヤーを公開しようとします (ちなみに、この私の解釈は正しいですか?)。しかし、すでにリーフにいる場合、どうすればこの関数呼び出しを呼び出すことができるでしょうか?

例として、誰かが以下の関数呼び出しの実行トレースを書いて明確にするのを手伝ってもらえますか?

明らかな何かが欠けている可能性がありますが、この質問が同様の混乱を共有する他の人々にとってまだ意味があることを願っています.

回答のまとめ

@nm は、Haskell コンパイラが Functor A が Functor B の不動点であることを理解するには、明示的である必要があることを指摘して、私の最初の質問に答えました。この場合、

@luqui と @Will Ness は、葉 (この場合は NilF) で fmap (cata lenAlg) を呼び出すと、fmap の定義により NilF が返されることを指摘しました。

私の最初の（より大きな）質問に直接対処したので、@ nmの回答を受け入れますが、3つの回答すべてが気に入っています。ご協力ありがとうございました。

フォルダのアイデンティティは

より一般的に言えば、折り畳みを使用すると、構造を破壊して要約値になるか、同じ出力構造になるように構造を挿入することができます。

[Int] -> [Int] または [Int] -> Int または [Int] -> ?

unfoldr/l と同じようなアイデンティティがあるかどうか疑問に思っています。

入手方法を知っている

Int -> [Int]

展開/アナで。

私はそこから抜け出すためのある種の方法を探しています

Int -> Int

再帰スキームを使用します。

次のコードを SML から Haskell に変換しようとしていますが、少し問題があります。

これが私が試したことです：

エラーError: type constructor List_alg given 0 arguments, wants 2 が表示されますが、何が問題なのか、どのように修正すればよいのかわかりません。どんな助けでも大歓迎です！

私は典型的な二分探索木のデータ型を持っています:

そしてカタモルフィズム

を使用して挿入関数を定義しようとしましたfoldtが、興味深い結果が得られました。

もちろん、従来の挿入メソッドは期待どおりに動作します。

insertの観点から定義する方法はありますfoldtか、またはここで間違ったツリー ( ha ) を吠えていますか?