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

functional-programming, haskell

Solution

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

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.

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.

Problem

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.

Original source