Faking typeclasses with static type constraints in F#

18 Sep 2014

Introduction

It seems natural that when learning a new programming people try and apply concepts or practices which they've experienced before in other languages. Before learning F# I, like many people, had toyed with Haskell so part of getting to grips with F# was going though the process of reimplementing some of the types and functions I'd come across in Haskell into F#. Firstly, the Maybe type.

type Maybe<'a> =
    | Just of 'a
    | Nothing

Once I'd defined the type then it was natural to define the functor and monadic operations for the type.

let fmap f v = 
    match v with 
    | Just x -> Just (f x)
    | Nothing -> Nothing

let return' v = Just v

let bind v f = 
    match v with 
    | Just x -> f x
    | Nothing -> Nothing

let ( >>= ) = bind

And finally, we can define a computation expression builder for our type.

type MaybeBuilder() = 
    member x.Bind(v,f) = bind v f
    member x.Return v = return' v

let maybe = MaybeBuilder()

And we can quite happily use this new type and computation expression.

let result = 
    maybe {
        let! x = Just 1
        let! y = Nothing
        return 5
    }

This all works very nicely. However, I started to have issues when defining an Either type. F# does not support function overloading based on the function parameter types, so I could not redefine fmap, return' or bind/>>= unless I put these definitions in their own module, seperate from the definitions for Maybe. Even though each type will have it's own implementation of, say, bind, it might still be nice to have a single definition of >>= which is "overloaded" for each monadic type. It's at this point that I started trying to use interfaces to replicate Haskell's typeclasses and came up against a brick wall. The interface that I'd need to declare would look something like this:

public interface IMonad<M, A>
{
    M<B> Bind<B>(M<A> m, Func k);
    M<A> Return(A a);
}

Unfortunately, this interface definition will not compile. The CLR type system is not capable of representing this type of construct. An excellent article explaining why this is the case can be found on Joe Duffy's blog (the original link seems to be broken so here's the google cache version).

Statically resolved type parameters to the rescue

I ended up abandoning this experiment for a while in favour of looking at other areas of the F# language and I eventually came across statically resolved type parameters. A statically resolved type parameter is exactly what it sounds like, a type that is resolved and replaced at compile time as opposed to run time. Crucially, statically resolved type parameters can have interesting constraints placed upon them. Here's a slightly contrived example:

type TypeA = | TypeA of int
    with member x.GetVal = match x with TypeA v -> v

// Declaration with a statically resolved type parameter.
// We require that the parameter 'a' be of type ^a.
// We then constrain ^a such that it must have a member function
// named GetVal that takes no parameters and returns an integer.
// We then apply this statically resolved function to the parameter 'a'
// to yield the integer that was wrapped in TypeA.  We can now increment
// and return the number.
let inline increment (a : ^a) : int =
   let v1 = (^a : (member GetVal : int) a)
   v1 + 1

let t1 = TypeA 1
let result = increment t1

The only constraint we placed upon the increment function was that the parameter a have a member named GetVal that returns an integer. We can pass any parameter to this function that fullfills this constraint. The following is still perfectly valid:

// Declare a new type that satisfies the type constraint for increment
type SomeOtherType =  SomeOtherType
    with member x.GetVal = (new System.Random()).Next()

let t2 = SomeOtherType
let result2 = increment t2

The ability to constrain an argument by the members it defines is called structural typing or, more colloquially, duck typing.

Armed with our new knowledge of statically resolved type parameters is it possible to define to a single function that can be applied to arguments of both Maybe and Either types? Yes:

// Single definition of each of our Monadic functions. Each is constrained
// to require the supplied monadic type to define a doReturn or a 
// doBind function.
let inline return' (v : ^a) : ^b =
   (^b : (static member doReturn : ^a -> ^b) v)

let inline bind (v : ^a) (f : ^b) =
   (^a : (static member doBind : ^a -> ^b -> ^c ) v,f)

let inline (>>=) v f = bind v f

type Maybe<'a> = 
    | Nothing 
    | Just of 'a
    static member inline doReturn(v) = Just v
    static member inline doBind(v,f) = 
        match v with 
        | Just v' -> f v'
        | Nothing -> Nothing

type Either<'a, 'b> = 
    | Left of 'a 
    | Right of 'b     
    static member inline doReturn(v) = Right v
    static member inline doBind(v,f) =
        match v with 
        | Right v' -> f v'
        | Left v' -> Left v'

let m1 = (Just 1) >>= (fun x -> return' (x + 1)) >>= (fun x ->return' (x.ToString()))
let e1 = (Right 1) >>= (fun x -> return' (x + 1)) >>= (fun x ->return' (x.ToString()))

Our bind function, >>= can be successfully applied to both Either and Maybe types. It's now possible to simulate Haskells do-notation with a single definition of a DoBuilder:

type DoBuilder() =
    member inline x.Bind (v,f) = bind v f
    member inline x.Return v = return' v 

let do' = DoBuilder()

let mTest = 
    do'{
        let! a = (Just 1)
        return a
    }

let eTest : Either<string, int> = 
    do'{
        let! a = (Right 1)
        return a
    }

Conclusion

For me, this was an interesting learning exercise into some of F#'s lesser well-known capabilities. Whilst it's possible to replicate some of the power of typeclasses I get the feeling that the resulting F# is somewhat un-idiomatic. Having said that, a similar approach has been used in the fsharpx library.

Published on 18 Sep 2014 permalink Find me on Github

comments powered by Disqus