Haskell readsPrec rational functions

Question

I got a problem with the implementation of the readsPrec to parse an input for following datastructure:

data Term = Monom Int Int
          | Addition Term Term
          | Subtraction Term Term
          | Multiplication Term Term
          | Division Term Term

I already implemented an instance of show which makes a monom look like:

let k  = Monom 2 3
Main.show k

returns:

(2x^3)

and

let m = Addition k k
Main.show m

returns:

(2x^3)+(2x^3)

Meanwhile I'm sitting like 5 hours around with the task and I really haven't any clue how to deal with it. My first approach looked like this:

instance Read Term where
  readsPrec _ inp = let[(a,b)] = lex inp in
   case a of
   "x" -> readsPrec 0 b
   "^" -> [(Monom 1 (read b::Int), "")]
   c  -> let[(d, "")] = readsPrec 0 b in
     [(Monom (read c::Int) ((\(Monom x y) -> y) d), "")]

At first I felt very happy until I noticed that this code doesn't work for anything else than Monom. Anyone got an better approach?

Answer 1

Yes. This might seem a little overpowered, but using a parser combinator library like Parsec would allow you to write the code neatly. E.g.

import Text.ParserCombinators.Parsec
import Data.Maybe

monom, term :: Parser Term
operations :: [(Char,(Term -> Term -> Term))] -> Parser Term

int :: Parser Int
int = fmap read $ many1 digit

monom = do
         coef <- int
         string "x^"
         power <- int
         return $ Monom coef power


operations ops = do
                   a <- term
                   c <- choice . map (char . fst) $ ops
                   b <- term
                   return $ (fromJust $ lookup c ops) a b

term = do
        char '('
        x <- monom <|> (operations [('+', Addition), ('-', Subtraction), ('*', Multiplication), ('/', Division)])
        char ')'
        return x

term' = do 
         x <- term
         eof 
         return x

readTerm :: String -> Term
readTerm string = case parse term' "" string  of
                        Left err -> error . show $ err
                        Right term -> term

As an explanation, monom parses something like 2x^3 (without brackets), operations takes a list of tuples and parses a term followed by one of the operation characters, followed by another term, and then uses the appropriate data constructor to make the right instance (the fromJust $ lookup c ops line).

The term parser parses either a monom or one of the operations, surrounded by brackets. term' parses a whole string (i.e. makes sure that the parser runs to the end of the string). readTerm is just a "cleaner" version of the parser.

Some examples:

> readTerm "(2x^3)"
Monom 2 3
> readTerm "((2x^3)+(2x^3))"
Addition (Monom 2 3) (Monom 2 3)
> readTerm "(((2x^3)+(2x^3))*(2x^3))"
Multiplication (Addition (Monom 2 3) (Monom 2 3)) (Monom 2 3)

---

The above is a very basic version, and can easily be extended to (for example) make the coef term optional, so that x^2 parses as Monom 1 2, or make the power term optional so that 2x parses as Monom 2 1. (The option function is extremely useful for this specific modification, and only adds 1 or 2 more lines.)

(Note. this might be more efficient and elegant written in an applicative style, e.g.

import Control.Applicative

monom = Monom <$> int <* string "x^" <*> int

but this can get a bit unweildy when making modifications.)