Justin du Coeur (jducoeur) wrote,
Justin du Coeur
jducoeur

Typeclasses

[For programmers only]

Yesterday was another of those programming epiphanies, in which I finally not only understand what a functional-programming concept means, but (more importantly) grok *why* it works the way it does. As I did with Monads a few months ago, let's take a stab at explaining the concept, while it's still fresh in my brain. Today's concept is "Typeclasses", another Haskellism that has made its way into Scala. (The functional programmers with more experience than I are encouraged to correct any misconceptions below.)

That said, my first try at writing this started getting horribly long. So let's see if I can keep this to a sane length:

The name seems a bit weird to those of us from an OO background, but it's literally correct: a Type is (or more accurately, can have) an "instance" of a Typeclass in much the same way that an Object is an instance of a Class. That is, a Typeclass describes a somewhat abstract bit of functionality, and you can define an instance that maps from a Type to that functionality.

Why is it useful? The usual reason: once you've got the idea of this Typeclass, you can then write higher-order functions that use it, and thereby reduce duplication and boilerplate.

A simple example in pseudo-code: say I have an "Addable" Typeclass:
typeclass Addable[T] {
  def +(a:T, b:T):T
}
That is, an Addable is a Type for which there exists a binary function "+", which adds two values of this Type together, and returns another value of this Type. Using that, I can define sum:
def sum(elems:List[Addable]) = {
  if (elems.length == 0)
    0
  else
    elems.head + sum(elems.tail)
}
At this point, the sharp-eyed OO programmers are saying, "So, it's exactly the same as an interface, right?". Not quite. The thing is, a Typeclass instance is, like I said, a mapping from the Type to the Typeclass -- and that implies that you can have *multiple* such mappings.

The classic illustration seems to be the Monoid Typeclass, which seems to be basically the abstraction of our Addable above. It is a Typeclass that defines an "append" operation, which takes two values, combines them, and produces a new value of the same Typeclass instance. (With the added constraint that the operation must be associative, and you must have an "identity" or "zero" value.) So Monoid looks roughly like this:
typeclass Monoid[T] {
  def append(a:T, b:T):T
  def identity:T
}
The equivalent of our sum() function above is "concat" in Haskell-speak:
def concat(elems:List[Monoid]) = {
  if (elems.length == 0)
    identity
  else
    elems.head append concat(elems.tail)
}
Obviously, we can define an SumMonoid -- the Typeclass instance that represents the concept of "summing" -- by saying that append is (a+b), and identity is 0; that becomes exactly Addable, above. But you can also define a ProductMonoid -- representing the concept of "multiplying" -- by saying that append is (a*b), and identity is 1. There are at least two distinct and *separate* Monoids for Int, because "Monoid" isn't a Type -- it's a Type *plus* some operations.

(The same is true for Boolean and Monoids: the concept of the "conjunction" of a List of Booleans is the Monoid of "and" with the identity of true, and "disjunction" is the Monoid of "or" with the identity of false.)

In other words, Monoid is (roughly) the abstract concept of "an operation that you can perform on a couple of Foos, and get another Foo". That's a Typeclass.

How much does this matter in real-world programming? I'm honestly not certain yet, but I'm slowly starting to appreciate that it helps you separate concerns, even without the multiple-definition thing. It's very un-OO, but thinking of a Typeclass instance as being something separate from the Type itself allows you to add functionality without endlessly complicating your inheritance trees -- it's not *part* of your class, it's a kind of thing that you can do *with* your class. (Or course, carried to its extreme, this logic gets very anti-OO; I suspect it helps explain the visceral functional-vs-OO wars I sometimes see.)

And of course, I wind up asking: is any of this going to get into Querki? I suspect so eventually, although not soon. I am likely to add the concept of Typeclasses internally at first, for some of the numeric operations (eg, I might actually implement sum() in terms of Monoids, as described above, to prove out the concept). Eventually it'll likely become user-visible, although only around the edges for high-end power-user use.

Questions? The above is largely me getting the ideas straight in my head, so discussion is welcome...
Tags: programming
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 10 comments