This answer is a synthesis of the partial answers provided by both 0__ and Nicolas Rinaudo.
Summary:
There are many convenient (but also highly intertwined) assumptions being made by the Scala compiler.
- Scala treats
extends (A => B)
as synonymous withextends Function1[A, B]
(ScalaDoc for Function1[+T1, -R]) - A concrete implementation of Function1's inherited abstract method
apply(x: A): B
must be provided;def apply(x: A): B = cache.getOrElseUpdate(x, f(x))
- Scala assumes an implied
match
for the code block starting with= Memo {
- Scala passes the content between
{}
started in item 3 as a parameter to the Memo case class constructor - Scala assumes an implied type between
{}
started in item 3 asPartialFunction[Int, BigInt]
and the compiler uses the "match" code block as the override for the PartialFunction method'sapply()
and then provides an additional override for the PartialFunction's methodisDefinedAt()
.
Details:
The first code block defining the case class Memo can be written more verbosely as such:
case class Memo[A,B](f: A => B) extends Function1[A, B] { //replaced (A => B) with what it's translated to mean by the Scala compiler
private val cache = mutable.Map.empty[A, B]
def apply(x: A): B = cache.getOrElseUpdate(x, f(x)) //concrete implementation of unimplemented method defined in parent class, Function1
}
The second code block defining the val fibanocci can be written more verbosely as such:
lazy val fibonacci: Memo[Int, BigInt] = {
Memo.apply(
new PartialFunction[Int, BigInt] {
override def apply(x: Int): BigInt = {
x match {
case 0 => 0
case 1 => 1
case n => fibonacci(n-1) + fibonacci(n-2)
}
}
override def isDefinedAt(x: Int): Boolean = true
}
)
}
Had to add lazy
to the second code block's val in order to deal with a self-referential problem in the line case n => fibonacci(n-1) + fibonacci(n-2)
.
And finally, an example usage of fibonacci is:
val x:BigInt = fibonacci(20) //returns 6765 (almost instantly)