Learn You a Haskell for Great Good! - Miran Lipovaca [92]
If the item is none of the operators, we assume it’s a string that represents a number. If it’s a number, we just apply read to that string to get a number from it and return the previous stack but with that number pushed to the top.
For the list of items ["2","3","+"], our function will start folding from the left. The initial stack will be []. It will call the folding function with [] as the stack (accumulator) and "2" as the item. Because that item is not an operator, it will be read and then added to the beginning of []. So the new stack is now [2]. The folding function will be called with [2] as the stack and "3" as the item, producing a new stack of [3,2]. Then it’s called for the third time with [3,2] as the stack and "+" as the item. This causes these two numbers to be popped off the stack, added together, and pushed back. The final stack is [5], which is the number that we return.
Let’s play around with our function:
ghci> solveRPN "10 4 3 + 2 * -"
-4.0
ghci> solveRPN "2 3.5 +"
5.5
ghci> solveRPN "90 34 12 33 55 66 + * - +"
-3947.0
ghci> solveRPN "90 34 12 33 55 66 + * - + -"
4037.0
ghci> solveRPN "90 3.8 -"
86.2
Cool, it works!
Adding More Operators
One nice thing about this solution is that it can be easily modified to support various other operators. They don’t even need to be binary operators. For instance, we can make an operator "log" that just pops one number off the stack and pushes back its logarithm. We can also make operators that operate on several numbers, like "sum", which pops off all the numbers and pushes back their sum.
Let’s modify our function to accept a few more operators.
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 (x:y:ys) "/" = (y / x):ys
foldingFunction (x:y:ys) "^" = (y ** x):ys
foldingFunction (x:xs) "ln" = log x:xs
foldingFunction xs "sum" = [sum xs]
foldingFunction xs numberString = read numberString:xs
The / is division, of course, and ** is exponentiation. With the logarithm operator, we just pattern match against a single element and the rest of the stack, because we need only one element to perform its natural logarithm. With the sum operator, we return a stack that has only one element, which is the sum of the stack so far.
ghci> solveRPN "2.7 ln"
0.9932517730102834
ghci> solveRPN "10 10 10 10 sum 4 /"
10.0
ghci> solveRPN "10 10 10 10 10 sum 4 /"
12.5
ghci> solveRPN "10 2 ^"
100.0
I think that making a function that can calculate arbitrary floating-point RPN expressions and has the option to be easily extended in 10 lines is pretty awesome.
Note
This RPN calculation solution is not really fault tolerant. When given input that doesn’t make sense, it might result in a runtime error. But don’t worry, you’ll learn how to make this function more robust in Chapter 14.
Heathrow to London
Suppose that we’re on a business trip. Our plane has just landed in England, and we rent a car. We have a meeting really soon, and we need to get from Heathrow Airport to London as fast as we can (but safely!).
There are two main roads going from Heathrow to London, and a number of regional roads cross them. It takes a fixed amount of time to travel from one crossroad to another. It’s up to us to find the optimal path to take so that we get to our meeting in London on time. We start on the left side and can either cross to the other main road or go forward.
As you can see in the picture, the quickest path from Heathrow to London in this case is to start on main road B, cross over, go forward on A, cross over again, and then go forward twice on B. If we take this path, it takes us 75 minutes. Had we chosen any other path, it would take longer.
Our job is to make a program that takes input