問題タブ [foldable]

Haskell では、Foldable と Traversable が Haskell prelude に登場します。

これらは両方とも、シーケンスに対して操作を行います。

私の質問は、Haskell の Foldable と Traversable に相当するものは、単純に Clojure のシーケンスですか?

仮定:

• Haskellの fmap に相当するものは、Clojureの m-fmapです。

Haskell を学ぶための演習として、独自の foldMap 関数を作成しようとしています。

現在はこんな感じ

ただし、コンパイルすると、次のエラーが発生します

このエラーでコンパイラが何を伝えようとしているのかわかりません。foldMap の何が問題なのか誰か教えてもらえますか?

これは、ラベル付きのノードとエッジを持つ循環有向グラフのタイプです。

グラフにループがある場合を処理するために、「結び目を結び」、有限空間で無限に再帰的なグラフを作成することができます。

グラフをノードのコレクションとして表示することでFoldable、深さ優先トラバーサルを実行するインスタンスを作成できます。*

ただし、単純なツリー形状のグラフであっても、重複する要素が生成されます。

グラフにサイクルがある場合、その効果はさらに劇的です -foldMap永久に再帰します! ループ内のアイテムが繰り返され、一部の要素が返されません!

これでいいですか？のインスタンスはFoldableその要素の一部を複数回返すことができますか、それともクラスの契約に違反していますか? インスタンスは、構造の一部を無限にループできますか? 私はこの問題に関するガイダンスを探していました - 私は問題を解決する一連の「折り畳み式の法律」を望んでいました - しかし、オンラインで質問に関する議論を見つけることができませんでした.

この状況から抜け出すための 1 つの方法は、グラフをトラバースするときに既にアクセスした要素を「記憶」することです。ただし、これによりEqorOrdの署名に制約が追加foldMapされ、型が のメンバーになることができなくなりFoldableます。

_{Functor* ちなみに、 のインスタンスを書くことはできませんNodeGraph。グラフ内のノードが一意にラベル付けされるという不変条件が壊れてしまうからです。(fmap (const "foo")たとえば、 はすべてのノードを「foo」に再ラベル付けしますが、それらはすべて異なるエッジ セットを持ちます!) ただし、(適切な を使用して) すべてのエッジラベルをマップnewtypeする を記述できます。Functor}

私はtype-aligned sequenceで遊んでいます。特に、それらを折りたたむというアイデアをいじっています。折り畳み可能な型整列シーケンスは次のようになります。

最初に を使用して、単純な方法でシーケンスを型整列リストに変換し (つまり、型整列リスト カテゴリを使用)、次にそのリストを折りたたむfoldrTAという点で、実装は非常に簡単です。残念ながら、長いリストは短いリストの前に追加される可能性があるため、これは非常に非効率的です。右と左の折り目をより効率的に定義するために使用したのと同様のトリックを使用する方法を見つけようとしていますが、そのタイプにはめまいがします。トリックを実行するのに十分なほど一般的ではないようであり、他の方向に進むたびに、追跡できるよりも多くの型変数につながります.foldMapTAfoldMapTAData.FoldableEndo

GHC 7.8またはおそらくそれより古いバーニングブリッジの提案（GHC 7.10の一部であるfoldable/traversable提案とも呼ばれる）をエミュレートする簡単な方法はありますか？

真似するのが本当に難しい側面もあります。これには、クラス階層の変更が含まれます。おそらく、その部分はエミュレートできません。

Data.Foldable新しい関数と関数の置換は、友人から簡単にインポートできます。lengthただし、やなどの関数nullは、新しい型シグネチャでは使用できません。次のスニペットは、橋が燃えているふりをするいくつかの側面を実現します。

これをより完全な方法で行うパッケージはありますか?

Functor インスタンスを作成して使用できます

しかし、(t -> a) の代わりに (Tree t -> a) が欲しいので、t だけでなく (ノード t) 全体にアクセスできるとしたらどうでしょうか?

折り方も同じ

これらのような関数の一般化はありますか?