Type Classes Are The Secret Sauce

I came across a recent post on adding Ruby and C# operators to F# that sparked a few thoughts in my head.  The post was good, but yet there were operators that already existed for some of the operations mentioned such as the defaultArg and ( @ ).  But what really got me was thinking about type classes again due to the fact that extension operators aren’t currently supported in the language whereas extension events, properties, methods and statics are.  I covered this in the past in regards to implementing an approximate equality check for my Functional Programming Unit Testing series, but I want to dive further into that subject a little more in this post.

Just What Are Type Classes?

As you may note that I do cover a bit of Haskell on this blog, and I think for very good reason.  It’s a great language for incubating a lot of interesting ideas.  Some of these ideas have been distilled into other languages such as concepts as monads.  Type classes is another great feature of the language that I have come to know and love. 

When we talk about implementing functions, we have two main types of polymorphism, parametric and overloading.  Talking about parametric polymorphism is the typical programming with generics in which a function allows arguments of arbitrary related types of an unlimited nature.  One such example of this is the map function, or the Select method for those in the LINQ land which allows us to specify both the source and destination types which might be just about anything.

Prelude> :t map
map :: (a -> b) -> [ a ] -> [ b ]

On the other hand, we have ad-hoc polymorphism or overloading, which depending on its context, can assume more than one type.  If the allowable types are limited and must be known ahead of time, this makes is ad-hoc.  This polymorphism type is made possible in Haskell through the use of type classes.  For example, if we want to check for equality between two given algebraic types, this type must either derive the Eq type class or we create and instance of our own.  Let’s make this a little more clear by actually looking at one.  Instead of taking a look at the Eq or Equality check, let’s look at the Ord which contains the comparison operators.

Prelude> :i Ord
class (Eq a) => Ord a where
  compare :: a -> a -> Ordering
  (<) :: a -> a -> Bool
  (>=) :: a -> a -> Bool
  (>) :: a -> a -> Bool
  (<=) :: a -> a -> Bool
  max :: a -> a -> a
  min :: a -> a -> a
      -- Defined in GHC.Classes

This type class lays out our basic comparison operators such as greater than, less than, min, max, etc.  But, it also has a restriction which states that any implementation of this type class must also have an associated implementation of the Eq type class which checks for equality.  You can think of this as generic restrictions.  The command we ran above, the info command also not only gave us information about the type class, but also some implementations such as the following:

instance (Ord a) => Ord (Maybe a) -- Defined in Data.Maybe
instance (Ord a, Ord b) => Ord (Either a b)
  -- Defined in Data.Either
instance Ord Integer -- Defined in efined in GHC.Base
instance Ord Char -- Defined in GHC.Base
instance (Ord a) => Ord [a] -- Defined in GHC.Base
instance Ord Int -- Defined in GHC.Base

In order to provide that functionality such as ordering checking, we must create an instance of the Ord class and implement some members.  We needn’t implement all, just the ones we need for our given scenario.  To give you a sense of how this works, let’s take a look at the implementation of Ord for the Bool type. 

instance Ord Bool where
    compare False True  = LT
    compare True  False = GT
    compare _     _     = EQ

Now we have the compare function available to use with the Bool type.  Pretty nice and easy.  Because of this, we can determine whether one is greater than the other such as the following:

Prelude> compare True False
GT

Besides the Eq and the Ord I’ve already mentioned, there are others such as:

• Show – Converting values to strings
• Read – Converting strings to other values (opposite of Show)
• Num – Numeric operations such as addition, subtraction, multiplication, etc
• Enum – Enumeration operations
• Fractional - Division

And the list goes on.  But what I 'like about this, is the opt-in nature of providing a given set of operations and implementing only what you need.  Also, it allows everything to be open so that I can create new instances of a type class for a given type as I see fit, even outside of the module in which it was created.  If you want to go deeper on the subject, Brent Yorgey has a great article called the Typeclassopedia in the Monad Reader Issue 13.

A Poor Man’s Type Class in F#

Ah, but alas we do not have type classes in F#.  It would be great if we did, but I’m sure it might take some changes to the CLR to make this happen such as allowing for higher-kinded polymorphism, which I’ve covered in the past.  As it is, creating generic functions such as the basic math ones can prove to be rather difficult even with the CLR generics.  What it essentially does is checks to see if that given operator exists for your given class among other things.  But, what if you don’t own that class, how could you possibly extend it this way, for example things like adding two Colors?  That’s the power of type classes.

Although not supported natively, we can add that behavior to our classes.  Take for example checking for approximate equality for floating point arithmetic.  As we know, the precise nature of checking for equality of floating points isn’t the same as for integers, and instead must be checked if the difference is less than epsilon.  Let’s define an interface for what that might look like:

open System
open System.Collections.Generic

// Define the type class and it's global associations table
type IApproxEq<'a> = 
    abstract member approxEqual    : 'a -> 'a -> bool
    abstract member approxNotEqual : 'a -> 'a -> bool

What we have here is the beginning of a type class as to define two functions, one for equality and one for inequality.  Next, we need to have some sort of repository for our instances that we declare so that we can dynamically look them up and perform the given operation.  That might look like the following:

[<AbstractClass>]
[<Sealed>]
type ApproxEqualAssociations private() = 
  static let associations = new Dictionary<Type, obj>()
  static member Add<'a>(approxEqual : IApproxEq<'a>) = associations.Add(typeof<'a>, approxEqual)
  static member Get<'a>() = 
    match associations.TryGetValue(typeof<'a>) with 
    | true, assoc -> assoc :?> IApproxEq<'a>
    | false, _    -> failwithf "Type %O does not have an implementation of IApproxEq" <| typeof<'a>

This solution gives us a global singleton in a way of dealing with these operators.  As we shouldn’t be adding to them frequently, and instead reading, it shouldn’t be too much of an issue, but it is an issue nonetheless.  Now that we have this repository of them, let’s declare ones for both single precision floating point and double precision floating points. 

type SingleApproxEqual() =
    let epsilon = 0.001f
    interface IApproxEq<float32> with
        member this.approxEqual x x' = abs(x - x') < epsilon
        member this.approxNotEqual x x' = abs(x - x') >= epsilon  
type DoubleApproxEqual() =
    let epsilon = 0.001
    interface IApproxEq<float> with
        member this.approxEqual x x' = abs(x - x') < epsilon
        member this.approxNotEqual x x' = abs(x - x') >= epsilon      
ApproxEqualAssociations.Add(new SingleApproxEqual())       
ApproxEqualAssociations.Add(new DoubleApproxEqual())

Once we’ve created these two implementations and added them to our associations table, it’s time to put some syntactic sugar on top to make them a real infix operator. 

let (=~) x x' = ApproxEqualAssociations.Get().approxEqual x x'
let (/~) x x' = ApproxEqualAssociations.Get().approxNotEqual x x'

Now we have an extensible operator that can be added to at any given time.  Say if we wanted to say that some colors are considered approximately equal?  It wouldn’t be hard to implement something like that and add it to the associations table.  We can now test our behavior such as the following:

> 4.000001f =~ 4.0f;; // Testing with float32
val it : bool = true
> 5.1 /~ 5.01;; // Testing with float
val it : bool = true

The true power of this approach is that it opens up the function for future implementations that may want to enlist in our behavior.  Take this in contrast to the typical way we create operators in F# which lock us in to one type, although it can be circumvented, but it’s not well known and not well documented.

> let (+*) x y = (x * y) + (x + y);;
val ( +* ) : int -> int -> int

As you can see, we’re locked into the integer implementation which isn’t extensible.  I noted above there are ways around this and if you look through the F# implementation, you will find some pretty interesting code for how they implemented the standard operators.

What Are the Limitations?

So like everything, there are limitations.  For example, there is no such thing as compile time safety, which doesn’t actually bother many people, especially those in the dynamically typed world.  Another issue is of course the maintenance of this global association table per type class can also be a little much as it might grow over time.  It’s not the ideal solution, but it’s a solution.  Do I think that F# should incorporate this?  Absolutely!  I really do like this language feature of type classes in Haskell and there are other lessons other languages can take from it.