問題タブ [recursion-schemes]

para以下は、 fromを使用するための練習として私が書いたコードですrecursion-schemes(この縮小された例はcata、 だけを使用して解決できることはわかっていますが、この質問ではこれを無視しましょう)。

これを行っているときに、コンストラクターparaへの引数のいずれかの式ツリーにアクセスしたい場合は、使用時に非網羅的なパターン マッチを行う必要があることに気付きました。Depth

この問題がなく、 を必要とせず、 のインスタンスだけを必要とするgcata'andの代替実装を見つけました。なぜこのバージョンが の実装に使用されなかったのか? 何か問題がありますか、それとも私が探しているものを達成するためのより良い方法がありますか?para'ComonadFunctorwrecursion-schemes

そして、これを使用する方法の例を次に示します。

ご覧のとおり、どちらの関数も同じことを行い、ツリーの最大深度を計算します (最も外側のdepth呼び出し自体はカウントしません) 。

Churchエンコーディングのリストにパッケージcataから使えるようにしたいです。recursion-schemes

便宜上二等式を使いましたが、気にしません。newtype必要に応じてを追加したり、GADT を使用したりしてください。

Church エンコーディングの考え方は広く知られており、単純です。

基本的に「未指定の抽象」consでありnil、「通常の」コンストラクターの代わりに使用されます。私はすべてがこの方法でエンコードできると信じています（Maybe、ツリーなど）。

List1が実際に通常のリストと同型であることを示すのは簡単です:

したがって、その基本ファンクターはリストのファンクターと同じであり、それを実装projectしてからの機構を使用できるはずrecursion-schemesです。

でもできなかったので、「どうしたらいいの？」というのが私の質問です。通常のリストの場合は、パターン マッチのみを実行できます。

関数のパターン マッチができないため、フォールドを使用してリストを分解する必要があります。project通常のリストの折り畳みベースを書くことができます：

ただし、教会でエンコードされたリストには適用できませんでした。

cata次の署名があります。

リストで使用するには、次のものが必要です。

1. を使用してリストの基本ファンクタ型を宣言するにはtype family instance Base (ListC a) = ListF a
2. 実装するinstance Recursive (List a) where project = ...

私は両方のステップで失敗します。

http://blog.sumtypeofway.com/recursion-schemes-part-2/の一部を読んだ (および実装した) 後 でも、関数の型がどのようにcata機能するのか疑問に思っています。cata関数は次のように定義されます。

のようなものがありTerm Exprます。開梱後、Expr (Term Expr). 代数 ( f) は、たとえば として定義されf :: Expr Int -> Intます。以下を簡単に呼び出すことができることはわかっています。

私はまた想像することができます：

しかし、次のことはうまくいかないと思います：

ただし、cata関数でどのように機能するかはまだわかりませExpr (Term Expr)んExpr a。値が機能することは理解していますが、型がわかりません。ツリーの葉で何が起こるのでしょうか? これは確かにmystery...

編集：理解できないことをより明確に述べようとします。

精神的には、次のcataように機能するようです。

• fmap f葉に適用します。
• これで、持っているノードをExpr Int呼び出して、上に行くことができます。fmap f

私が申請しているので、明らかにこのようには機能しませんfmap (cata f)。ただし、最終的に関数は引数として (リーフで)f呼び出されます。Expr IntこのタイプExpr (Term Expr)は以前のものからどのように作られたのですか？

私はそれを理解することになりました。私が行った講演のビデオとスライドをご覧ください。

• スライド/pdf

• ビデオ

元の質問:

一般的な再帰スキーム (つまり、 の使用Fix) を理解するための努力の中で、さまざまなスキームのリストのみのバージョンを作成すると便利であることがわかりました。実際のスキームを理解するのがはるかに簡単になります (追加のオーバーヘッドなしでFix)。

zygoただし、 と のリストのみのバージョンを定義する方法はまだわかりませんfutu。

これまでの私の専門的な定義は次のとおりです。

histoリストに対してzygoとをどのように定義futuしますか?

私はこの単純なExprAST を持っており、簡単に に変換できますString。

ここで、追加のデータを追加したいと思います。だから私は使用しようとしていますCofree

に変換できExprますExpr2

Expr2しかし、私はに変換する方法を理解できませんString

また、Cofree はこの注釈の問題を解決する最良の方法ですか?

私はこのASTを持っています

そして比較したい

しかし、すべての再帰スキーム関数は単一の構造でのみ機能するようです

明らかに再帰を使用できます

しかし、ある種のzipfold機能を使用できることを願っています。