問題タブ [fixpoint-combinators]

xmonadパッケージに次のコードが表示されます。

このfix関数はData.Functionから来ているようです

しかし、ここでそれがどのように使用されているのか理解できません。また、誰かがこの修正機能をいつ使用するのでしょうか?

ファンクターの不動点の抽象的な概念を理解したいと思いますが、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つの回答すべてが気に入っています。ご協力ありがとうございました。

fix末尾再帰アルゴリズムとして表現する方法がわかりません。それともすでに末尾再帰ですか？多分考え過ぎですよね…

私はたくさん試しましたが、まだリモートで役立つものは何も思いつきません。末尾再帰アルゴリズムは、スタック セーフ ループに簡単に変換できます。それが実際の目標です。

recursion-schemesパッケージでは、次のタイプが定義されています。

それらは同形ですか？もしそうなら、どうやってそれを証明しますか？