4 Ways to Make Change in Scala

Posted on September 16, 2020
ScalaProgrammingLiterate

I’ve recently been going through Exercism exercises with a group of Colleagues. The colleagues in question are group of experienced developers, but who generally started with little to no Scala experience.

On the surface, our only goal is to learn some Scala syntax and libraries, by solving some fun problems.

That said, I’m secretly aiming to win them over to joys of my favourite programming style: Purely Functional Programming.

With that in mind, this blog post is about 4 different ways to solve one of the exercises, and what they taught me, not just about Pure FP, but about teaching Pure FP.

The Exercise in question is called “Change”. As described on Exercism, the task in Change is:

Correctly determine the fewest number of coins to be given to a customer such that the sum of the coin’s value would equal the correct amount of change.

In a nutshell, we want to write a function

def findFewestCoins(target: Int, coins: List[Int]): Option[List[Int]]

This should take a target value, and a list of the different coins that we might use, and should return an Option, with a possible list of those coins, that should add up to the value.

Right off the bat, we’ve run into one concept from FP: Our function findFewestCoins is “Partial”, there are some possible sets of coins that can’t be used to make every value. For example findFewestCoins(target=94, coins=List(5, 10)) doesn’t have an answer. Because Partial Functions are dangerous we’re using Scala’s Option type to represent a partial function, as a total function with an Option return type; which may return None` for values outside of it’s domain.

Using Option “correctly” can take a while to get used to, for developers without FP experience. They tend to fall back on the tried and tested technique of writing code that’s liable to throw Null Pointer Exceptions, and then finally wrapping it all in a Try/Catch. I’m a huge fan of Alexis King’s blog post “Parse, Don’t Validate”, as an explanation of the correct way to think about Option, although fair warning, it contains a whole bunch of Haskell.

An Approach That Nearly Gets There

An Algorithm for solving the “Change” problem looks pretty simple, let’s dive straight into some code:

object NearlyWorksChange {
    // explicitly write out some "useful" results
    val noCoins = Some(List.empty[Int])
    val failure = None
    def findFewestCoins(target: Int, coins: List[Int]): Option[List[Int]] = 
        (target, coins) match {
            // the value 0 is made up from 0 coins
            case (0, _) => noCoins 
            // if we have no "coins" we can't solve the problem
            case (_, Nil) => failure  
            // if the target value is negative, we also can't solve the problem
            case (t, _) if t < 0 => failure
            // otherwise, we want to investigate 2 possibilities
            case (_, h::tail) => {
                // Either we do use the first coin
                // so we need to know how to make target - it's value
                lazy val usingFirstCoin = findFewestCoins(target - h, coins).map(h::_)
                // or we don't, so we need to know how to make the target
                // without using it
                lazy val notUsingFirstCoin = findFewestCoins(target, tail)
                // of those two possibilities
                // we're interested in the one that involves the fewest coins
                List(usingFirstCoin, notUsingFirstCoin).flatten.minByOption(_.length)
        }
    }
}

This is a recursive approach, it has three base cases:

  • the value is zero: and the solution is “no coins”
  • there are no “candidate” coins: the problem has no solution
  • the target value is negative: there’s also no solution

If neither of those cases match, then the solution either does, or doesn’t, involve the first coin on the list. So we can use recursion to solve both of those cases, and then choose the one with the shortest solution.

There’s just one problem with this solution, it’s much too slow.

It passes all of the Exercism test cases, except one.

Change.findFewestCoins(999, List(1, 2, 5, 10, 20, 50, 100))

This doesn’t fail, per say, it just takes an inordinate amount of time, far more than is reasonable.

The problem is, the search space is pretty big, and we’re exploring the entirety of it. More specifically, we’re re-calculating each sub problem every time we run into it. While trying to solve the problem for 999, we wind out re-calculating the solution for 500: “11,390,171 times”.

The State Monad

Fortunately, there’s a drop in solution for the entire category of problems where you need to re-calculate an expensive function very frequently: Memoization

Memoization is an optimization technique where we cache the result of our function calls, using the arguments as a key. And then, when the function is called again with the same arguments, we return those cached results rather than re-calculating them.

We can add Memoization to “Pure Functions” without changing the results of our program, (other than the runtime) because they have no side effects. This is great because I’m able to demonstrate yet another advantage of pure FP to my colleagues.

Since we want to add Memoization, while remaining Purely Functional, one approach is to use the State Monad from the Cats library.

The State Monad can be used to model restricted mutable state, in a purely functional style. We can think of a value of Cats’ State[S, A] as being similar to a function S => (A, S). That is, a function that takes some initial state, of type S, and returns an updated state, along with a result of type A.

Thanks to the magic of Cats, we’re able to use for comprehensions to compose individual computations returning State together.

object CatsStateChange {
    import cats.data.State
    import cats.syntax.all._
    // Let's define some type aliases,
    // because otherwise our time definitions are going to be really long
    // We're storing our cached results in a `Map` 
    // where the keys are a tuple of the arguments
    type Memo = Map[(Int, List[Int]), Option[List[Int]]]
    // And that value `Memo` will appear in our `State` Monad
    type MemoState[A] = State[Memo, A]
    // We need some Initial State to run the Monad. 
    // At the start of the calculation, we haven't memoized anything yet
    // So we can just use an empty Map
    val nothingMemoizedYet = Map.empty[(Int, List[Int]), Option[List[Int]]]
    // Our two base cases, are `None` or `Some(List.empty) in a `MemoState` Context
    val failure = (None :Option[List[Int]]).pure[MemoState]
    val noCoins = Option(List.empty[Int]).pure[MemoState]
    // The function we're trying to memoize has the type `(Int, List[Int]) => Result`
    // This takes a function with those types, and memoizes it via the State Monad
    // I find that writing this in a "generic" way, with type parameters 
    // makes it slightly easier to think about
    def memoize[A, R](f: A => State[Map[A, R], R])(a: A): State[Map[A, R], R] = for {
        previous <- State.get[Map[A, R]]
        result <- previous.get(a) match {
            case Some(memoizedResult) => State.pure[Map[A, R], R](memoizedResult)
            case None => f(a)
        }
        _ <- State.modify[Map[A, R]](_.updated(a, result))
    } yield result
    // This is _more or less_ the same solution we used previously
    val findFewestCoinsMemo: ((Int, List[Int])) => MemoState[Option[List[Int]]] =
        memoize[(Int, List[Int]), Option[List[Int]]]({
            case (0, _) => noCoins
            case (_, Nil) => failure
            case (t, _) if t < 0 => failure
            case (target, h::tail) => for {
                usingFirstCoin <- findFewestCoinsMemo(target - h, h::tail)
                notUsingFirstCoin <- findFewestCoinsMemo(target, tail)
            } yield List(
                usingFirstCoin.map(h::_),
                notUsingFirstCoin
            ).flatten.minByOption(_.length)
        })(_)
    // Finally "run" our memoized function, using an initial empty state
    def findFewestCoins(target: Int, candidates: List[Int]): Option[List[Int]] = 
        findFewestCoinsMemo(target, candidates).run(nothingMemoizedYet).value._2
}

With memoization added via the State monad, we pass all of the Exercism test cases.

If I was solving these by myself, I’d probably stop here.

But the point of these exercises is as a learning exercise, and we’ve already introduced two concepts; Option and Memoization. Trying to explain both of these, and the State Monad, and for-comprehensions in one session is probably too much to introduce in one go. Let’s try and see if we can pair it back a little.

Philosophical Purity

A mixed blessing associated with programming in Scala, is that the compiler doesn’t enforce purity.

If we want to add side effects or introduce local state, we’re free to do so.

Earlier, we mentioned an advantage of programming with pure functions:

We can safely add Memoization without otherwise changing the behaviour of our program.

Let’s treat this as an excuse to go wild, and add some limited local impurity.

We’re happy to do this, with the proviso that it doesn’t affect our ability to reason about our code as if it were pure.

// Memo2 is a case class that takes a function with two arguments of type A and B
// it contains a mutable map
// Memo2 can be used as a function
// when it is, it looks up the value in the map
// and calculates it if it's missing
// This is in many respects similar to our `memoize` function, from the `State` code. 
case class Memo2[A,B,R](f: Function2[A, B, R]) extends Function2[A, B, R] {
  import scala.collection.mutable
  private val cache = mutable.Map.empty[(A, B), R]
  def apply(x: A, y: B) = cache.getOrElseUpdate((x, y), f(x, y))
}
object Memo2Change {
    val noCoins = Some(List.empty[Int])
    val failure = None
    // find fewest coins is a "simple" depth first search
    // but it's memoized using Memo2
    val findFewestCoins: Function2[Int, List[Int], Option[List[Int]]] = 
        Memo2[Int, List[Int], Option[List[Int]]]{ 
            case (0, _) => noCoins 
            case (_, Nil) => failure  
            case (t, _) if t < 0 => failure
            case (target, coins@h::tail) => {
                lazy val usingFirstCoin = findFewestCoins(target - h, coins).map(h::_)
                lazy val notUsingFirstCoin = findFewestCoins(target, tail)
                List(usingFirstCoin, notUsingFirstCoin).flatten.minByOption(_.length)
        }
    }
}

This was the example that I showed to my colleagues. I think it’s the most understandable solution that I’m going to come up with.

There are some caveats around this, for instance, access to the map used in Memo2 isn’t thread safe.

Recursion Schemes

I’m a big believer in occasionally going in the opposite direction, and writing “deliberately fancy code”.

There are a handful of reasons for this, first and foremost, it’s loads of fun.

But even from a pragmatic perspective, there’s a specific category of really weird bugs that you hardly ever see in the course of normal development, but that somehow, beginners are really good at running into. I find that deliberately challenging yourself to use obscure techniques is the fastest way to encounter, and hence understand, those bugs.

For example, while writing this recent blog post that I ran into a bug in the Scala Compiler and learnt about the workaround. This is far more relaxing than being stuck, frantically Googling, in the middle of a pair programming session.

With that said, this is probably a good place to stop reading. Recursion schemes are a large and complex topic, and I’m about to butcher the task of explaining them. This isn’t entirely my fault, the type of Recursion Scheme required to solve “Change”, a histomorphism, is one of the more obscure ones. And unlike other posts about Recursion Schemes, I’m not going to build up to it.

If you want to learn more about Recursion Schemes, I can recommend any of these articles, although the standard Haskell warning applies to the last one.

Recursion Scheme code operates over “Fixed Point Types”. If you’ve ever tried and failed to construct a recursive Option[_] that was options all the way down

Option[Option[Option[Option[Option[Option[Option[Option[Option[Option[Option[Option[...

Fixed point types let you get close to that, by adding a layer of indirection:

case class Fix[F[_]](unfix: F[Fix[F]])

I’m going to refer to the type argument F in that definition, as the Functor. Because using a fix point type in a recursion scheme relies on F having a Functor instance; it needs to be something that you can map over. This let’s you construct values which are very similar to the impossible recursive Option, such as:

Fix[Option](Some(Fix[Option](Some(Fix[Option](None)))))

The fix point of Option is equivalent to a “Natural Number” (an integer that’s either positive or zero). We can see equivalence, by thinking of None as representing zero, and Some(Fix(x)) as representing x + 1.

Recursion scheme code let’s us write “Morphisms” which take Algebras and Co-Algebras written in terms of the Functor F, and convert them into folds and unfolds over the fixed point version of that functor. We’re going to use a couple of Recursion schemes below.

The first, and simplest of these is natAlgebra, which takes an Algebra[Option, Int] and produces a function that folds up a Fix[Option] returning the depth of the Option An Algebra[F[_], A] is literally just a function F[A] => A so we can think of our natAlgebra as a function Option[Int] => Int. The recursion scheme doing the folding is called a “catamorphism”.

The important thing to bear in mind about the natAlgebra function, is that it doesn’t involve any recursion. The recursive part of applying an Algebra to a Fixed Point type is abstracted away by the Recursion Scheme.

(We’re using an implementation of recursion schemes from a library called Droste.)

object RecursionSchemeChange {
    import higherkindness.droste._
    import higherkindness.droste.data._
    import higherkindness.droste.data.prelude._
    import cats.implicits._
    def natAlgebra: Algebra[Option, Int] = Algebra[Option, Int]{
        case Some(n) => n+1
        case None => 0
    }
    def toInt[A](x: Attr[Option, A]): Int = scheme.cata(natAlgebra).apply(x.forget)

We’re also doing the exact opposite, and using natCoalgebra to convert a (positive) Int to a Fixed Point Option. In the same way that the algebra is essentially just a function Option[Int] => Int, this is the opposite; a function Int => Option[Int] A recursion scheme that takes a co-algebra is called an anamorphism.

    val natCoalgebra: Coalgebra[Option, Int] =
        Coalgebra(n => if (n > 0) Some(n - 1) else None)

Next comes the core of the recursion scheme solution.

We’re going to phrase the change problem as CVAlgebra.

This is like similar to the Algebra used in natAlgebra. Except that instead of operating on an Option[Int], we’re operating on an Option[Attr[Option, A]].

A is our result type, Option[List[Int]].

Attr is another Fixed Point type, loosely defined as:

case class Attr[F[_], A](attribute: A, hole: F[Attr[F, A]])

The purpose of the hole variable, is that once we lift this CVAlgebra using a recursion scheme called a “histomorphism”, the hole will contain the results of “smaller” values in the recursion. We can use this like the cache in any of the previous examples.

    // Lookup a value from the recursion scheme "history"
    // "i" is the number of "layers" to go back
    // so if you're currently computing a value for 10 `lookup(4, attr)`
    // will be the value computed for 6
    def lookup[A](i: Int, v: Option[Attr[Option, A]]): Option[A] = (i, v) match {
        case (0, Some(Attr(a, _))) => Some(a)
        case (n, Some(Attr(_, tail))) => lookup(n - 1, tail)
        case (_, None) => None
    }

Unlike the previous implementation of findFewestCoins, our implementation as a CVAlgebra closes over the list of coins. We use the same list of coins at every point in the search tree. And instead of asking “do we use the first coin or not”, at each level, we ask, “which of these coins do we use next”.

Finally we combine the CVAlgebra with our natCoalgebra, forming a “hylomorphism”. A hylomorphism is a recursion scheme that combines a histomorphism, and an anamorphism. The anamorphism is just responsible for converting from the amount as an Int, to the “Fixed Point of Option” form.

An advantage to chaining recursion schemes together like this is we don’t have to construct the entire Fixed Point object in memory at once. (That might be hearsay, I’ve not peaked at the internals of Droste).

    def findFewestCoins(amount: Int, coins: List[Int]): Option[List[Int]] = {
        val coinAlgebra: CVAlgebra[Option, Option[List[Int]]] = CVAlgebra {
            // this is our base case, corresponding to a value of zero
            case None => Some(List.empty[Int])
            // this is our recursive case, where the value is positive
            case cur@Some(next) => {
                val toProcess = coins.filter(_ <= 1 + toInt(next))
                val processedResults: List[List[Int]] = toProcess.map{ coin => 
                    lookup(coin-1, cur) // lookup the values in the history
                    .flatten // flatten: to combine 2 layers of `Option` 
                    .map(coin :: _) // then add the current coin to the prior result
                }.flatten // and flatten, removing `None`s, coins that can't appear here
                processedResults.minByOption(_.length)
            }
        }
        
        val f = scheme.ghylo(
            coinAlgebra.gather(Gather.histo),
            natCoalgebra.scatter(Scatter.ana))
        // Negative numbers can't be represented as a Nat
        // So filter them out first
        Some(amount).filter(_ >= 0).flatMap(f)
    }
}

As mentioned above, the Recursion Scheme solution introduces a lot of concepts at once.

Hopefully, if you’ve read this far, and you take one thing home from it, it will be the following.

Recursion schemes let you write a non recursive Algebra, and then lift this into a recursive function.

I might not get to use this a lot, but I think that it’s incredibly cool that it’s even possible.

Appendix

This blog post is Literate Scala, view the raw source-code here.

If you’re trying to run it, you may find the build.sbt file containing the specific version of the dependencies to be valuable.

The build.sbt has the following contents:

scalaVersion := "2.13.3"

addCompilerPlugin("com.olegpy" %% "better-monadic-for" % "0.3.1")
libraryDependencies += "org.scalatest" %% "scalatest" % "3.2.0" % "test"
libraryDependencies += "org.typelevel" %% "cats-core" % "2.0.0"
libraryDependencies += "io.higherkindness" %% "droste-core" % "0.8.0"