問題タブ [recursion-schemes]

Foldable.toListアナモフィズムを使用して空でないバラの木を書きたいのですが、最後の要素を抽出することは不可能のようです:

それは本当に不可能であり、空でないすべての構造に一般化されますか?

また (オプションのボーナス質問のようなものです) Fix f -> Fix gg-coalgebras ではなく f-algebras を使用していつ実装できるかを決定する一般的なルールはありますか?

ところで、アポモルフィズムは機能しました：

apo coalg6と同じ型ana5ですが、1 つの要素を失いません

算術式を表すデータ型があります。

式を変数の積の合計に変換する展開関数を書きたいと思います (中かっこ展開のようなものです)。もちろん、再帰スキームを使用します。

「進歩と維持」の精神に則ったアルゴリズムしか思いつきませんでした。各ステップのアルゴリズムは、完全に展開された用語を構築するため、再チェックする必要はありません。

の処理にMul頭がおかしくなったので、直接行う代わりに の同形型を使用し、それを利用し[[String]]てconcatすでにconcatMap実装されていました。

だから私はちょうど使用しますcata：

そして元に戻す：

大幅に優れたアプローチはありますか?

更新：混乱はほとんどありません。

1. このソリューションでは、複数行の変数名を使用できます。Add (Val "foo" (Mul (Val "foo) (Var "bar")))の表現ですfoo + foo * bar。私は何かを代表x*y*zしているわけではありませんVal "xyz"。スカラーがないため、「foo * foo * quux」などの繰り返し変数も完全に許可されていることに注意してください。

2. 積の合計とは、一種の「カリー化された」積の n-ary 和を意味します。積和の簡潔な定義は、括弧のない式が必要であり、すべての括弧が結合性と優先順位によって表されるということです。

したがって(foo * bar + bar) + (foo * bar + bar)、中間+は合計の合計であるため、積の合計ではありません。

(foo * bar + (bar + (foo * bar + bar)))または対応する左結合バージョンは正しい答えですが、結合性が常に左または常に右であることを保証する必要があります。したがって、右結合ソリューションの正しいタイプは次のとおりです。

これは、空でないリストに同型です: (の代わりにNonEmpty Poly注意してください)。空の合計または積を許可すると、使用したリスト表現のリストだけが得られます。Sum Mono PolySum Poly Poly

3. また、パフォーマンスを気にしないでください。乗算は単なるようですliftA2 (++)