Haskell parse expression

Question

Hi I got a code like this:

data Digit = Zero | One | Two | Three | Four | Five | Six | Seven | Eight | 
             Nine 
             deriving (Eq, Show)

data Number = Single Digit | Many Digit Number deriving (Eq, Show)

data Expr = Lit Number
          | Sub Expr   
          | Sum Expr Expr 
          | Mul Expr Expr
          deriving (Eq, Show)

So the idea with this code is to have a string, like * + 2 3 * 2 + 6 - 2, which will be represented as ((2 + 3) * (2 * (6 - 2))), and then use this to put parts of the string in there types. And of course at the end find the result, in this case 40. The problem is that I don't know much about parsing, so I really don't know how I could parse an expression like this. I have seen some simple parsing where strings are been parsed into types, like person or something. But I think this is a bit more complex. If anyone have any suggestions, I would be really interested.

Are you sure your input isn't supposed to be * + 2 3 * 2 - 6 2? This looks like prefix Polish notation. — Alec
– Alec, Commented Oct 2, 2017 at 22:55
Compare with stackoverflow.com/q/46516500/625403 - I think there must be some class somewhere assigning this as an exercise. In which case, the - is supposed to be unary negate, not binary subtract. — amalloy
– amalloy, Commented Oct 2, 2017 at 23:00
@Alec Sum Expr Expr looks right to me. The constructor at issue was Sub, not Sum. — amalloy
– amalloy, Commented Oct 3, 2017 at 4:49
Also your example will be more clear if instead of (6 - 2) you write (6 + (-2)), which is what the input actually represents. — amalloy
– amalloy, Commented Oct 3, 2017 at 7:27

amalloy · Accepted Answer · 2017-10-02 23:21:12Z

6

While sophisticated parsing libraries exist for Haskell, and would be great for this task, your input format is simple enough that it's not too imposing to parse by hand, with a recursive function consuming the input and returning both a parsed expression and the remainder of the string to continue parsing.

Here's a skeleton of what it would look like:

parse :: String -> (String, Expr)
parse (' ':more) = parse more
parse ('-':more) = let (remainder, e) = parse more
                   in (remainder, Sub e)
parse ('+':more) = undefined -- TODO
parse ('*':more) = undefined -- TODO
parse s@(num:more) | isDigit num = parseNumber s
parse s = error ("unexpected input: " ++ s)

parseNumber :: String -> (String, Expr)
parseNumber s = undefined

edited Oct 2, 2017 at 23:21

answered Oct 2, 2017 at 23:09

amalloy

92.9k8 gold badges148 silver badges214 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

mschmidt Over a year ago

A nice introduction into the concepts of monadic parsing is the Functional Pearls Paper

iIllumination Over a year ago

Thanks dude, very helpful! I have put in my almost done code at the top of the page if u are interested. Maybe u can't give some suggestion to how I can improve the code too :P

Martijn Pieters Over a year ago

@iIllumination: please don't do that; keep the question post for the question only; if you have a solution (even a partial one), use an answer post for that. I've rolled back your edit.

Collectives™ on Stack Overflow

Haskell parse expression

1 Answer 1

3 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Linked

Related