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.

Nov 072011
 

Although F# seems to have no tuple size limit there’s no primitive functions to “expand” a tuple.
Tuples are intended to be composed and decomposed as Algebraic Data Types, there are only 2 functions provided: fst and snd, and they work only with a 2-uple.
We can build functions with overloads for each arity, up to a reasonable size, the problem with this approach is that we will have a lot of repetitive code for each function.
To avoid the repetitive code, one approach is to use a code generator.
Another approach is to define the primitives functions repeating code and using inline for the rest of the functions.
We can think of a tuple as a list, so the primitives are cons and split in head-tail.
We’ll need a way to represent the 0-uple and a single element 1-uple. For the 1-uple we will a type called Singleton and for the empty tuple we will use the unit value ().

type Singleton<'a>   = Singleton of 'a

type Split = Split with
    static member ($) (Split, Singleton x1    ) = (x1, ())
    static member ($) (Split, (x1,x2)         ) = (x1, Singleton x2)
    static member ($) (Split, (x1,x2,x3)      ) = (x1, (x2,x3))
    static member ($) (Split, (x1,x2,x3,x4)   ) = (x1, (x2,x3,x4))
    static member ($) (Split, (x1,x2,x3,x4,x5)) = (x1, (x2,x3,x4,x5))
 
type Join = Join with
    static member ($) (Join, ()           ) = fun x -> Singleton x
    static member ($) (Join, Singleton x1 ) = fun x -> (x,x1)
    static member ($) (Join, (x1,x2)      ) = fun x -> (x,x1,x2)
    static member ($) (Join, (x1,x2,x3)   ) = fun x -> (x,x1,x2,x3)
    static member ($) (Join, (x1,x2,x3,x4)) = fun x -> (x,x1,x2,x3,x4)

let inline (|Cons|) tuple   = Split $ tuple
let inline Cons (head,tail) = Join $ tail <| head

Functions to be implemented:
Cons – Will be implemented also as an active pattern so we can go both ways.
Rev – Reverse the elements of the tuple.
Map – Map a function into a tuple with elements of the same type.
Fold – Will work also with tuples with elements of the same type.
<*> – Apply each function of the first tuple to the corresponding element of the second tuple. For Haskellers this will be like the <*> operator for the ZipList applicative functor.

We’ll need to define a binary operator, but the first parameter will be the type that represent the function.
As operator we’ll use ($), the Haskell equivalent of (<|) which should be read as 'apply'.
Some functions take 2 parameters, so for the second parameter we may need to use parenthesis, because the binary operator has precedence over the apply:
f a1 a2 = (f $ a1) a2
But we will use the idiomatic F# 'apply' (<|)
f $ a1 <| a2
In some cases we will swap the order of the parameters, because we need the tuple to participate in the ($) operator resolution to select the right overload.
Having implemented the primitives, before doing the rest of the functions, let's think how would they look for lists.

let rec Rev list ac = match list with
                      | x::xs -> Rev xs (x::ac) 
                      | []    -> ac
let rev list = Rev list [] 

let rec Map list f = match list with
                     | x::xs -> f x :: Map xs f
                     | []    -> []
let map f list = Map list f

let rec Fold list f z = match list with
                        | x::xs -> Fold xs f (f z x)
                        | []    -> z
let fold f z list = Fold list f z

let rec Ap fnList list = match fnList with
                         | f::fs -> let (x::xs) = list in (f x :: Ap fs xs)
                         | []    -> []
let (<*>) fnList list = Ap fnList list

Let’s do it point-free.

let rec Rev = function
    | x::xs -> fun ac -> Rev xs (x::ac) 
    | []    -> id
let rev list = Rev list []

let rec Map = function
    | x::xs -> fun f -> f x :: Map xs f
    | []    -> fun _ -> []
let map f list = Map list f

let rec Fold = function
    | x::xs -> fun f z -> Fold xs f (f z x)
    | []    -> fun _ x -> x
let fold f z list = Fold list f z

let rec Ap = function
    | f::fs -> fun (x::xs) -> (f x :: Ap fs xs)
    | []    -> fun _       -> []
let (<*>) fnList list = Ap fnList list

List with different number of elements may share the same type, this is not true with tuples.
For tuples we will go from one type to another all the time.
Remember in previous post the rules to translate a value-level to a type-level implementation?

“for each case in the discriminated union create a separate type, for each case in the match create different overloads of the same method”

We already have different types: () , Singleton, (,) , (,,) , (,,,) and so on. The difference is now we’re using existing types, except for Singleton.
But then in the first post of these series we faced that problem, the solution when we don’t have access to the source code of the type was

“use a DU as intermediate type, implement an operator as static member, accepting an unused parameter which is a value of the DU and the other parameter is overloaded”

So, the same functions for tuples could be written this way:

type Rev = Rev with
    static member inline ($) (Rev, Cons(x,xs)) = fun ac -> Rev $ xs <| Cons(x,ac)
    static member        ($) (Rev, ()        ) = id
let inline rev tuple = Rev $ tuple <| ()

type Map = Map with
    static member inline ($) (Map, Cons(x,xs)) = fun f -> Cons(f x, Map $ xs <| f)
    static member        ($) (Map, ()        ) = fun _ -> ()
let inline map f tuple = Map $ tuple <| f

type Fold = Fold with
    static member inline ($) (Fold, Cons(x,xs)) = fun f z -> Fold $ xs <| f <| f z x
    static member        ($) (Fold, ()        ) = fun _ x -> x
let inline fold f z tuple = Fold $ tuple <| f <| z

type Ap = Ap with
    static member inline ($) (Ap, Cons(f,fs)) = fun (Cons(x,xs)) -> Cons(f x, Ap $ fs <| xs)
    static member        ($) (Ap, ()        ) = fun _            -> ()
let inline (<*>) fnTuple tuple = Ap $ fnTuple <| tuple

A quick test

> rev (1, "second", [3], 4.0) ;;
val it : float * int list * string * int = (4.0, [3], "second", 1)

> map ((+) 10) (5, 15, 25) ;;
val it : int * int * int = (15, 25, 35)

> map string (5, 15, 25) ;;
val it : string * string * string = ("5", "15", "25")

> fold (+) 0 (5, 15, 25) ;;
val it : int = 45

> ((+), (*)) <*> (2, 5.5) <*> (3, 2.0) ;;
val it : int * float = (5, 11.0)

Some functions make more sense with lists, otherwise we are restricted to a tuple of elements of the same type, but in the case of the operator <*> it’s the opposite, it will be more interesting with tuples than with lists because it will be able to operate with different types.

Another interesting function could be nth, but we can’t use integers, because we can’t select a type based on a value.
What we can do is select type based on another type.
Remember Peano numbers?

type Zero     = Zero with
    static member inline (|!|) (Cons(x,_),Zero) = x
 
type Succ<'a> = Succ of 'a with
    static member inline (|!|) (Cons(_,xs),Succ p) = xs |!| p

let inline nth tuple  n = tuple |!| n

Now we can access any element without losing type information.


> let I = Succ Zero ;;
val I : Succ<Zero> = Succ Zero

> let II = Succ I ;;
val II : Succ<Succ<Zero>> = Succ (Succ Zero)

> nth (50, 'b', "F# is fun") Zero ;;
val it : int = 50

> nth (50, 'b', "F# is fun") I ;;
val it : char = 'b'

> nth (50, 'b', "F# is fun") II ;;
val it : string = "F# is fun"



Conclusion

In this post we used and abused of recursive inline functions at the point we’re killing the compiler.
We integrated two different techniques we saw individually in previous posts.
In the next post we will concentrate and refine more this technique.

Oct 272011
 

In previous post we did some “tricks” to create a generic function without creating or changing the types that function handles.
We’re going to dig more into this technique.

We can apply this technique for Type Level Programming, I mean calculations at compile time using the type inference.
A typical example on Type Level Programming is Peano numbers, but before showing the implementation at Type Level let’s have a look at the implementation of Peano numbers as Values.

Peano numbers as values:

type Peano =
    | Zero
    | Succ of Peano
    with
    static member (+) (x,y) =
        match x,y with
        | (Zero  ,b) -> b
        | (Succ a,b) -> Succ (a + b)
    static member (*) (x,y) =
        match x,y with
        | (Zero  ,b) -> Zero
        | (Succ a,b) -> (b + (a * b))

In order to test them we can write:

let p1    = Succ Zero
let p2    = p1 + p1
let p2'   = Zero + p2
let p0    = Zero + Zero
let p1'   = p1 + p0
let p4    = p2 * p2
let p0'   = p0 * p2
let p0''  = p2 * p0
let p0''' = p0 * p0

All variables have the proper value but they have the same type.
For the Type Level implementation we’ll have a different type for each number.
The implementation at Type Level could be:

type Zero     = Zero       
type Succ<'a> = Succ of 'a with
    static member        ( + ) (Zero  , b) = b 
    static member inline ( + ) (Succ a, b) = Succ (a + b)
    static member        ( * ) (Zero,b   ) = Zero
    static member inline ( * ) (Succ a, b) = b + (a * b)

The very basic translation rule between both implementations is, “for each case in the discriminated union create a separate type, for each case in the match create different overloads of the same method”.
But if we try to run the same tests:

  let p0 = Zero + Zero
  ----------------^^^^

stdin(20,17): error FS0001: The type 'Zero' does not support any operators named '+'

As we showed previously the operator resolution looks in the type of both operands. In the first and the second line it finds the definition in the Type Succ but in the third line both operands are of type Zero so it will not look in Succ type.
We can fix it easily by moving the non-inline members to the type Zero.

type Zero     = Zero with      
    static member        ( + ) (Zero  , b) = b 
    static member        ( * ) (Zero  , b) = Zero

type Succ<'a> = Succ of 'a with
    static member inline ( + ) (Succ a, b) = Succ (a + b)
    static member inline ( * ) (Succ a, b) = b + (a * b)

Now if we try the test it will work, but it will take a few seconds to compile.
In fact we don’t need to run the code, just paste the tests in a script file and rollover with the mouse over the variables and you’ll see the results.
That’s the main difference, here it’s not the run-time, it’s the type inference resolving the operations.
What about subtraction?
We can try to resolve 3 – 1 a-la Prolog saying a is 1, a + b is 3, tell me about b:

   
let f (a:Succ<Zero>) b : Succ<Succ<Succ<Zero>>> = a + b
val f : Succ<Zero> -> Succ<Succ<Zero>> -> Succ<Succ<Succ<Zero>>>

Type inference was able to figure out that the type of b is Succ < Succ < Zero > > .
But Type Inference is not a Prolog engine, this will not work with a, but we can implement (-) and other operations.
Here’s the full code:

  
type Yes = Yes
type No  = No

type Zero = Zero with 
    static member ( + ) (Zero  , b     ) = b
    static member ( - ) (a     , Zero  ) = a
    static member ( * ) (Zero  , b     ) = Zero
    static member (.<.) (a     , Zero  ) = No
    static member (.>.) (Zero  , b     ) = No
    static member (.=.) (a:Zero, b:Zero) = Yes    

type Succ<'a> = Succ of 'a with
    static member inline ( + ) (Succ a, b     ) = Succ (a + b)
    static member inline ( - ) (Succ a, Succ b) = a - b
    static member inline ( * ) (Succ a, b     ) = b + (a * b)
    static member inline (.<.) (Succ a, Succ b) = a .<. b
    static member        (.<.) (Zero  , Succ b) = Yes                                
    static member inline (.>.) (Succ a, Succ b) = a .>. b    
    static member        (.>.) (Succ a, Zero  ) = Yes
    static member inline (.=.) (Succ a, Succ b) = a .=. b
    static member        (.=.) (Zero  , Succ b) = No
    static member        (.=.) (Succ a, Zero  ) = No

Conclusion

We saw how to do recursive inlining which is something we will be using (and abusing) in the next post.
We may wonder how is this useful in real-world code.
There are some cases where Type Level Programming will help, we will use it in future posts.
This is not useful to deal with user input, we can’t go from values to types.
But we can go the other way, so it may allow us to develop F# libraries with generic and well constrained functions.
Because the inline feature exists only in the F# world, this kind of libraries will be intended to be used only from F#, although we can expose to .NET non-inline functions.

Oct 052011
 

We know with static member constraints is possible to write more generic functions, duck typing is also possible.
In this series of posts I will show how combining static member constraints and operator resolution is possible to write code that otherwise is not possible with the current .Net Type System.

To illustrate this technique let’s think in an hypothetical situation where we want to implement an overloaded function that works with two different types, but we can’t change those type definitions.
So let’s create a function length : ‘a -> int and ‘a could be a list, an array or a string.

The first attempt may look like this:

type MyHelperType =
    static member length x = String.length x
    static member length x = List.length x
    static member length x = Array.length x

let length x = MyHelperType.length x

It doesn’t work, type inferred is

type MyHelperType =
  class
    static member length : x:string -> int
    static member length : x:'b list -> int
    static member length : x:'a [] -> int
  end
val length : string -> int

Although we can call MyHelperType.length [2;3;4] and MyHelperType.length “hello” we can’t get rid of the helper class at the calling site.
As we’ve seen before this is because .Net overloading is resolved at the calling site, so when we define length it picks up the first overload that match, in this case string.
Second try, we know those types have a Length property:

let inline length x = (^T: (member get_Length: unit -> int) (x))

Works, but we were lucky because we found a built-in method which exists in all those types.
However, we can’t always be that lucky, let’s try now to implement a function append (x:’a) (y:’a) where ‘a could be a string a list of chars or an array of chars.
If they were types we’re defining in the same module, no problem, we add a member cons then the rest is the same as previous solution.
Extension methods will not work, static constraints only look into the class definition.
Remember operators? They have a particular behavior, at operator resolution the compiler looks in every operand class, so for example if we have a binary operator $ : (‘a,’b) -> ‘c it looks first into class ‘a then into class ‘b for the operator definition.
So the trick is we will use an intermediary class with an operator with overloads for the second parameter.

type HelperType = HelperType with    
    static member (=>) (d:HelperType,x: list<char>) = fun y -> x @ y    
    static member (=>) (d:HelperType,x:array<char>) = fun y -> Array.append x y
    static member (=>) (d:HelperType,x:string     ) = fun y -> x + y

let inline append x = HelperType => x

The type inferred is

type HelperType =
  | HelperType
  with
    static member
      ( => ) : d:HelperType * x:char list -> (char list -> char list)
    static member
      ( => ) : d:HelperType * x:char array -> (char [] -> char [])
    static member ( => ) : d:HelperType * x:string -> (string -> string)
  end
val inline append :
   ^a ->  ^_arg3
    when (HelperType or  ^a) : (static member ( => ) : HelperType *  ^a ->
                                                            ^_arg3)

At this point we may wonder if it’s possible to write the same code without operators.
Just copy-paste the inferred type and try.

let inline append (x: ^a) :  ^_arg3 when (HelperType or  ^a) : (static member ( => ) : HelperType *  ^a ->  ^_arg3) = HelperType => x ;;

  let inline append (x: ^a) :  ^_arg3 when (HelperType or  ^a) : (static member ( => ) : HelperType *  ^a ->  ^_arg3) = HelperType => x ;;
  ------------------------------------------^^^^^^^^^^

stdin(3,43): error FS0010: Unexpected identifier in type constraint. Expected infix operator, quote symbol or other token.

It doesn’t work, I don’t know why, personally have no explanation why F# don’t accept the constraint itself infers.

Conclusion

As we’ve seen the trick consists in creating a type, specifically a discriminated union as intermediate type.
There we will implement the operators as static member, accepting an unused parameter which is a value of the DU intentionally to use an instance of that class later at the caller site, the other parameter is overloaded.
Then wrap with a function that will “hide” the DU and the operator.
This is very useful in those cases where we don’t have access to the source code of the type we’re overloading.
This way we can use inline to write more generic code, in future posts we will see more applications and more “tricks”.

Aug 092011
 

In my previous post we defined an overloaded AddVector function.
There is a more convenient way to define those functions: using operators.
We have basically two ways of defining operators in F#, one alternative is to define them at the global scope level as any other function.
Another way is to define them as static members of a type.

Consider this code:

type Vector2D = Vector2D of float * float with
    static member Add(Vector2D(a1,a2),Vector2D(b1,b2)) = Vector2D(a1+b1, a2+b2)

type Vector3D = Vector3D of float * float * float with
    static member Add(Vector3D(a1,a2,a3), Vector3D(b1,b2,b3)) = Vector3D(a1+b1, a2+b2, a3+b3)

We have only the function Add defined for Vector2D and Vector3D, but those are different functions, so if we invoke them we have to specify the Vector type, I mean if we try this:

Add(Vector2D (2.0,3.0) , Vector2D (5.0,3.0) )

We get error FS0039: The value or constructor ‘Add’ is not defined.
If we specify the Class it will work.

Vector2D.Add(Vector2D (2.0,3.0) , Vector2D (5.0,3.0) )

To avoid specifying the class, in the last post we defined an AddVectors which will pick up the right function.
But we could have defined operators:

type Vector2D = Vector2D of float * float with
    static member (+.)  (Vector2D(a1,a2),Vector2D(b1,b2)) = Vector2D(a1+b1, a2+b2)
    static member (~-.) (Vector2D(a1,a2)) = Vector2D (-a1 , -a2)

type Vector3D = Vector3D of float * float * float with
    static member (+.)  (Vector3D(a1,a2,a3), Vector3D(b1,b2,b3)) = Vector3D(a1+b1, a2+b2, a3+b3)
    static member (~-.) (Vector3D(a1,a2,a3)) = Vector3D (-a1, -a2, -a3)

This way we can write directly Vector2D (1.0,2.0) +. Vector2D (6.0,5.0) and it will pick up the right function.
And instead of SubVectors we can define the binary (-.) operator, re-using previous operators:
Now let’s suppose for compatibility reasons we want to define AddVectors, InvVector and SubVectors

let inline AddVectors x y = x +. y
let inline InvVector  x   = -.x
let inline SubVectors x y = x +. -.y

Here we can see how it works, this is the type inferred for AddVectors.

val inline AddVectors :
   ^a ->  ^b ->  ^_arg3
    when ( ^a or  ^b) : (static member ( +. ) :  ^a *  ^b ->  ^_arg3)

When we write exp1 +. exp2 the compiler tries to find the operator defined at the global scope, then as a static member in the type of exp1 and in the type of exp2.

We could have defined all this code with (+) and (-) but then of course, these functions will work with everything that has a binary (+) operation and an unary (-) operation defined, I mean if we call SubVectors 10.0 5.0 will work as well.

Now we will try to generalize this code.
Right now it works only with floats but let’s make it work with all underlying types that support (+) and (-).
All we have to do is make the static members inline, type inference will do the rest for us.

type Vector2D<'a> = Vector2D of 'a * 'a with
    static member inline ( +.) (Vector2D(a1,a2),Vector2D(b1,b2)) = Vector2D(a1+b1, a2+b2)
    static member inline (~-.) (Vector2D(a1,a2)) = Vector2D (-a1 , -a2)

type Vector3D<'a> = Vector3D of 'a * 'a * 'a with
    static member inline ( +.) (Vector3D(a1,a2,a3), Vector3D(b1,b2,b3)) = Vector3D(a1+b1, a2+b2, a3+b3)
    static member inline (~-.) (Vector3D(a1,a2,a3)) = Vector3D (-a1, -a2, -a3)

let inline AddVectors x y = x +. y
let inline InvVector  x   = -.x
let inline SubVectors x y = x +. -.y


Global Level operators vs operators as static members

The global level definition in fact is not that global, it is restricted to the scope.
Surprisingly, it has priority over the static member definition.
When an operator is found the compiler first try to find a “global” definition at the local scope, if no definition is found then it is assumed as an operator defined at the type of one of the operands.

In F# some operators are already defined at the global level, for instance (+) operator is defined at global level, then in that definition the plus operator as static member is invoked.

Let’s compare these definitions at global level:

> let inline f x = (+) x ;;

val inline f :
   ^a -> ( ^b ->  ^c)
    when ( ^a or  ^b) : (static member ( + ) :  ^a *  ^b ->  ^c)

> let inline g x = ($) x ;;

val inline g :
   ^a -> ( ^_arg2 ->  ^_arg3)
    when ( ^a or  ^_arg2) : (static member ( $ ) :  ^a *  ^_arg2 ->  ^_arg3)


Function f has a different signature as g. This is because f is re-using the global definition from (+) while in the other case there is no global definition for ($), so function g will call directly a static member ($) in the first or the second operand type.
The constraints we have in function f are automatically generated by the use of (+) in his body, taken from (+) definition at global definition whereas the constraints of g are generated “from scratch”.

Conclusion
If used properly operators can improve code readability.
Operators can behave as functions, we just need to enclose them in parenthesis.
There is no need to specify static constraints, in most cases they are automatically guessed by the compiler.
Another possibility is to define operators at the global scope.

Jun 192011
 

In principle overloading is just a syntactic construct where we define two or more different functions with the same name, but for this post I would like to point out a distinction between two different overloading approaches:
For the rest of this post I will use the terms “unrelated overload” and “related overload”.

Unrelated overloads: When there are different number of parameters or the same number but still with no intrinsic relationship between each overload parameter types.
We find this ad-hoc overloading in many .Net framework methods like Int32.Parse where we have one overload that use NumberStyles, another that uses IFormatProvider and another one that uses both.

Related overloads: The same number of parameters with different input parameter types but with an intrinsic relationship between them.
As an example, F# defines the operator (*) for several types, but those types are different way of representing numbers.

In languages like C# you can define both related and unrelated overloads but as we will see later it will not allow you to scale up and generalize over overloaded functions.

In Haskell you can’t define unrelated overloads, in order to define overloads you need to establish first a relationship between the different types through typeclasses, but this will allow you to create generic functions on top of the overloaded function.
Another difference is in Haskell you can have two functions where the only overloaded parameter is the output parameter. This makes sense because in FP languages with currying there no distinction between input and output parameters.
Because F# is functional and on top of the .NET framework both types of overload are available in F#, the former happens at .NET compile time and the latter is handled by the F# compiler.

Overloading in F#

The first problem we can imagine when overloading in most functional programming languages is conflicting with currying when we have different number of parameters, but this can be solved if we use tupled arguments.
Anyway if we want to write directly different overloads in F# we have to do it in methods and method’s parameters can’t be directly curried.
The next problem could be type inference.
This approach works the same as in C#, the overloading is resolved at compile time each time we call the method.
Related and unrelated overloading can be achieved this way.

There is another way to do overloading in F# which is not available in C#: inline functions with static constraints.
This option requires, as in Haskell, to specify first a relationship between the types.
In F# you specify this relationship with static constraints.

type Vector2D = Vector2D of float * float with
    static member Add(Vector2D(a1,a2),Vector2D(b1,b2)) = Vector2D(a1+b1, a2+b2)
    static member Inv(Vector2D(a1,a2)) = Vector2D (-a1 , -a2)

type Vector3D = Vector3D of float * float * float with
    static member Add(Vector3D(a1,a2,a3), Vector3D(b1,b2,b3)) = Vector3D(a1+b1, a2+b2, a3+b3)
    static member Inv(Vector3D(a1,a2,a3)) = Vector3D (-a1, -a2, -a3)

let inline AddVectors x y = (^Vector: (static member Add: ^Vector -> ^Vector -> ^Vector) (x,y))
let inline InvVector  x   = (^Vector: (static member Inv: ^Vector -> ^Vector) (x))

In the code above, the function AddVectors will accept any type that has a static member Add with the signature ‘a->’a->’a.
A function declared inline will be resolved also at compile time at every point that function is called.
This kind of functions can be called also from other F# assemblies, because they are “shipped” with F# metadata which allows inlining in another F# assembly.

AddVectors (Vector2D (1,2)) (Vector2D (3,4))
let Sum3D (x:Vector3D) = AddVectors x

At the caller site should be clear which overload will be used, but not always.
What happens if the caller is inside another inline function?
In that case the caller function is also inline, so in this case the type is still not “decided”.
This way we can define generic functions by “chaining” inline functions.

let inline SubVectors x y = AddVectors x (InvVector y)

Note that here it’s no longer necessary to declare the static constraints, type inference is smart enough to do it for us.
If we compare this technique with C#’s method overloading, what’s the difference? Can’t we achieve the same with standard .Net method overloading?

The first difference is with inline we defined a function that will decide between two methods (which are seen as the same method) on two different types whereas with member overloading the decision is between two different methods on the same type.
Anyway we can rewrite the code like this:

type Vector2D = Vector2D of float * float
type Vector3D = Vector3D of float * float * float 

type VectorOperations = VectorOperations with
    static member Add(Vector2D(a1,a2),Vector2D(b1,b2)) = Vector2D(a1+b1, a2+b2)
    static member Inv(Vector2D(a1,a2)) = Vector2D (-a1 , -a2)
    static member Add(Vector3D(a1,a2,a3), Vector3D(b1,b2,b3)) = Vector3D(a1+b1, a2+b2, a3+b3)
    static member Inv(Vector3D(a1,a2,a3)) = Vector3D (-a1, -a2, -a3)

And now we can call those functions this way:

VectorOperations.Add (Vector2D (1.0,2.0) ,Vector2D (3.0,4.0))
VectorOperations.Add (Vector3D (1.0,2.0,4.0) ,Vector3D (3.0,4.0,6.0))

What happen here? The method is resolved at the point is called, .Net support this without inlining.
Now the question is, can we go further and chain generic functions?
Here’s the answer

> let SubVectors x y = VectorOperations.Add ( x , (VectorOperations.Inv y)) ;;

  let SubVectors x y = VectorOperations.Add ( x , (VectorOperations.Inv y)) ;;
  -------------------------------------------------^^^^^^^^^^^^^^^^^^^^^^

stdin(6,50): error FS0041: A unique overload for method 'Inv' could not be determined based on type information prior to this program point.
The available overloads are shown below (or in the Error List window). A type annotation may be needed.
Possible overload: 'static member VectorOperations.Inv : Vector3D -> Vector3D'.
Possible overload: 'static member VectorOperations.Inv : Vector2D -> Vector2D'.

It doesn’t work because at this point the compiler needs to decide which overload are we using, there’s no way to continue chaining, except defining again two overloaded methods which will contain exactly the same code, but operate on different types

type VectorOperations' = VectorOperations' with
    static member Sub(x: Vector2D,y: Vector2D) = VectorOperations.Add ( x , (VectorOperations.Inv y))
    static member Sub(x: Vector3D,y: Vector3D) = VectorOperations.Add ( x , (VectorOperations.Inv y))

The code above will work, but requires code duplication, both methods have the same body. If we add an overload for VectorOperations.Add for Vector4D we will have to add the corresponding overload in every chained method to make it work.
With inline functions it’s possible to make them “share” the body, and in this case adding a type Vector4D with the basic operations Add and Inv will automatically make work the function Sub with Vector4D.

Conclusion:

.NET overloading
. Related or unrelated types
. No “chaining” of overloaded function, the overload will be decided always at each call site.
. Overloading is really ad-hoc, they are just different functions with the same name.

Overloading using inline and hat types
. Static constraints explicit relationship between different overloaded types.
. “Chaining” overloaded functions is possible.
. It’s possible to define generic functions.