Another application of the technique showed in previous posts is to emulate Haskell’s typeclasses.
If you’re not familiar with typeclasses I would recommend reading this tutorial. The typeclassopedia goes through most of the typeclasses covered in this code.
We know how to overloaded functions using an intermediate DU with overloaded operators, this will allow us to define overloads for predefined or built-in types like list and option.
Here’s our first try to define the Functor class.

type Fmap = Fmap with
    static member ($) (Fmap, x:option<_>) = fun f -> Option.map f x
    static member ($) (Fmap, x:list<_>  ) = fun f -> List.map   f x
let inline fmap f x = Fmap $ x <| f

Now we can try, for example:

> fmap ((+) 2) [1;2;3] ;;
val it : int list = [3; 4; 5]
> fmap ((+) 2) (Some 3) ;;
val it : int option = Some 5

It works as expected, now let’s try the Monad class.
We need two types, one for return and another one for (>>=).
One thing we will need to resolve to implement return is how do we specify different overloads when the only overloaded parameter is the output.
One trick to achieve this is sending a value of the return type as input, that value shouldn’t be used because it may contain an invalid value for that type (ie: a null for a DU).
Here’s how:

type Return = Return with
    static member ($) (Return, t:'a option) = fun (x:'a) -> Some x
    static member ($) (Return, t:'a list)   = fun (x:'a) -> [x]
let inline return' x : ^R = (Return $ Unchecked.defaultof< ^R> ) x

type Bind = Bind with
    static member ($) (Bind, x:option<_>) = fun f -> Option.bind f x
    static member ($) (Bind, x:list<_>  ) = fun f ->
        let rec bind f = function
                         | x::xs -> f x @ (bind f xs)
                         | []    -> []
        bind f x
let inline (>>=) x f = Bind $ x <| f

Some tests

> let a:list<_> = return' 1 ;;
val a : int list = [1]

> let a:option<_> = return' 1 ;;
val a : int option = Some 1

> [(+) 10;(*) 2] >>= fun f -> [f 1;f 2;f 3] ;;
val it : int list = [11; 12; 13; 2; 4; 6]

> return' ((+) 10) >>= fun f -> Some (f 1) ;;
val it : int option = Some 11

Eventually we will need a method accepting two polymorphic parameters, both input parameters or an input and an output parameter.
Then we will need a ternary operator, the only one ternary operator in F# is the dynamic assignment (?<-).
The 2nd parameter of this operator is expected to be a string, so type inference will unify it by default with the string type, that's why it will be used for the DU that represent the function we're overloading.
Because this operator will cover more cases we will adopt it and use it, even if there are unused parameters (as will be the case for return), just to make the signatures easier.
Another thing we can do to make the signature more readable is accept an unused value for the DU but instead of _ will be named _Monad in this example. We will use it to represent the name of the Typeclass.

So return' and bind will be defined as:

// return’ and (>>=)

type Return = Return with
    static member (?<-) (_, _Monad:Return, _:'a option   ) = fun (x:'a) -> Some x
    static member (?<-) (_, _Monad:Return, _:'a list     ) = fun (x:'a) -> [x]
let inline return' x : ^R = (() ? (Return) <- Unchecked.defaultof< ^R> ) x

type Bind = Bind with
    static member (?<-) (x:option<_>  , _Monad:Bind,_:option<'b>) = fun f -> Option.bind f x
    static member (?<-) (x:list<_>    , _Monad:Bind,_:list<'b>  ) = fun f ->
        let rec bind f = function
                         | x::xs -> f x @ bind f xs
                         | []    -> []
        bind f x
let inline (>>=) x f : ^R = (x ? (Bind) <- Unchecked.defaultof< ^R> ) f


Do Notation

Having defined the Monad class, we can define a generic computation expression.
This will be very similar to Haskell's do notation, but because do is an F# reserved word we will use do' instead.

type DoNotationBuilder() =
    member inline b.Return(x) = return' x
    member inline b.Bind(p,rest) = p >>= rest
    member b.Let(p,rest) = rest p
    member b.ReturnFrom(expr) = expr
let do' = new DoNotationBuilder()

This way the liftMs functions can be defined the Haskell way:

let inline liftM  f m1      = do' { let! x1 = m1 in return (f x1) }
let inline liftM2 f m1 m2   = do' { let! x1 = m1 in let! x2 = m2 in return (f x1 x2) }



Adding new instances to existing Typeclasses

Now, let's suppose we have this code already defined in a library and we can't or we don't want to change it, the question is how do we declare functions of a new type as instance of an existing class.

As an example we will create the type IO (same as in Haskell) and make it a Monad.

Well, all we have to do is declare the new type and implement the corresponding static method from the class we're interested on, with same signature as it was defined, I mean with the arguments in the same order.

Here's how

type IO<'a> = IO of (unit->'a)

let runIO  (IO f)   = f()
let primretIO  f    = IO(fun () -> f)
let primbindIO io f = IO(fun () -> runIO (f (runIO io )))

let getLine    = IO(fun() -> System.Console.ReadLine())
let putStrLn x = IO(fun() -> printfn "%s" x)

type IO<'a> with // these are not Extension Methods
    static member (?<-) (_      , _Monad:Return, _:'a IO ) = fun (x:'a) -> primretIO x
    static member (?<-) (x:IO<_>, _Monad:Bind  , _:IO<'b>) = fun f      -> primbindIO x f

Once compiled we can test if it's included on the overload resolution


let action = do' {
    do! putStrLn  "What is your first name?"
    let! fn = getLine
    do! putStrLn  ("Thanks, " + fn)
    do! putStrLn  ("What is your last name?")
    let! ln = getLine
    let  fullname = fn + " " + ln
    do! putStrLn  ("Your full name is: " + fullname)
    return fullname }

    // Compile it and type at the command line runIO action ;;


The F# Typeclasses Library

Based on these techniques I created a project here that mimics many Haskell Typeclasses.
At the time I'm writing this post I was able to define Typeclasses like Functor, Applicative Functor, Monoid, Traversable, Monad and even Monad Transformer and Arrow.
There's still lot of things that could be added to the library. Reviews, suggestions and improvements are welcome.

Conclusion

In this post we covered another trick that will allow us to declare overloads based on the return parameter.
Together with the other techniques covered in previous articles, this post presented a way of implementing Typeclasses in F# at compile time.
As we're not using recursive inlining compile time is not an issue compared to previous posts.

  2 Responses to “Inline Fun Part IV – Type Classes for F#”

  1. Very interesting! I think the only major downside to this technique is lack of extensibility… i.e. can you add new instances outside the library?

  2. Thanks Mauricio.
    Yes, you can add instances (I updated the article explaining how).
    In a few words, the instances should be declared either in the class definition or in the type definition.
    I’m still looking for a way to declare orphan instances although even in Haskell is not a good practice.

 Leave a Reply

(required)

(required)

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

 
© 2012 Nutcracker Suffusion theme by Sayontan Sinha