Chapter 10 of the book, Learn You a Haskell for Great Good!, is titled, Functionally Solving Problems. In that chapter, the author describes a “Reverse Polish Notation” (RPN) calculator. If you ever used an old Hewlett-Packard (HP) calculator, you might know what that is. (At least that’s where I first learned about RPN.)
You don’t have to read it all yet, but some of that discussion is shown in this image:
The equation to solve
In short, the author shares this RPN equation:
"10 4 3 + 2 * -"
and then describes (a) how we should generically think about solving this problem, and then (b) how we should specifically solve this problem by writing an RPN Calculator in Haskell.
A Scala RPN Calculator
I’ll skip over that discussion, because you can find it online at that URL. Instead, I’ll jump right in and show one possible solution to this problem with this Scala RPN Calculator code:
package rpncalculator object SolveRPN extends App { // the desired equation val equation = "10 4 3 + 2 * -" // print the solution println(solveRPN(equation)) def solveRPN(eqn: String): Double = { val items = eqn.split(" ") val accumulator = List[Double]() items.foldLeft(accumulator)(foldingFunction).head } def foldingFunction (stack: List[Double], a: String): List[Double] = stack match { case List() => a.toDouble :: stack // Nil, if you prefer case List(_) => a.toDouble :: stack case x::y::ys => a match { case "*" => x * y :: ys case "+" => x + y :: ys case "-" => y - x :: ys case "/" => y / x :: ys case s: String => s.toDouble :: stack } } }
Discussion
As you can see from that code, I define the equation as a String
, like this:
val equation = "10 4 3 + 2 * -"
Then I call the solveRPN
method to get the solution as a Double
value, which I print like this:
println(solveRPN(equation))
I tested my code against most of the equations shared in the Haskell book, including these:
val equation = "10 4 3 + 2 * -" val equation = "2 3.5 +" val equation = "10 2 ^" val equation = "10 10 10 10 sum 4 /"
The last two equations are solved by adding these cases to the code shown above:
case "^" => Math.pow(y, x) :: ys case "sum" => List(x + y + ys.sum)
The solveRPN method
Some people will say the solveRPN
method is a little verbose, but I wrote it as is for clarity. I could have written it like this as well:
def solveRPN(eqn: String): Double = eqn.split(" ").foldLeft(List[Double]())(foldingFunction).head
That code also works, but whether it’s readable is subject to debate (depending on your experience with Scala, functional programming, the foldLeft
method, your brain, and other factors).
The foldingFunction
The foldingFunction
can be written in a variety of different ways; I’ve just shown one possible solution here which seems clean and also seems to follow the approach of the Haskell solution.
My solution first handles the case of an empty List
, and then the case of a List
with one item, and then handles the case of multiple List
elements by looking at the value of a
, where a
may be a number or an operator.
Note that I could have written List()
in the match/case expression as Nil
instead. You can use whichever one seems to be more clear to you.
That’s all I’m going to write about this RPN problem and solution today. The “Learn You a Haskell” author covers this problem in detail, so I encourage you to read his discussion and solution.
Bonus: A little more about the Scala foldLeft method
If you haven’t used Scala’s foldLeft
method before, I’ve updated this article to provide a discussion of how it works, in the context of this example. (If you already understand foldLeft
, feel free to skip this part.)
The foldLeft
method, found on Scala sequences, is a fun little method. Its signature looks like this:
def foldLeft[B](z: B)(f:(B, A) => B): B
What that signature means is that foldLeft
is a method that takes two parameter lists, this one:
(z: B)
and this one:
(f:(B, A) => B)
The signature also infers that foldLeft
works with two generic types, A
and B
, which I’ll discuss more in a few moments.
As the Scaladoc states, foldLeft
“Applies a binary operator to a start value and all elements of this list, going left to right.”
The first parameter list
Looking back at my solution above, my first parameter list was named accumulator
, and had this type:
List[Double]()
So for my solution, the generic parameter B
is the type List[Double]
.
One note here: I don't think of this being an accumulator as much as I think of it as (a) setting the desired type, and (b) giving
foldLeft
a starting value. I've just seen "accumulator" as a common name in Haskell books, so I used that name here. It could be called something likestartingList
,emptyList
, or anything else that makes sense to you.
The second parameter list
Again looking back at my solution, my second parameter list contains the method named foldingFunction
. If you look at its signature, you’ll see that it matches the signature required by foldLeft
’s second parameter list. Specifically, foldLeft
’s second signature must look like this:
(f:(B, A) => B)
and my foldingFunction
’s signature is this:
def foldingFunction (stack: List[Double], a: String): List[Double]
So again you see that the generic parameter B
is the type List[Double]
, and now we see the generic parameter A
is of type String
. As a quick summary of this parameter list, this method takes two parameters, one of type B
, the second of type A
, and returns a result of type B
.
More on the generic parameters A and B
When you think about this, you know that the generic type A
must be a String
, because that’s the type of our original list. Going back to my code, my original list was named items
, and it had a type of List[String]
:
val items = eqn.split(" ")
So the generic type A
is easy to reason about; it’s the type contained by your list.
The generic type B
is whatever you need for your solution. For this problem I needed for B
to have the type List[Double]
to implement the algorithm described in the Learn You a Haskell book.
this post is sponsored by my books: | |||
#1 New Release |
FP Best Seller |
Learn Scala 3 |
Learn FP Fast |
Summary
In summary, if you were interested in seeing how to solve that RPN calculator problem with foldleft
in Scala, or just wanted to see a foldleft
example, I hope this article has been helpful.