# Reverse Polish Notation evaluator in Haskell

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 ().

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."

• 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. – atmostmediocre Jan 3 at 14:13 • <$> is the infix operator alias for fmap. If it's easier for you to read, you could use fmap TOp $ instead of TOp <$> – 4castle Jan 3 at 14:16