Parsec sitting in Haskell

Question

I have 2 parsers:

nexpr::Parser (Expr Double) sexpr::Parser (Expr String) 

How to create a parser that tries to use one and then another if it doesn't work? I can’t understand what to return. There must be a smart way to do this.

Thanks.

EDIT:

Adding a little extra info ...

I am studying Haskel, so I started with:

 data Expr a where N::Double -> Expr Double S::String -> Expr String Add::Expr Double -> Expr Double -> Expr Double Cat::Expr String -> Expr String -> Expr String 

then I read about F-algebra ( here ), and so I changed it to:

 data ExprF :: (* -> *) -> * -> * where N::Double -> ExprF r Double S::String -> ExprF r String Add::r Double -> r Double -> ExprF r Double Cat::r String -> r String -> ExprF r String 

from

 type Expr = HFix ExprF 

so my parsing is:

 Parser (Expr Double) 

in fact:

 Parser (ExprF HFix Double) 

Maybe I bite off more than I can chew ...

Answer 1

As noted in the comments, you can have such a parser

 nOrSexpr :: Parser (Either (Expr Double) (Expr String)) nOrSexpr = (Left <$> nexpr) <|> (Right <$> sexpr) 

However, I think the reason you are experiencing such a difficulty is because you do not represent your parse tree as one type, which is more common. Something like that:

 data Expr = ExprDouble Double | ExprInt Int | ExprString String 

Thus, you can have parsers for each kind of expression, all of a type Parser Expr . This is the same as using Either , but more flexible and supported. So you may have

 doubleParser :: Parser Expr doubleParser = ... intParser :: Parser Expr intParser = ... stringParser :: Parser Expr stringParser = ... exprParser :: Parser Expr exprParser = intParser <|> doubleParser <|> stringParser 

Note that the parser order matters, and use can use the Parsec try function if backtracking is required.

So, for example, if you want to now have a sum expression, you can add to the data type

 data Expr = ExprDouble Double | ExprInt Int | ExprString String | ExprSum Expr Expr 

and make a parser

 sumParser :: Parser Expr sumParser = do a <- exprParser string " + " b <- exprParser return $ ExprSum ab 

UPDATE

Ok, I take my hat to dive right into GADT if you are just starting out with Haskell. I read the article you linked and immediately noticed this in the first paragraph:

The jury still does not know whether the additional type safety provided by GADT is worth the additional inconvenience of working with them.

I think three points should be taken away here. First, I just wish I could try an easier way to do something to understand how this works, and why you might want to add more type safety before trying to use more complex types of theoretical materials. This comment may not help, so feel free to ignore it!

Secondly, and more importantly, your idea ...

 data ExprF :: (* -> *) -> * -> * where N :: Double -> ExprF r Double S :: String -> ExprF r String Add :: r Double -> r Double -> ExprF r Double Cat :: r String -> r String -> ExprF r String 

... specifically designed to prevent abusive expressions of the type. Unlike a mine, which can, for example, ExprSum (ExprDouble 5.0) (ExprString "test") . So the question you really want to ask is what should happen when the parser tries to parse something like "5.0 + \"test\"" ? Do you want this to simply not be parsed, or do you want it to return a nice message that this expression is the wrong type? For this reason, compilers are usually designed in several stages. The first pass turns the input into an abstract syntax tree (AST), and then passes the annotation of this tree to type judgments. This annotated AST can then be converted to a semantic representation in which you really want it.

So, in your case, I would recommend two steps. first, analyze a mute representation like mine that will give you the correct tree shape, but allow you to use non-typed expressions. how

 data ExprAST = ExprASTDouble Double | ExprASTInt Int | ExprASTString String | ExprASTAdd Expr Expr 

Then enter another function that will check the ExprAST type. Sort of

  typecheck :: ExprAST -> Maybe (ExprF HFix a) 

(You can also use Either and return either the GADT verification code or an error string that indicates what the problem is.) A further problem is that you do not know that a static. Another answer solves this using type tags and an existential wrapper, which you may find as the best way. I feel that it would be easier to have a top-level expression in your GADT so that all expressions should live, so all parsing will always be of the same type. In the end, usually there is only one type of program.

My third and final point is related to this.

The jury still does not know whether the additional type safety provided by GADT is worth the additional inconvenience of working with them.

The more type safety you have, the more work you must do to get it. You mention that you are new to Haskell, but this adventure has led us to the edge of what he is capable of doing. The type of the expression being analyzed cannot depend only on the input string in the Haskell function, since it does not allow the use of dependent types. If you want to go this route, I can suggest you take a look at a language called Idris. An excellent introduction to what he is capable of can be found in this video in which he creates the printf font.

Answer 2

The described problem is to use Parsec for parsing in the GADT representation, for which, probably, the simplest solution will be analyzed as a monotype and then have a verification phase (probably partial) of the type to create a well-typed GADT, if possible. A monotype representation can be an existential wrapper over the term GADT, with a tag type to validate the GADT index.

EDIT: quick example

Define a type for type tags and an existential wrapper:

 data Type :: * -> * where TDouble :: Type Double TString :: Type String data Judgement f = forall ix. Judgement (f ix) (Type ix) 

In the GADT example indicated in the original message, we only have a problem with the external production itself, which we need to parse into a monotype, since we do not statically know what type of expression we will get at runtime:

 pExpr :: Parser (Judgement Expr) pExpr = Judgement <$> pDblExpr <*> pure TDouble <|> Judgement <$> pStrExpr <*> pure TString 

We can write a type check phase to create a GADT or crash, depending on whether the type statement is executed or not:

 typecheck :: Judgement Expr -> Type ix -> Maybe (Expr ix) typecheck (Judgement e TDouble) TDouble = Just e typecheck (Judgement e TString) TString = Just e typecheck _ _ = Nothing