How to parse a string in GADT

Question

I am trying to implement Combinatory Logic in Haskell, and I would like to write a parser for the language. I'm having trouble getting a parser to work through Parsec. The main problem is that I need a way to make sure the objects returned by the parser are well-typed. Does anyone have any creative ideas on how to do this?

{-# Language GeneralizedNewtypeDeriving #-} import qualified Data.Map as Map import qualified Text.ParserCombinators.Parsec as P import Text.Parsec.Token (parens) import Text.ParserCombinators.Parsec ((<|>)) import Control.Applicative ((<$>), (<*>), (*>), (<*)) data CTree = CApp CTree CTree | CNode String deriving (Eq, Read) instance Show CTree where show c@ (CApp xy) = showL c where showL (CApp x' y')= "(" ++ showL x' ++ " " ++ showR y' ++ ")" showL (CNode s) = s showR (CApp x' y') = "(" ++ showL x' ++ " " ++ showR y' ++ ")" showR (CNode s) = s show (CNode s) = s -- | Parser parseC :: String -> Maybe CTree parseC s = extract$ P.parse expr "combinator_string" s where extract (Right r) = Just r extract (Left e) = Nothing expr :: P.CharParser () CTree expr = P.try (CApp <$> (CApp <$> term <*> term) <*> expr) <|> P.try (CApp <$> term <*> term) <|> term term = P.spaces *> (node <|> P.string "(" *> expr <* P.string ")") node :: P.CharParser () CTree node = CNode <$> (P.many1 $ P.noneOf "() ") eval (CApp (CNode "I") x) = x eval (CApp (CApp (CApp (CNode "S") f) g) x) = (CApp (CApp fx) (CApp gx)) eval (CApp (CApp (CApp (CNode "B") f) g) x) = (CApp f (CApp gx)) eval (CApp (CApp (CApp (CNode "C") f) g) x) = (CApp (CApp fx) g) eval x = x 

Answer 1

I am a strong proponent of parsing for a monotyped representation, and then apply the type / design phase to convert it to a typed representation (GADT). The best tutorial on the general idea, probably from the compiler Lennart Augustsson llvm

The representation for SKI calculus may look like

 data TyComb t where TyS :: TyComb ((a -> b -> c) -> (a -> b) -> a -> c) TyK :: TyComb (a -> b -> a) TyI :: TyComb (a -> a) TyApp :: TyComb (a -> b) -> TyComb a -> TyComb b evalTyComb :: TyComb t -> t evalTyComb TyS = \xyz -> (xz) (yz) evalTyComb TyK = const evalTyComb TyI = id evalTyComb (TyApp ab) = (evalTyComb a) (evalTyComb b)