Do Loop Until You Die

Do Loop Until You Die

Matthew Doig’s Weblog

Do Loop Until You Die RSS Feed
 
 
 
 

Type Classes for the .Net Underclass

In the comments of the last post, Cale Gibbard noted that the monad abstraction is pointless unless you can write code that works against the abstraction, instead of a particular instance.

Haskell let’s you write work with the monad abstraction through the use of type classes.  This ad hoc form of polymorphism allows a function parameter to be constrained to the set of types that have been defined for a class of operations.  Don’t worry, the above definition will be much clearer by the time we’re done.

So does F# support type classes?  Well, I guess that depends on your definition of support.

 

The Numeric Type Class

When you write your first F# program you’ll probably write something similar to this.

 

let square x = x * x

let result = square 5

 

You’ll pat yourself on the back and tell your object oriented programming buddies you’ve gone functional, until you write the following line.

 

let result = square 5.0

 

The F# compiler is a harsh taskmaster. So what’s wrong with the following code?  It only works with integers, for the compiler has to choose a default type signature for the multiplication operator.

 

val square : int -> int

 

This default can be traced back to the definition of the operator in prim-types.fsi

 

val inline ( * ) : ^a -> ^b -> ^c 

    when (^a or ^b) :

    (static member ( * ) : ^a * ^b    -> ^c)

     and default ^b : ^c and default ^c : ^a

     and default ^c : ^b and default ^a : ^c

     and default ^a : ^b and default ^a : int

 

Notice the int at the very end of the definition.  This tells the compiler to default to int if no type annotation is provided.  So how do we write a square function that works with ints, floats, and complex numbers?  We write a function that works with the numeric type class instead of a particular numeric class.

 

Interfaces Define the Methods for our Type Class

The following interface defines all of the methods that an instance of our numeric type class must support.  This definition along with the comment can be found in Math namespace.

 

// A type-class for numeric types

type INumeric<’a> =

    abstract Zero: ‘a

    abstract One: ‘a

    abstract Add: ‘a * ‘a -> ‘a

    abstract Subtract: ‘a * ‘a -> ‘a

    abstract Multiply : ‘a * ‘a -> ‘a

    abstract Negate : ‘a -> ‘a

    abstract Sign : ‘a -> int

    abstract Abs : ‘a -> ‘a   

    abstract ToString : ‘a * string * System.IFormatProvider -> string

    abstract Parse : string * System.Globalization.NumberStyles * System.IFormatProvider -> ‘a

 

Instance Declarations Provide a Concrete Implementation of the Type Class

Here is a declaration for 32 bit integers.

 

module Instances =

  let Int32Numerics =

    { new INumeric<int32> with

         member x.Zero = 0

         member x.One = 1

         member x.Add(a,b) = a + b

         member x.Subtract(a,b) = a - b

         member x.Multiply(a,b) = a * b

         member x.Negate(a) = - a

         member x.Sign(a) = Math.Sign(a)

         member x.Abs(a) = a

         member x.ToString((x:int32),fmt,fmtprovider) =

                x.ToString(fmt,fmtprovider)

         member x.Parse(s,numstyle,fmtprovider) =

                System.Int32.Parse(s,numstyle,fmtprovider)

    }

 

An instance is defined for every type that will be a member of the Numeric type class. We can now use our Numeric type class along with our instances of Numeric to write a a square function that works for the class of Numeric types.

 

let square_numeric x =

    let num = GetNumericAssociation<’a>()

    num.Multiply(x,x)

let resulti = square_numeric 5

let resultf = square_numeric 5.0

 

Great! We’ve written a square function that works for all instances of Numeric. Unfortunately, our square_numeric function is rather too good, as it let’s us write a square function that work for types that aren’t even instances of Numeric

 

let results = square_numeric “hello”

 

This is where your definition of “support” will start to vary.

 

A Dictionary of Instances Generated at Compile…Err Runtime

At runtime, F# builds a dictionary of instances for the Numeric type class.  Because the dictionary is built at runtime, the compiler cannot statically check to make sure our string is not an instance of this class.  Instead we get a runtime Invalid Operation Exception.  Yuck! Feels like I’m writing JavaScript.  Here is the code that creates the dictionary.

 

let instances =

    let instances = new System.Collections.Hashtable()

    let optab =

        [ typeof<float>,   (Some(FloatNumerics    :> INumeric<float>) :> obj);

          typeof<int32>,   (Some(Int32Numerics    :> INumeric<int32>) :> obj);]

    List.iter (fun (ty,ops) -> instances.Add((ty :> obj),ops)) optab;

    instances

 

So what would we like to be able to do?  We’d like to add a class constraint to our variable that says the parameter must have an instance defined in our dictionary for its type.  Something like the following.

 

let square_numeric_constrained (x :: Numeric<_>.Instances) =

    let op = Numeric<_>.Instances.Get<’a>()

    op.Multiply(x,x)

 

As opposed to the traditional type annotation ( : ),  which means is a.  The ( :: ) means is a member of.  The compiler would of course need to build these instance dictionaries at compile time and type check for us.

 

 

So What is a Type Class?

 

Hopefully the rather obtuse definition at the start of the post is a bit clearer now.  Let’s break it down.

·         A definition of operations/methods.  F# uses an interface to define this.

·         Instances that define the operations/methods for a particular type. A regular old class can be used for this.

·         A dictionary that can be used to lookup the instance for a particular type.

·         A dictionary of these instances that can be used to constrain a function parameter.

 

Interface + Instances + Dictionary + Compiler Constraint Support = Type Class.

 

F# has 3 out of 4.  Does F# support type classes?  Was VB6 an object oriented language? Are Hershey Kisses chocolate or chocolately candy?

I’ll let you decide.
kick it on DotNetKicks.com

One Response to “Type Classes for the .Net Underclass”

  1. 1
    Diegoeche:

    A lot of tricks i didn’t know… thanks!

    Still, F# doesn’t support type classes in the same way C is not functional programming language because you can pass function pointers.

Leave a Reply