GADTを使用して文字列を構文木に構文解析する方法

Question

GADTの紹介hereを読んでいました。プログラマーに構文木の種類を偉大にするように制限するというアイデアがありました。このアイデアを簡単なラムダ計算インタープリタに入れました。後で私はこの構文木に文字列をパースすることができないことに気づきました。なぜなら、1つの解析関数は、入力に応じてさまざまな種類の構文木を返す必要があるからです。

{-# LANGUAGE GADTs #-} 
data Ident 
data Lambda 
data Application 

data Expr a where 
    Ident :: String -> Expr Ident 
    Lambda :: Expr Ident -> Expr a -> Expr Lambda 
    Application :: Expr a -> Expr a -> Expr Application 

GADTsを使用する前に、私はこれを使用していた：ここでは例です

data Expr = Lambda Expr Expr 
      | Ident String 
      | Application Expr Expr 

GADTsは、ここで今私がLambda (Application ..) ..のように無効な構文木を作成することはできませんbacuse大きな利点があります。

しかし、GADTでは、文字列を解析して解析ツリーを作成できませんでした。ここではラムダのためのパーサー、のIdent、およびアプリケーションの表現です：

ident :: Parser (Expr Ident) 
ident = ... 

lambda :: Parser (Expr Lambda) 
lambda = ... 

application :: Parser (Expr Application) 
application = ... 

今の問題は、次のとおりです。

expr = choice [ident, application, lambda] 

各パーサは、異なるタイプを返しているので、これは明らかに、動作しません。

したがって、GADTを使用して文字列を解析し、構文ツリーを作成する方法はありますか？

Answer 1

GADTを使用して、Expr aが不明なaを含むタイプにすることができます。あなたが状況ではないで

data AnyExpr where AnyExpr :: Expr a -> AnyExpr 

AnyExprを使用し、特定のタイプにExprを制限したいです。

anyExpr :: Parser (Expr a) -> Parser AnyExpr 
anyExpr p = fmap AnyExpr p 

expr :: Parser AnyExpr 
expr = choice [anyExpr ident, anyExpr application, anyExpr lambda]