She starts with a real life situation such as:
If Grandma gives you five cookies and Grandpa gives you five cookies, how many cookies will you have ?
Let's model this as box of cookies that you get from your Grandma and Grandpa and you need to count them and find the total. Let's model this in Scala and we may have something like the following ..
case class CookieBox(count: Int)
and we can define a function that gives you a
CookieBox containing the total number of cookies from the 2 boxes that we pass to the function ..def howManyCookies(gm: CookieBox, gp: CookieBox) = {
CookieBox(gm.count + gp.count)
}and we use
howManyCookies to find the count ..scala> val gm = CookieBox(5) gm: CookieBox = CookieBox(5) scala> val gp = CookieBox(5) gp: CookieBox = CookieBox(5) scala> howManyCookies(gm, gp) res5: CookieBox = CookieBox(10)
.. so we have 10 cookies from our Grandma & Grandpa .. Perfect!
The problem is .. the child answers: "None, because I'll eat them all". To model this let's add a function
eat to our CookieBox abstraction ..case class CookieBox(count: Int) {
// let's assume n < count for simplicity
def eat(n: Int): CookieBox = CookieBox(count - n)
}So instead of the correct way to answer the question, the child cheats and implements
howManyCookies as ..def howManyCookies(gm: CookieBox, gp: CookieBox) = {
CookieBox(gm.eat(gm.count).count + gp.eat(gp.count).count)
}and we get the following ..
scala> howManyCookies(gm, gf) res6: CookieBox = CookieBox(0)
Prof. Cheng continues ..
The trouble here is that cookies do not obey the rules of logic, so using math to study them doesn't quite work. .. We could impose an extra rule on the situation by adding "... and you're not allowed to eat the cookies". If you're not allowed to eat them, what's the point of them being cookies ?
This is profound indeed. When we are asked to count some stuff, it really doesn't matter if they are cookies or stones or pastries. The only property we need here is to be able to add together the 2 stuff that we are handed over. The fact that we have implemented
howManyCookies in terms of CookieBox gives the little child the opportunity to cheat by using the eat function. More information is actually hurting us here, being concrete with data types is actually creating more avenues for incorrect implementation.Prof. Cheng is succinct here when she explains ..
We could treat the cookies as just things rather than cookies. We lose some resemblance to reality, but we gain scope and with it efficiency. The point of numbers is that we can reason about "things" without having to change the reasoning depending on what "thing" we are thinking about.
Yes, she is talking about generalization, being polymorphic over what we count. We just need the ability to add 2 "things", be it cookies, monkeys or anchovies. In programming we model this with parametric polymorphism, and use a universal quantification over the set of types for which we implement the behavior.
def howMany[A](gm: A, gp: A) = //..
We have made the implementation parametric and got rid of the concrete data type
CookieBox. But how do we add the capability to sum the 2 objects and get the result ? You got it right - we already have an abstraction that makes this algebra available to a generic data type. Monoids FTW .. and it doesn't get simpler than this ..trait Monoid[T] {
def zero: T
def append(t1: T, t2: T): T
}zero is the identity function and append is a binary associative function over 2 objects of the type. So given a monoid instance for our data type, we can model howMany in a completely generic way irrespective of whether A is a CookieBox or Monkey.def howMany[A : Monoid](gm: A, gp: A): A = gm append gp
Implementing a monoid for
CookieBox is also simple ..object CookieBox {
implicit val CookieBoxMonoid = new Monoid[CookieBox] {
val zero = CookieBox(0)
def append(i: CookieBox, j: CookieBox) = CookieBox(i.count + j.count)
}
}
With the above implementation of howMany, the little child will not be able to cheat. By providing a simpler data type we have made the implementation more robust and reusable across multiple data types.Next time someone wants me to explain parametricity, I will point them to Page 19 of How to Bake π.
