再帰型レンダリング

Question

私はのいずれかのの再帰的文法データ型とそのデータ型の表現をとることができ、同じ種類のすべての部分式のリストを生成するようなコードを作成しようとしていますその型の再帰でscanのようにします。

付属の玩具電卓の文法タイプEExpについては、以下の2つの手動の例を書いています。最初の例では、Lensライブラリのプリズムとレンズを使用していますが、eg1の式の1つでは動作しますが、2番目の関数はハンドリングされたコードを使用しますが、EExpの式では動作します。

理想的には、テンプレートのhaskellなどを使用して、そのタイプ（プリズム/レンズのような）の式の各サブ式に焦点を当てる再帰関数を自動的に構築することができます。それに与えられたあらゆる表現のすべての部分のリストを出してください。

私はちょっと試してみてください。どんな助けも本当にありがとう！

import qualified Control.Lens as Lens 
import qualified Control.Lens.TH as LTH 


-- Syntax for toy language 

data EExp a 
    = ELit a 
    | EAdd (EExp a) (EExp a) 
    | EMul (EExp a) (EExp a) 
    | ESub (EExp a) (EExp a) 
    deriving Show 

-- build out a set of focus functions using lens/TH 

LTH.makePrisms ''EExp 


-- An example "text" in the Syntax 

eg1 :: EExp Int 
eg1 = EAdd 
     (ELit 1) 
     (EAdd (ELit 2) (ELit 0)) 

-- using lenses, we build out all the 
-- EExp possibilities from the example "text": 

lensedOptions :: Show a => EExp a -> [EExp a] 
lensedOptions exp = 
    let 
    maybeGet l = Lens.preview l exp 
    listMaybes = 
     [ Just exp 
     , maybeGet (_EAdd.(Lens._1)) 
     , maybeGet (_EAdd.(Lens._2)) 
     , maybeGet (_EAdd.(Lens._2)._EAdd.(Lens._1)) 
     , maybeGet (_EAdd.(Lens._2)._EAdd.(Lens._2)) 
     ] 
    in 
    maybe [] id $ sequenceA listMaybes 

printEm :: IO() 
printEm = sequence_ $ map print $ lensedOptions eg1 

-- using handwritten code, we build out all the 
-- EExp possibilities from the example "text": 


buildOptions :: Show a => EExp a -> [EExp a] 
buildOptions exp = 
    let 
    buildBinOpts e1 e2 = [exp] ++ buildOptions e1 ++ buildOptions e2 
    in 
    case exp of 
     ELit i -> [exp] 
     EAdd e1 e2 -> 
     buildBinOpts e1 e2 
     EMul e1 e2 -> 
     buildBinOpts e1 e2 
     ESub e1 e2 -> 
     buildBinOpts e1 e2 

printEm2 :: IO() 
printEm2 = sequence_ $ map print $ buildOptions eg1 

Answer 1

あなたはControl.Lens.Platedモジュールを探しています。その後

{-# language DeriveDataTypeable #-} 
import Data.Data 
import Data.Data.Lens 
import Control.Lens -- for universeOf function 

data EExp a 
    = ELit a 
    | EAdd (EExp a) (EExp a) 
    deriving (Show, Data) 

：

まずData派生を追加

> buildOptions eg1 
[EAdd (ELit 1) (EAdd (ELit 2) (ELit 0)),ELit 1,EAdd (ELit 2) (ELit 0),ELit 2,ELit 0] 

> universeOf uniplate eg1 
[EAdd (ELit 1) (EAdd (ELit 2) (ELit 0)),ELit 1,EAdd (ELit 2) (ELit 0),ELit 2,ELit 0] 

をuniplateレンズは、ここで魔法の大部分を行っています。 Data typeclassによって提供される情報を使用して、自己相似性の子供を見つけるために任意のData-フレンドリーなデータ構造に歩み進めることができます。また、トラバーサルを効率的にするためにsome high-altitude caching gymnasticsを実行していますが、無視しても問題ありません。

universeOf uniplateは、すべての推移的子孫を見つけるために繰り返しuniplateを呼び出します。

Data.Dataの詳細については、LämmelとSPJのScrap Your Boilerplate paperをご覧ください。