/*
*---
*title: 4 Ways to Make Change in Scala
*social_image_url: http://www.doscienceto.it/blog/images/social/change.png
*description: In which I solve a problem from Exercism.io in 4 different ways
*---
* ![](/images/scala-trojan-horse.jpg "A Trojan Horse meme, my co-workers are being 'tricked' into accepting the joys of pure functional programming, by a horse claiming that Scala is just 'a better Java'"){.right}
*
* I've recently been going through [Exercism](exercism.io) 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](exercism.io), 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"](https://lexi-lambda.github.io/blog/2019/11/05/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
*
* ![](/images/memory-from-cats.jpg "Memory: from the musical, Cats"){.right}
*
* 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](https://en.wikipedia.org/wiki/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](https://typelevel.org/cats/datatypes/state.html) from the [Cats library](https://typelevel.org/cats/).
*
* 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
*
* ![](/images/socrates.jpg "Socrates: from Bill and Ted"){.right}
*
* 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
*
* ![](/images/inception.jpg "A Spinning Top: from the movie, Inception"){.right}
*
* 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](2020-05-26-boring.html) that I ran into [a bug in the Scala Compiler](https://github.com/scala/bug/issues/1570) and [learnt about the workaround](https://stackoverflow.com/questions/62003214/implicit-error-when-trying-to-implement-the-absurd-typeclass/62007378).
* 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](https://www.47deg.com/blog/basic-recursion-schemes-in-scala/) [of](https://kubuszok.com/2019/ast-playground-recursion-schemes-and-recursive-data/) [these](https://blog.sumtypeofway.com/posts/introduction-to-recursion-schemes.html) 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](https://github.com/higherkindness/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](/posts/2020-09-16-change.scala).
*
* 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:
*
* ```scala
* 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"
* ```
*/