1
\$\begingroup\$

I've created an RPN evaluator in Haskell, as an exercise because I'm new to this language.

It runs well:

$ ./rpn 
2 3 4 5 + - +
-4

And the source code:

{-# LANGUAGE BangPatterns #-}
import Data.String
import System.IO

data Token = TNum Int | TOp Operator
data Operator = Add | Sub | Mul | Div

main :: IO ()
main = do
    line <- getLine
    let tokens      = tokenise line
        (numc, opc) = countTok tokens
        !junk       =
            if numc == opc + 1
                then ()
                else error "Not a correct expression."
    print $ eval [] tokens


tokenise :: String -> [Token]
tokenise = map str2tok . words

eval :: [Int] -> [Token] -> Int
eval (s:_) []                   = s
eval stack (TNum t:ts)          = eval (t : stack) ts
eval (x:y:stacknoxy) (TOp t:ts) = eval (applyOp t y x : stacknoxy) ts

str2tok :: String -> Token
str2tok tkn@(c:_)
    | c `elem` ['0'..'9'] = TNum (read tkn :: Int)
    | otherwise = TOp $ case tkn of
        "+" -> Add
        "-" -> Sub
        "*" -> Mul
        "/" -> Div
        _   -> error $ "No such operator " ++ tkn

applyOp :: Operator -> Int -> Int -> Int
applyOp Add a b = a + b
applyOp Sub a b = a - b
applyOp Mul a b = a * b
applyOp Div a b = a `div` b

countTok :: [Token] -> (Int, Int)
countTok [] = (0, 0)
countTok (t:ts) =
    let (x, y) = case t of
            TNum _ -> (1, 0)
            _      -> (0, 1)
     in (x, y) `addPair` countTok ts

addPair :: (Num a, Num b) => (a, b) -> (a, b) -> (a, b)
addPair (x, y) (z, w) = (x + z, y + w)

How can this code be improved? I hope my implementation is elegant, and if it isn't - what are the ways to clean it up? In particular, I really don't like the errors because they're just ugly:

./rpn
5 6 + +
rpn: Not a correct expression.
CallStack (from HasCallStack):
  error, called at rpn.hs:16:22 in main:Main

I know they can be replaced with fail, which has a much nicer output, but from what I've read it can only be done inside a function that returns IO ().

\$\endgroup\$
2
\$\begingroup\$

First, I would convert all of the functions which might throw an error to return some kind of failable type, like Maybe Int or Either String Token. This includes str2tok, tokenize, and eval. This would also remove the need for the countTok function, since the program can just return an error value from eval instead. With the help of the Monad instances for these error types, this is a relatively simple change.

Next, I would use isDigit from Data.Char instead of c `elem` ['0'..'9'] because isDigit makes less comparisons in order to determine if it's a digit.

Lastly, I would change the Operator type to the function type Int -> Int -> Int. This will remove the need for applyOp and will consolidate all the places that would be necessary to change if you wanted to extend the program to accept more operators.

import Data.Char (isDigit)

data Token = TNum Int | TOp (Int -> Int -> Int)

main :: IO ()
main = do
    line <- getLine
    either putStrLn print $ do
        tokens <- tokenize line
        eval [] tokens

tokenize :: String -> Either String [Token]
tokenize = mapM str2tok . words

str2tok :: String -> Either String Token
str2tok tkn
    | (c:_) <- tkn, isDigit c = Right $ TNum (read tkn)
    | otherwise = TOp <$> case tkn of
        "+" -> Right (+)
        "-" -> Right (-)
        "*" -> Right (*)
        "/" -> Right div
        _   -> Left $ "No such operator " ++ tkn

eval :: [Int] -> [Token] -> Either String Int
eval (s:_) []                   = Right s
eval stack (TNum t:ts)          = eval (t : stack) ts
eval (x:y:stacknoxy) (TOp t:ts) = eval (t y x : stacknoxy) ts
eval _ _                        = Left "Not a correct expression."
\$\endgroup\$
  • \$\begingroup\$ Brilliant! But I have one more question, what does the <$> do? I suspect it has to do something to do with Monads, which I don't grasp, unfortunately. \$\endgroup\$ – atmostmediocre Jan 3 at 14:13
  • 1
    \$\begingroup\$ <$> is the infix operator alias for fmap. If it's easier for you to read, you could use fmap TOp $ instead of TOp <$> \$\endgroup\$ – 4castle Jan 3 at 14:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.