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 // or 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. 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 like`startingList`

,`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.

## 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.