6
\$\begingroup\$

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` ["+", "-", "*", "/"]
\$\endgroup\$

1 Answer 1

3
\$\begingroup\$

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
\$\endgroup\$
3
  • \$\begingroup\$ 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? \$\endgroup\$ Jul 3, 2014 at 0:21
  • \$\begingroup\$ 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. \$\endgroup\$ Jul 3, 2014 at 1:13
  • \$\begingroup\$ 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 \$\endgroup\$ Jul 3, 2014 at 1:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.