Haskell readsPrec rational functions
-
13-07-2021 - |
Frage
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?
Lösung
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.)