Reverse Polish Notation Calculator

Question

Working through Learn You a Haskell, I made a Reverse Polish Notation calculator.

Please critique it.

-- LYAH uses `(Num a) => String -> a` as the signature
solveRPN :: String -> Double
solveRPN xs = head $ foldl (\acc x -> foldingFunction acc x) [] $ words xs
foldingFunction :: [Double] -> String -> [Double]
foldingFunction acc elem 
 | isOp elem = calculate (take 2 acc) elem : (drop 2 acc)
 | otherwise = (read elem :: Double) : acc 
calculate :: [Double] -> String -> Double
calculate (y:x:_) op
 | op == "+" = x + y
 | op == "-" = x - y
 | op == "*" = x * y
 | op == "/" = x / y
isOp :: String -> Bool
isOp x = x `elem` ["+", "-", "*", "/"]

Answer 1

Using foldl is the right idea, I think. (\acc x -> foldingFunction acc x) is a useless lambda, which could just be written as foldingFunction. The fact that it's a folding function is evident from the fact that you passed it to foldl; you could name it something more useful, such as manipulateStack.

Consider breaking up solveRPN. For example, it might be useful to inspect the end state of the whole stack rather than just taking the top element. Also, it's possible that the input might already be split into words (from the command line via getArgs, for example).

The beauty and simplicity of RPN comes from the fact that operators can manipulate the stack directly. Instead, you've implemented a calculate function that performs binary operations only. That results in two problems:

• In the case of RPN stack underflow, you'll get a "Non-exhaustive patterns in function calculate" error.
• You can't support unary operators (such as "sqrt"), nor can you support nullary operators (such as a "pi" operator that pushes 3.141592653589793 onto the stack).

import System.Environment
manipulateStack :: [Double] -> String -> [Double]
manipulateStack stack s
 | s == "+" = (next + top) : stack''
 | s == "-" = (next - top) : stack''
 | s == "*" = (next * top) : stack''
 | s == "/" = (next / top) : stack''
 | s == "^" = (next ** top) : stack''
 | s == "sqrt" = (sqrt top) : stack'
 | s == "sin" = (sin top) : stack'
 | s == "cos" = (cos top) : stack'
 | s == "tan" = (tan top) : stack'
 | s == "pi" = pi : stack
 | s == "e" = (exp 1) : stack
 | otherwise = (read s::Double):stack
 where top = head stack
 stack' = tail stack
 next = head stack'
 stack'' = tail stack'
rpn :: ([Double] -> [String] -> [Double])
rpn = foldl manipulateStack
solveRPN :: String -> Double
solveRPN s = head $ rpn [] $ words s
main = do
 args <- getArgs
 putStrLn $ show $ head $ rpn [] args

• Kevin Meredith: Thanks for this detailed, superior implementation. If the user enters no argument, then args will have no values. As a result, putStrLn $ show $ head [] will bomb. Also, if the user just enters 1 2 then that seems to be wrong behavior too - where's the op? Do you think it's worthwhile to handle those cases?
• 200_success: If I run the command with no argument, then it prints Prelude.head: empty list to standard error, and exits with status 1 — reasonably appropriate, considering that it took no effort. As for whether rpn 1 2 should print 2.0, or print [1.0, 2.0], or be an error, that's a judgement call for you to make.
• Kevin Meredith: LYAH also notes: We'll make a fault tolerant version of this with a type declaration of solveRPN :: String -> Maybe Float once we get to know monads (they're not scary, trust me!). We could make one right now, but it would be a bit tedious because it would involve a lot of checking for Nothing on every step