Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Parsing function in haskell

I'm new to Haskell and I am trying to parse expressions. I found out about Parsec and I also found some articles but I don't seem to understand what I have to do. My problem is that I want to give an expression like "x^2+2*x+3" and the result to be a function that takes an argument x and returns a value. I am very sorry if this is an easy question but I really need some help. Thanks! The code I inserted is from the article that you can find on this link.

import Control.Monad(liftM)
import Text.ParserCombinators.Parsec 
import Text.ParserCombinators.Parsec.Expr  
import Text.ParserCombinators.Parsec.Token  
import Text.ParserCombinators.Parsec.Language  

data Expr = Num Int       | Var String    | Add Expr Expr
          | Sub Expr Expr | Mul Expr Expr | Div Expr Expr
          | Pow Expr Expr
          deriving Show

expr :: Parser Expr
expr = buildExpressionParser table factor
    <?> "expression"

table = [[op "^" Pow AssocRight],
         [op "*" Mul AssocLeft, op "/" Div AssocLeft],
         [op "+" Add AssocLeft, op "-" Sub AssocLeft]]
    where
        op s f assoc
            = Infix (do{ string s; return f}) assoc
factor = do{ char '('
        ; x <- expr
        ; char ')'
        ; return x}
    <|> number
    <|> variable
    <?> "simple expression"

number :: Parser Expr
number = do{ ds<- many1 digit
        ; return (Num (read ds))}
    <?> "number"

variable :: Parser Expr
variable = do{ ds<- many1 letter
        ; return (Var ds)}
    <?> "variable"
like image 517
izayoi Avatar asked Jan 17 '11 10:01

izayoi


People also ask

What is parsing in Haskell?

Parser combinators are known to be simple to use without requiring external tools or too many concepts to learn. That is, they are ordinary Haskell constructors that can easily be combined and returned with other parsers because of their nature as functions.

Is Haskell good for parsing?

Haskell is an excellent language for all your parsing needs. The functional nature of the language makes it easy to compose different building blocks together without worrying about nasty side effects and unforeseen consequences.

How do parser generators work?

A parser generator takes a grammar as input and automatically generates source code that can parse streams of characters using the grammar. The generated code is a parser, which takes a sequence of characters and tries to match the sequence against the grammar.

Are parser combinators slow?

Parser combinators are generally slower than a hand-written or code-generated parser. That's somewhat innate due to the overhead of “threading” (for lack of a better word) your control flow through many function calls.


1 Answers

This is just a parser for expressions with variables. Actually interpreting the expression is an entirely separate matter.

You should create a function that takes an already parsed expression and values for variables, and returns the result of evaluating the expression. Pseudocode:

evaluate :: Expr -> Map String Int -> Int
evaluate (Num n) _ = n
evaluate (Var x) vars = {- Look up the value of x in vars -}
evaluate (Plus e f) vars = {- Evaluate e and f, and return their sum -}
...

I've deliberately omitted some details; hopefully by exploring the missing parts, you learn more about Haskell.

As a next step, you should probably look at the Reader monad for a convenient way to pass the variable map vars around, and using Maybe or Error to signal errors, e.g. referencing a variable that is not bound in vars, or division by zero.

like image 168
Cactus Avatar answered Nov 16 '22 02:11

Cactus