Nov 152011
 

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.

  10 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?

    • 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.

  2. Can this be used to declare

    1) typeclasses that depend on other typeclasses? For example, if one would like to define a monoid in terms of a semigroup, or declare that all monads are automatically applicative functors too?

    2) typeclass operation which would require typeclass constraints on the argument, like traversable’s sequence operation requiring the type argument of the traversable to be an applicative?

    I don’t know F# but am interested in comparing level of typeclass support betwen languages. Thanks!

    • Hi Ron,

      Sorry for the very late reply, since you posted your comment this technique was refined so now I can say the short answer is YES, here’s the long story:

      1) Actually this technique was refined and it took me many sleepless nights but finally I found a way to do this, though not straightforward and not always achievable.
      Here’s a project where I defined a default for Applicative Functors which are already Monads, in the latest version the applicative instances were reintroduced to increase a bit the performance but otherwise it works as well.

      2) This is also possible, but not straightforward, you need to fight a bit with static constraints until you get the desired behaviour. Here’s a portion of the above mentioned project where I define Traversable and by the use of the applicative is inferred the constraint.

      Conclusion: It’s not native as in Haskell, F# does not have this feature but still we can workaround until we get the desired behaviour in most cases.

      Thanks

  3. Hello Gustavo,

    It may be a long time since you’ve had responses to this but as it happens your work would be very useful for a project of mine, involving operations on heterogeneous vectors (basically functions for tuples as you’ve described earlier in this series).

    I’m using Monodevelop on the Mac (and new to that platform) and I wondered if you could give me any pointers on how to install your fsharp-typeclasses on that platform?

    All the best,
    Matthew.

    • Hi Matthew,

      Sorry for the very late reply.
      You’re project is probably already finished and you might be an expert in Monodevelop on Mac by now.
      Anyway here’s the response:
      The project fsharp-typeclasses was exploratory, not intended to use in production code.
      After some time playing with that code I decided to create FsControl a production-code-project, more focused in F# which you can use for your projects.
      It is available in Nuget for an easy install.

      Thanks

  4. Interesting. I was experimenting a bit and thinking about whether there is a way how to enforce type class constraints in function signature similarly to haskell, e.g. in the example of YesNo type class (see http://learnyouahaskell.com/making-our-own-types-and-typeclasses#a-yes-no-typeclass) where having defined a type class YesNo, the function signature may be :

    yesnoIf :: (YesNo y) => y -> a -> a -> a

    (notice the YesNo constraint). I was only able to specify the function as inline. However, as the function contract is not explicit, it might be difficult for other developers to read the code at first sight.

  5. Hey! I’ve been playing around with this and I was wondering if you found a way to make a function polymorphic in more than 2 types? Since ? ‘c, ‘d) and I’ve tried two things. Firstly, I tried chaining two ?<- operators with separate groups of overloads. One group that matches all combinations of 'a and 'b, and the second group that matched combinations of 'c and 'd, but after a ton of cryptic type errors I figured it wouldn't work like that.
    Secondly, I tried a similar approach with two separate usages of ? ‘d. Then the second usage takes two functions ‘b -> ‘c and ‘a -> ‘d where the first function is the one I actually use and the second is just a dummy function (the result of the first ?<-). I figured I could do that and pack two types into one type. That didn't work either.

    Have you found a better approach?

    • Hi Luka,

      I think it would be possible, but am not sure of what you are trying to do, can you link a gist with your attempts?

      Thanks

 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>