How do I improve this Haskell function to evaluate an RPN expression?

Question

Here's what I came up with:

solveRPNWrapper :: (Read a, Integral a) => String -> a
solveRPNWrapper str = solveRPN [] $ words str

calcFunction :: String -> String -> String -> String
calcFunction "+" x y = show $ read x + read y
calcFunction "-" x y = show $ read x - read y
calcFunction "*" x y = show $ read x * read y
calcFunction "/" x y = show $ read x / read y
calcFunction op x y = error $ "Unknown operator: " ++ op ++ "."

isOperator :: String -> Bool
isOperator "+" = True
isOperator "-" = True
isOperator "*" = True
isOperator "/" = True
isOperator _ = False

solveRPN :: (Read a, Integral a) => [String] -> [String] -> a
solveRPN [] (x:[]) = read x
solveRPN [] (x:y:xs) = solveRPN (x:y:[]) xs
solveRPN stack (x:xs)
         | isOperator x =
           let z = calcFunction x (last (init stack)) (last stack)
           in solveRPN (init (init stack)) (z:xs)
         | otherwise = solveRPN (stack ++ [x]) xs
solveRPN stack [] = error $ "Badly formatted expression: Stack contains " ++ show stack

While it does work ...

*Main>  solveRPNWrapper "10 4 3 + 2 *  -"
-4

... I can see this is anything but idiomatic (surely lots of duplication in the operator bit and the read/show seems redundant), and the constraints might be messed up too.

Answer 1

1. Change the type of the stack to Integral a => [a]. This not only removes the need for read and show everywhere, but also reveals a hidden type error in your original code. You were using fractional division (/) instead of integer division (div).

2. Reverse the stack. Lists are easier to manipulate from the front, so use that as the top of your stack. This also lets us use pattern matching on the stack to pick elements from the top of the stack easily instead of messing around with last and init. This is also more efficient.

3. Use a lookup table for the operators. This cuts down further on the duplication, and we can just store the corresponding Haskell functions (+, div, etc.) directly in the table.

This is what I ended up with after making those changes:

solveRPNWrapper :: (Read a, Integral a) => String -> a
solveRPNWrapper str = solveRPN [] $ words str

solveRPN :: (Read a, Integral a) => [a] -> [String] -> a
solveRPN [result] [] = result
solveRPN (y : x : stack) (token : tokens)
  | Just f <- lookup token operators = solveRPN (f x y : stack) tokens
solveRPN stack (token : tokens) = solveRPN (read token : stack) tokens
solveRPN stack [] = error $ "Badly formatted expression: Stack contains " ++ show (reverse stack)

operators :: Integral a => [(String, a -> a -> a)]
operators = [("+", (+)), ("-", (-)), ("*", (*)), ("/", div)]

You could also use a fold instead of recursion, but that would require adding some more error handling to the wrapper. I'd also consider using just Integer instead of Integral a => a, but that's just a matter of changing the type signatures.

For robustness, it would also probably be a good idea to use a pure form of error handling like Either or Maybe instead of using error, and use reads instead of read to handle malformed input.