• Choose a category
• All
• Classic-Fiction

solveRPN :: String -> Double

Note

It really helps to first think what the type declaration of a function should be before dealing with the implementation. In Haskell, a function’s type declaration tells you a whole lot about the function, due to the very strong type system.

When implementing a solution to a problem in Haskell, it can be helpful to consider how you did it by hand. For our RPN expression calculation, we treated every number or operator that was separated by a space as a single item. So it might help us if we start by breaking a string like "10 4 3 + 2 * -" into a list of items, like this:

["10","4","3","+","2","*","-"].

Next up, what did we do with that list of items in our head? We went over it from left to right and kept a stack as we did that. Does that process remind you of anything? In I Fold You So in I Fold You So, you saw that pretty much any function where you traverse a list element by element, and build up (accumulate) some result—whether it’s a number, a list, a stack, or something else—can be implemented with a fold.

In this case, we’re going to use a left fold, because we go over the list from left to right. The accumulator value will be our stack, so the result from the fold will also be a stack (though as we’ve seen, it will contain only one item).

One more thing to think about is how we will represent the stack. Let’s use a list and keep the top of our stack at the head of the list. Adding to the head (beginning) of a list is much faster than adding to the end of it. So if we have a stack of, say, 10, 4, 3, we’ll represent that as the list [3,4,10].

Now we have enough information to roughly sketch our function. It’s going to take a string like "10 4 3 + 2 * -" and break it down into a list of items by using words. Next, we’ll do a left fold over that list and end up with a stack that has a single item (in this example, [-4]). We take that single item out of the list, and that’s our final result!

Here’s a sketch of that function:

solveRPN :: String -> Double

solveRPN expression = head (foldl foldingFunction [] (words expression))

where foldingFunction stack item = ...

We take the expression and turn it into a list of items. Then we fold over that list of items with the folding function. Notice the [], which represents the starting accumulator. The accumulator is our stack, so [] represents an empty stack, which is what we start with. After getting the final stack with a single item, we apply head to that list to get the item out.

All that’s left now is to implement a folding function that will take a stack, like [4,10], and an item, like "3", and return a new stack [3,4,10]. If the stack is [4,10] and the item is "*", then the function will need to return [40].

Before we write the folding function, let’s turn our function into point-free style, because it has a lot of parentheses that are kind of freaking me out:

solveRPN :: String -> Double

solveRPN = head . foldl foldingFunction [] . words

where foldingFunction stack item = ...

That’s much better.

The folding function will take a stack and an item and return a new stack. We’ll use pattern matching to get the top items of a stack and to pattern match against operators like "*" and "-". Here it is with the folding function implemented:

solveRPN :: String -> Double

solveRPN = head . foldl foldingFunction [] . words

where foldingFunction (x:y:ys) "*" = (y * x):ys

foldingFunction (x:y:ys) "+" = (y + x):ys

foldingFunction (x:y:ys) "-" = (y - x):ys

foldingFunction xs numberString = read numberString:xs

We laid this out as four patterns. The patterns will be tried from top to bottom. First, the folding function will see if the current item is "*". If it is, then it will take a list like [3,4,9,3] and name its first two elements x and y, respectively. So in this case, x would be 3, and y would be 4. ys would be [9,3]. It will return a list that’s just like ys, but with x and y multiplied as its head. With this, we pop the two