複雑なASTの再帰を考慮する

Question

私は現在、抽象構文木を扱い、規則に従って変換する必要がある（具体的なことは重要ではない）サイドプロジェクトについては作業中です。

AST自体は重要ではありません。つまり、一部の種類に限定されたサブ表現があることを意味します。 （例えばオペレータAは唯一のタイプBである引数ではなく、任意のExprを取る必要があり、私のデータ型の大幅簡素化縮小版は、次のようになります。

data Expr = List [Expr] 
      | Strange Str 
      | Literal Lit 
data Str = A Expr 
      | B Expr 
      | C Lit 
      | D String 
      | E [Expr] 
data Lit = Int Int 
      | String String 

私の目標は、明示的な再帰を考慮し、依存することです私はしなかった場合は

data ExprF a = List [a] 
      | Strange (StrF a) 
      | Literal (LitF a) 
data StrF a = A a 
      | B a 
      | C (LitF a) 
      | D String 
      | E [a] 
data LitF a = Int Int 
      | String String 

：。私のAST上で動作するように非常に強力な汎用的なツールを提供thesetwo優れたブログの記事、で示されるように、代わりに再帰スキームに必要な因数分解を適用すると、我々は、で終わります混乱、type Expr = Fix ExprFは、前に定義したExprと同形でなければなりません。私はよく入力する必要cataためStr :: ExprF aの内側パターンマッチB a :: StrF aに持っているよう

しかし、これらのケースのためcataを書くことは、かなり大変な作業となります。元のAST全体では、これは実行不可能です。

私は​​3210に遭遇しましたが、それは私の問題の解決策だと思われますが、複製された高次タイプのクラスなどのユーザーに不愉快なインターフェースは非常に不必要な定型文です。

だから、私の質問を総括します

1. はGADTとしてASTこれについて移動するための正しい方法を書き換えていますか？
2. 「はい」の場合、このサンプルをどのようにしてうまく動作するバージョンに変換できますか？ 2番目の注記では、GHCでより高い種別のFunctorが現在サポートされていますか？

Answer 1

データ型の再帰を外してしまった場合は、Functorを派生させれば完了です。あなたは、再帰スキームを得るために、派手な機能は必要ありません。 （注意点として、Litデータ型をパラメータ化する理由はありません。）

倍がある：

newtype Fix f = In { out :: f (Fix f) } 

gfold :: (Functor f) => (f a -> a) -> Fix f -> a 
gfold alg = alg . fmap (gfold alg) . out 

は（algパラメータ）代数を指定するには、反対のケース分析を行う必要がありますExprFですが、代わりに、各データコンストラクタごとに1つずつ、十数個以上のパラメータを持つように折り畳みを配置することもできます。それは本当にあなたに多くの入力を省くことはなく、読むのがずっと難しくなります。必要に応じて（これには一般にランク2型が必要な場合があります）、これらのパラメータをすべてレコードにパッケージ化し、レコード更新を使用してさまざまな状況で「デフォルト」の動作を提供する「既成の」レコードを更新できます。このようなアプローチをとる古い用紙Dealing with Large Bananasがあります。私が示唆していることは、上記の​​関数をレコードを取得する関数でラップし、ケース分析を行い、それぞれのケースのレコードの適切なフィールドを呼び出す代数を渡すことだけです。

もちろん、代わりにGHC Genericsまたはthe various "generic/polytypic" programming librariesのようにスクラップYour Boilerplateを使用できます。あなたは基本的に彼らが何をしているか再現しています。