Reverse Polish Notation evaluator in Haskell

Question

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

Answer 1

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

• atmostmediocre: 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.
• castletheperson: <$> is the infix operator alias for fmap. If it's easier for you to read, you could use fmap TOp $ instead of TOp <$>