Haskell recursive problem, tiny parser. A few things

Question

data Expr =  Var Char | Tall Int | Sum Expr Expr | Mult Expr Expr | Neg Expr | Let Expr Expr Expr
    deriving(Eq, Show)

That is the datatype for Expr, I have a few questions. I'm suppose to parse expressions like *(Expr,Expr) as shown in the datatype definition. However I do have some problems with "creating" a valid Expr. I use pattern matching for recognizing the different things Expr can be. Some more code:

parseExpr :: String -> (Expr, String)
parseExpr ('*':'(':x:',':y:')':s)   = (Mult (parseExpr [x] parseExpr [y]),s)

This is not working, obviously. The return type of parseExpr is to return the rest of the expression that is to be parsed an a portion of the parsed code as an Expr. The right side of this code is the problem. I can't make a valid Expr. The function is suppose to call it self recursively until the problem is solved.

ANOTHER problem is that I don't know how to do the pattern matching against Var and Tall. How can I check that Var is an uppercase character between A-Z and that Tall is 0-9 and return it as a valid Expr?

Generally I can just look at a few parts of the string to understand what part of Expr I'm dealing with.

Input like: parseProg "let X be 9 in *(X , 2)" Would spit out: Let (Var 'X') (Tall 9) (Mult (Var 'X') (Tall 2))

Answer 1

Your parseExpr function returns a pair, so of course you cannot use its result directly to construct an Expr. The way I would write this would be something like

parseExpr ('*':'(':s) = (Mult x y, s'')
    where (x,',':s') = parseExpr s
          (y,')':s'') = parseExpr s'

The basic idea is that, since parseExpr returns the leftover string as the second argument of the pair, you need to save that string in each recursive call you make, and when you've handled all the subexpressions, you need to return whatever is left over. And obviously the error handling here sucks, so you may want to think about that a bit more if this is intended to be a robust parser.

Handling Var and Tall I would do by just extracting the first character as is and have an if to construct an Expr of the appropriate type.

And if you want to write more complex parsers in Haskell, you'll want to look at the Parsec library, which lets you write a parser as pretty much the grammar of the language you're parsing.