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

## 7 comments:

FYI, for those of us who use only eBooks (especially with re-flowable content), the section on parametricity is "Cookies - How things that are too real don't obey mathematics".

Good catch .. I am still an old fashioned dude who loves to read the dead tree version :-). Thanks for clarifying - indeed that's the section I was referring to ..

:). BTW, nice post (as always). Thanks!

That was profound indeed. Thank you very much for the great post which was short, sweet but very profound.

Functional newbie here, so please be kind =)

Your final CookieBox lacks the "eat" behaviour that allowed the child to write a "cheat" version of howManyCookies. If "eat" is added to your final implementation isn't it then easy for the child to write a cheat version of "append"?

Very profound indeed! Another great read thanks very much!

This is a very useful article and desperately useful

Post a Comment