Overloading operators in type extensions

Question

Ok, so I'm basically trying to add the bind operator to the option type and it seems that everything I try has some non-obvious caveat that prevent me from doing it. I suspect is has something to do with the limits of the .NET typesystem and is probably the same reason typeclasses can't be implemented in user code.

Anyways, I've attempted a couple of things.

First, I tried just the following

let (>>=) m f = ???

realizing that I want to do different things based on the type of m. F# doesn't allow overloads on function but .NET does allow them on methods, so attempt number two:

type Mon<'a> =
    static member Bind(m : Option<'a>, f : ('a -> Option<'b>)) =
        match m with
        | None -> None
        | Some x -> f x
    static member Bind(m : List<'a>, f : ('a -> List<'b>)) = 
        List.map f m |> List.concat

let (>>=) m f = Mon.Bind(m, f)

No dice. Can't pick a unique overload based on previously given type info. Add type annotations.

I've tried making the operator inline but it still gives the same error.

Then I figured I could make the >>= operator a member of a type. I'm pretty sure this would work but I don't think I can hack it in on existing types. You can extend existing types with type Option<'a> with but you can't have operators as extensions.

That was my last attempt with this code:

type Option<'a> with
    static member (>>=) (m : Option<'a>, f : ('a -> Option<'b>)) =
        match m with
        | None -> None
        | Some x -> f x

"Extension members cannot provide operator overloads. Consider defining the operator as part of the type definition instead." Awesome.

Do I have any other option? I could define separate functions for different monads in separate modules but that sounds like hell if you want to use more than one version in the same file.

Answer 1

You can combine .NET overload resolution with inline/static constraints in order to get the desired behaviour.

Here's a step by step explanation and here's a small working example for your specific scenario:

type MonadBind = MonadBind with
    static member (?<-) (MonadBind, m:Option<'a>, _:Option<'b>) = 
        fun (f:_->Option<'b>) ->
            match m with
            | None -> None
            | Some x -> f x
    static member (?<-) (MonadBind, m:List<'a>, _:List<'b>) = 
        fun (f:_->List<'b>) ->
            List.map f m |> List.concat

let inline (>>=) m f : 'R = ( (?<-) MonadBind m Unchecked.defaultof<'R>) f

[2; 1] >>= (fun x -> [string x; string (x+2)]) // List<string> = ["2"; "4"; "1"; "3"]
Some 2 >>= (fun x -> Some (string x))          // Option<string> = Some "2"

You can also specify the constraints 'by hand', but when using operators they're inferred automatically.

A refinement of this technique (without the operators) is what we use in FsControl to define Monad, Functor, Arrow and other abstractions.

Also note you can use directly Option.bind and List.collect for both bind definitions.