A poor man's typeclass

This post contains a surprisingly short library which allows you to emulate Haskell's typeclasses in F#, except the type-safety. You might think that takes a lot away from the concept, but there is still plenty usefulness left. Not in the least it allows you to use an almost one-to-one translation of Haskell code including typeclasses to F#. At runtime both behave identically. In addition, since this is a library, its functionality can be extended beyond Haskell's typeclasses. Finally, if nothing else, you might be interested in how typeclasses work: this post shows you an implementation.

What is a typeclass, really?

If you don't know what typeclasses are, I recommend reading this chapter in the excellent Real World Haskell book. Let's look at a simple example of a typeclass from that chapter:

class BasicEq a where
    isEqual :: a -> a -> Bool

This defines a typeclass BasicEq. All instances (which are defined later) will need to provide a function isEqual, which compares two values of the instance a. An example of such an instance is:

instance BasicEq Bool where
    isEqual True  True  = True
    isEqual False False = True
    isEqual _     _     = False

This example provides an instance of BasicEq for the type Bool. A lot of people coming from an OO background compare this with an abstract class BasicEq with a subclass Bool, when in fact it is nothing like that. There is absolutely no subtyping of any kind going on. The only relevant type here is Bool; after the instance definition Haskell just knows what isEqual function to call when applied to type Bool. There is absolutely no abstract class. Even more, although Bool is an already defined type, we are adding it as an instance of BasicEq after the fact, something which is not possible in any mainstream statically typed OO language with subtyping.

Typeclasses are a form of so called ad-hoc polymorphism. It has much more in common with operator overloading as it is known in F#, than with subclassing. In fact, the type of isEqual is:

isEqual :: (BasicEq a) => a -> a -> Bool

This indicates that isEqual can be called on any instance a of the typeclass BasicEq. In fact, Haskell only knows the specific function to call when it knows the type a: then, it just looks up the functions associated with that type. So, in fact, the (BasicEq a) => in front of the arguments can (besides as a type annotation) be seen as a dictionary that maps types a to functions implementing the BasicEq typeclass functions for a. The great thing about this is that because of type inference, the actual type a is inferred without any programmer annotation. So Haskell can choose the correct function to call automatically.

So, in the end, what is a typeclass? It's just a dictionary from type to a record of functions, where on each application of a typeclass function Haskell passes along the dictionary to it's calling function implicitly (i.e. without requiring the caller to pass it in). Because of type inference, this sometimes looks like pulling a function or value out of thin air.

The idea

If a typeclass at runtime is nothing more than using type information to pass in an implicit parameter to a function, then in F# we can use respectively reflection and side effects to emulate much the same thing:

• Using reflection, we can obtain the type arguments with which a function is called
• Using side effects, we can build a globally accessible dictionary of types to functions, that can be accessed "transparently", without needing the caller to thread it in calls.

The rest is some syntactic sugar.

Let's first look at how we can use the library, before diving into it's internals. Usage is remarkably similar to that of typeclasses. First, we define the typeclass:

type IListOf<'a> =
    abstract ListOf : list<'a>

This looks like a traditional class or interface type definition, that represents the functions in the typeclass. This type should have exactly one type parameter, which represents the type that we'll be defining instances for.

Now, let's register this new typeclass with our library:

newTypeClass<IListOf<_>>

newTypeClass takes one generic parameter, of which only the generic type definition part is important; this registers IListOf<'a> as a typeclass with which instances for certain types 'a can be registered.

Now, let's make some instances:

type IListOfInstances() =
    static member Unit() = 
        { new IListOf<unit> with
            override x.ListOf = [()]}
    static member Bool() = 
        { new IListOf<bool> with
            override x.ListOf = [true;false] }
    static member Int() = 
        { new IListOf<int> with
            override x.ListOf = [1..20] }

That defined instances for our typeclass IListOf with three instances for types unit, bool and int. As you can see, the corresponding interface implementations should be returned as the result of static members.

These instances must now be registered with the typeclass:

registerInstances<IListOf<_>,IListOfInstances>()

A function that we need to give two type arguments: the typeclass we're registering instances for, and the the type with the static members which return the instances.

Now we can get a specific IListOf implementation for a specific type:

getInstance (typedefof<IListOf<_>>,typeof<unit>)

However, this returns an obj - not nice. We'd like a typed listOf function that can be used whenever we want a list of some typeclass instance. Let's define such a function:

let listOf<'a> = getInstance (typedefof<IListOf<_>>,typeof<'a>) |> unbox<IListOf<'a>> |> (fun l -> l.ListOf)

The function takes only a type argument - which is used to get the instance, unbox the result (if the implementation of the typeclass library is correct, the unbox should always succeed), and then call the ListOf property which should return the correct list. This function can now be used just like an overloaded function:

printfn "%A" (listOf |> List.map (fun x -> x+5))
printfn "%A" (listOf |> List.map (fun x -> if x then "pos" else "neg"))

What is going on? The first listOf returns a list of ints, while the second returns a list of bools, although it seems we're not passing it any argument or hint as to what list to produce. Magic? Of course not.

We are passing listOf information - in its type argument. The reason we don't have to explicitly mention this argument is because F# infers it for us. So this is a great way to let type inference do some work at runtime.

The implementation

The library maintains an internal dictionary of typeclass names to instances of that typeclass:

let private typeClasses = new Dictionary<_,_>()

Defining a new typeclass prepares the one value of that dictionary to hold another dictionary which will map the actual instance types to their implementation of the typeclass functions:

let newTypeClass<'typeClass> = typeClasses.Add((typeof<'typeClass>).GetGenericTypeDefinition(), new Dictionary<_,_>())

The following method then uses some reflection to find all the instances of a given typeclass, which should be defined as static members on a given class type:

let private findInstances (typeClass:Type) = 
    let addMethods l (t:Type) =
        t.GetMethods((BindingFlags.Static ||| BindingFlags.Public)) |>
        Seq.fold (fun l m ->
            match m.ReturnType with
                | GenericTypeDef typeClass args -> 
                    if (args.Length <> 1) then
                        failwithf "Typeclasses must have exactly one generic parameter. Typeclass %A has %i" typeClass args.Length
                    else
                        let instance = args.[0]
                        if instance.IsGenericType 
                            && (instance.GetGenericArguments() |> Array.for_all (fun t -> t.IsGenericParameter)) then
                            (args.[0].GetGenericTypeDefinition(), m) :: l   
                        else
                            (args.[0], m) :: l
                | _ -> l
            ) l
    addMethods []

///Register instances in a given class as instances of the given type class. 
let registerInstancesByType typeClass instance =
    findInstances typeClass instance |> Seq.iter (typeClasses.[typeClass].Add)

///Register instances in a given class as instances of the given type class.
let registerInstances<'typeClass,'instance>() = 
    registerInstancesByType (typedefof<'typeClass>) (typeof<'instance>)

The final ingredient is the lookup function, to get the implementation of a typeclass given a type:

let getInstance   =
    memoize (fun (typeClass:Type, instance:Type) ->
        let instances = typeClasses.[typeClass]
        let mi =
            match instances.TryGetValue(instance) with
            | (true, res) -> res
            | _ when instance.IsGenericType -> //exact type is not known, try the generic type
                match instances.TryGetValue(instance.GetGenericTypeDefinition()) with
                | (true, mi') -> if mi'.ContainsGenericParameters then (mi'.MakeGenericMethod(instance.GetGenericArguments())) else mi'
                | _ -> failwithf "No instances of class %A for type %A" typeClass instance 
            | _ -> failwithf "No instances of class %A for type %A" typeClass instance 
        mi.Invoke(null, Array.empty))

There is some heavy reflection going on here, which I'll let you figure out in your own time. The memoize function I took from the Expert F# book. Full implementation is downloadable below.

Conclusions

This posts shows how to get all the advantages of typeclasses in F#, except the static checking. I've found these advantages considerable:

• The use of reflection is heavy, but it is very nicely encapsulated: all the un-typesafeness goes on strictly inside the library and definition. What goes in and what comes out is strongly typed, and from a user point of view, the reflection is completely behind the scenes.
• Although reflection is involved, it is actually fast: there is some manipulation of  Types, but this is highly optimized in .NET. There is one reflective invocation per instance that is looked up, but the result is memoized so this can be considered startup cost. Finally, there are two constant time dictionary lookups.
• To give a real world example, in FsCheck 0.4 (which will be out real soon) I have been able to use this simple library to translate the Arbitrary and Testable typeclasses from QuickCheck directly into F#, making property combinators more powerful. For one, there is no longer a need for the 'prop' and 'propl' functions, a feat which I was not able to accomplish using reflection alone (and I did try!). So the typeclass abstraction is a nice way to structure your code around overloading.
• It has also allowed me to reduce the amount of reflection code in FsCheck and other projects - which is a Good Thing as reflection is always a pain to use.
• It's a great way to let type inference work for you, also at run time.

Finally, some things for the future:

• This library is not thread safe, although it could be made thread safe at the cost of some locking.
• Are multi-parameter type classes possible using this technique?
• ...

Anyway, I hope that this post has shown that with some imagination and a little work, you can do great things with F#, not in the least thanks to a lot of infrastructure in the form of .NET libraries, without which this would not have been possible.

Download the full implementation. It will also be distributed with FsCheck 0.4 (soon, I promise :).

Technorati: F#,typeclass,haskell

How to change the accessibility of a constructor using implicit object construction

The recommended way to define a class in F# is by using so-called implicit object construction.  The more traditional (for C# programmers, that is) but typically more tedious explicit object construction syntax feels distinctly less "functional". In short, implicit construction relieves you of writing an explicit constructor for your class, and also allows you to use let and do clauses in the body of your class that take the place of static or instance initializers. Check out Robert Pickering's F# wiki for a nice overview.

The other day I was writing a class that needs only factory methods to construct it, a not so uncommon pattern. In C#, I wouldn't think twice about how to do this: just add a private or internal constructor, and a few public factory methods. This is also straightforward to do using F#'s explicit object construction syntax, but I wondered if it is possible using implicit construction. Turns out it is!

The trick is simple:

type Foo internal()=

static member FactoryMethod = new Foo()

Notice the position of the 'internal' modifier. Modifying the accessibility of the 'Foo' class proper is done in the usual way, by putting the modifier right after the 'type' keyword. You can even mix these up:

type internal Foo private()=

This defines an internal class with a private constructor.

Thanks to Brian and Tomas for helping me out on this one!

Technorati: F#,implicit object construction,syntax,accessibility modifier

Announcing FsCheck 0.3

I am very pleased to announce a new release of FsCheck, for the first time on codeplex! Here is a short description.

FsCheck is a port of Haskell's QuickCheck: it is a tool for testing F# programs automatically. The programmer provides a specification of the program, in the form of properties which functions, methods or objects should satisfy, and FsCheck then tests that the properties hold in a large number of randomly generated cases. While writing the properties, you are actually writing a testable specification of your program. Specifications are expressed in F#, using combinators defined in the FsCheck library. FsCheck provides combinators to define properties, observe the distribution of test data, and define test data generators.

This release brings FsCheck about up to par with QuickCheck 0.1, and adds some smaller features. An overview:

• Added feature to derive a generator from the type of arguments. You can add your own generators for custom types. Radically reduces the use of forAll.
• Added feature to reduce use of prop and propl. For example: "quickCheck (fun a -> a+a = 2*a)" just works.
• Added feature to group related properties in a class, and check it at once. Can also be used to check all toplevel properties in a module.
• FsChecks no longer dies when a property throws an exception, but reports a test failure.
• Bug fixes and suggestions received through this blog, email and hubfs implemented. Thanks Neil, Chance, Mat and Anton, and everyone who emailed me!
• Some extension points to use FsCheck with whateverUnit frameworks.
• Updated examples, and documentation, the whole codeplex thing.

It was a lot of work, but I hope it was worth it.

I plan to devote more of my time to other projects from now on, at least for the next coming months. That said, your contributions to FsCheck are more than welcome. Besides, this release should keep you quiet for a while ;).

I will be posting some suggestions for features and improvements soon, should you run out of ideas.

[Update: check out the FsCheck issue tracker for some ideas on how to contribute]

Technorati: F#,FsCheck,random testing

Future plans for FsCheck

Because of a recent question on HubFS, I made my future plans for FsCheck public. I'm re-iterating them here:

• smaller bug fixes, some cleaning (mostly done)
• adding FsCheck.fsi module declaration & comments
• Feature: derive generators from types of arguments (mostly done)
• Feature: ability to group properties in classes, and check the class with one command (mostly done)
• Investigate using FsCheck with unit testing frameworks like MbUnit & co, or generally how to use it in practice (currently active)
• putting the project on codeplex + clarifying license . I'm checking compatibility with the QuickCheck license, but I'm aiming for a permissive license, like the new BSD license.

I intend to finalize this before the end of the year.

Finally, you can help by answering the following question. How are you using FsCheck? Do you have a separate console app that you run that contains your properties, or do you use F# interactive with the properties inline, or something else?

Technorati: F#,random testing,FsCheck

How to use named arguments in F#

Named arguments are a little-known feature of F#, that is actually very useful when calling heavily overloaded members. The DateTime constructor is one such example: it has twelve overloads, and I can never remember what (in C#) DateTime d = new DateTime(2008,11,12) means. Is it December 11th or 11 November (as we would say it in Dutch)? Fortunately, in F# there is a nice solution for this: you can always use the names of the formal arguments to specify a named argument. This not only clarifies what overload you're calling, you can also easily change the order of the arguments. For example:

let d = new DateTime(month=12, day=11, year=2008)

makes it very clear that we're talking about December 11th here. If you're from the US, it even looks 'normal'. Europeans may like:

let d' = new DateTime(day=11, month=12, year=2008)

For F#, it's all the same.

You can also mix positional with named arguments, and if the object has setters, you can use these to. For details, read Section 8.4.5 in the F# (draft) language spec.

Technorati: F#,named arguments

Fun with units of measure

Since the CTP, F# has a nice feature in its type system, called units of measure. Briefly, it allows you to specify a unit with any float, and the type system checks that your uses of units are consistent. For example, you can't add a float<m> to a float<ft>, which results in, among other things, less crashes of spacecraft on Mars. I won't go into details, if you're interested but don't know what I'm talking about, read Andrew Kennedy's blog before you continue.

But anyway, using units for, well, tracking units is kind of boring - type systems are made to be abused after all. So here's my attempt to use units of measure to track the lengths of vectors, so that the compiler will for example detect that you try to add two vectors of unequal length.

How can this be achieved? The basic idea is to encode the length of the vector as an exponent to a unit, that is kept in the 'safe vector' type as a unit of measure parameter. To do this, we first need a unit of measure and a 'safe vector' type that uses it:

[<Measure>] type length

type SVec<'a,[<Measure>]'l> = 
    SVec of list<'a> * float<'l>

 

So, SVec is a vector containing elements of type 'a, and with a length encoded in 'l. We'll use the float to both encode the length of the string as a value and as a type; the idea is that SVec ([1,5], 2.0) has type SVec<int, length ^2>. Let's define some utility functions to make type safe vectors:

let nil = SVec ([],0.0)
let cons elem (SVec (xs,un:float<'l>)) : SVec<_,'l length> = 
        SVec (elem::xs, (un + 1.0<_>) * 1.0<length>)
let (=+=) = cons

let removeUnits f = f |> box |> unbox<float> 

let length (SVec (_,c)) = removeUnits c |> int 
let from_list xs (l:float<'u>) : SVec<'a,'u> = 
    if List.length xs <> int (removeUnits l) then raise <| new ArgumentException("Actual length of list is not equal to given length")
    else SVec (xs,l)

'nil' constructs an empty vector. It has type SVec<'a>,1>, denoting a list with zero elements. 'cons' adds an element to the front of the vector. To do this, it needs to do three things:

1. Add the actual element to the front of the list
2. Update the length  value by adding 1
3. Update the length type by multiplying with 1.0<length>

To get the length of a vector, we return the unit value, stripping of all static unit types. I tried this first by dividing by 1.0<'u>,  but it appears that you can't use a type argument as a unit of measure with a constant value. I'm not exactly sure why.

'from_list' takes a list and turns it into a safe vector. You need to provide a list, with the length of the list correctly encoded in both value and type. The value is tested, the type is not: as far as I can see, this is impossible to check.

Let's make a safe vector:

let l = 3 =+= (2 =+= (1 =+= nil))

The type of l is SVec<int,length^3>. Now we can define type-safe multiplication and addition:

type SVec<'a,[<Measure>]'l> = 
    SVec of list<'a> * float<'l>
        static member (+) (SVec (xs, l1): SVec<_,'l>, SVec (ys, l2): SVec<_,'l>) = 
            SVec (zip xs ys |> map (fun (x,y) -> x + y), l1)
        static member (*) (SVec (xs, l1) : SVec<_,'l>, SVec (ys, l2): SVec<_,'l>)=
            zip xs ys |> sum_by (fun (x,y) -> x*y)    

The interesting part is of course not the implementation, but the types: they statically enforce that when you add or multiply two vectors, they have the same length. So:

let sum = l + l

will typecheck fine, but

let badsum = l + nil

will give a type error!

That concludes my experiment. Some final thoughts:

• This cannot be used to make a type safe head and tail operation, as far as I can see. We'd need an additional type to represent the empty list, and somehow make a head function that can transform between the two types - the kind of overloading necessary does not seem to be possible in F#.
• Try to make a recursive function  with SVec: it's impossible, since generic recursion is impossible.

Technorati: F#,units of measure

How to invoke a method with type parameters using reflection (in F#)

Methods with type parameters arise naturally in F# code, for example:

type Example =
    static member Test l = List.rev l

'Test' has one type parameter 'a, the type of the elements of the list that is being reversed.

In F# you can call the Test method with a list of any type, and the compiler infers the type parameters for you:

let result = Example.Test [1;2;3]

The compiler infers that 'a must be an int.

Mainstream languages such as C# and VB.NET only infer the type arguments at the call site. The programmer needs to declare all the type parameters of a method explicitly. Consider the type signature of the following method:

type Example =
    static member Test2 (a,b) = (fst a = snd b)

Test2 has three type arguments: it takes two tuples a and b as its arguments, which is a total of four types. But since Test2 compares the first element of a with the second element of b, these two are inferred to have the same types. In C#, a programmer would have to infer this for herself, and write:

public static bool Test2<T, U, V>(Tuple<T, U> a, Tuple<V, T> b)
{
   return a.Fst == b.Snd;
}

(of course, assuming that a type Tuple would be defined in .NET, which is not the case if you're not using the F# core libraries)

Because it is obvious that such type annotations require much more work by the programmer, in C# and VB.NET type arguments to methods are in my experience much less common, and much less complex, than what is written without a second thought in F#.

However, recently I faced the problem of calling a number of static methods such as the above using reflection. I had the actual arguments to the method available, so for Test2 above I would have the (type-correct, of course) arguments (true,2.0) and ("whatever", false) available.

To call a method using reflection, you can use MethodInfo.Invoke, on a MethodInfo object obtained using typeof<Example>.GetMethod("Test2") or some such. Executing a non-generic method is easy - just call Invoke() with the actual arguments. However, System.Reflection refuses to call Invoke on a method with unspecified generic arguments (T,U and V for Test2) . You need to specify the actual arguments (bool, float and string for Test2 resp.) manually. So, I had to deduce these from the actual arguments given to the method. The following two functions demonstrate how to do this:

let rec resolve (a:Type) (f:Type) (acc:Dictionary<_,_>) =
    if f.IsGenericParameter then
        if not (acc.ContainsKey(f)) then acc.Add(f,a)
    else 
        Array.zip (a.GetGenericArguments()) (f.GetGenericArguments())
        |> Array.iter (fun (act,form) -> resolve act form acc)

let invokeMethod (m:MethodInfo) args =
    let m = if m.ContainsGenericParameters then
                let typeMap = new Dictionary<_,_>()
                Array.zip args (m.GetParameters()) 
                |> Array.iter (fun (a,f) -> 
                    resolve (a.GetType()) f.ParameterType typeMap)  
                let actuals = 
                    m.GetGenericArguments() 
                    |> Array.map (fun formal -> typeMap.[formal])
                m.MakeGenericMethod(actuals)
            else 
                m
    m.Invoke(null, args)

The second function, invokeMethod, can be used as a replacement for MethodInfo.Invoke that also works for methods with generic arguments. The function above only works for static methods, but taking away this restriction should be straightforward.

invokeMethod takes a MethodInfo m(which should be a static method) and the arguments you want to call the method with. First we check if m is a generic method. If not, nothing needs to be done and we can just call Invoke.

If m is a generic method, we build a a typeMap which maps the formal type arguments to their actual types, for which we can use the signature of the method on the one hand (i.e. as given by the MethodInfo), and the types of the actual arguments args. The function 'resolve' does most of the heavy lifting here, building up the typeMap by comparing actual and formal arguments in a pairwise fashion. 'resolve' needs to be called recursively, since type arguments may be nested arbitrarily deeply. For example,   the formal argument list<'a*option<'b>> should resolve with the actual argument list<int*option<bool>> by mapping 'a to int and 'b to bool.

Once we've determined the actual type arguments to the generic method, System.Reflection lets us instantiate an invoke-able method using MethodInfo.MakeGenericMethod(), which takes an array of actual types that fill in the generic type arguments to the method. If we've determined the type arguments correctly, the result of MakeGenericMethod() is another MethodInfo object that can be invoked as usual.

The interested reader can figure out the details.

Some notes:

• 'resolve' is not tail-recursive. I just didn't bother since you would need to write some extremely convoluted method arguments to blow the stack. list<list<list<list<(repeat x 1000 000)>>>> anyone? Also for the same reason I didn't worry about performance - I don't actually expect to have very deeply nested types. (if type classes were ever added to F#, I guess I would  need to start worrying about that...)
• I dislike that I used a Dictionary in there, though it seemed to be the most elegant solution. I tried using a Map, but then I had to merge maps when the recursive call to resolve returned. It seemed easier with a (non-functional) Dictionary. If anyone can do better, I'd like to hear about it.

Technorati: F#,System.Reflection