OCaml Functors as Interfaces Take 2

We left off in a rather unsatisfying predicament, we can simulate OCaml functors with interfaces, but at the expense of passing in two type parameters and guarding all our functions with type constraints.  Yuck!

 

Let’s solve both these problems

 

OCaml Functors at the Type Level

 

Let’s leave the realm of regular F# and pretend we’re able to declare static members on our interfaces.  This allows us to pass functions around with the type parameters themselves instead of just the instances.  With this one simple enhancement to interfaces we can now declare the following signatures.

 

#type comparison = Less | Equal | Greater;;

type comparison = Less | Equal | Greater

 

#module type ORDERED_TYPE =

   sig

     type t

     val compare: t -> t -> comparison

   end;;

module type ORDERED_TYPE = sig type t val compare : t -> t -> comparison end

 

#module OrderedString =

   struct

     type t = string

     let compare x y = if x = y then Equal else if x < y then Less else Greater

   end;;

module OrderedString : sig type t = string val compare : ‘a -> ‘a -> comparison end

 

becomes

 

type comparison = Less | Equal | Greater

 

type ORDERED_TYPE<’a> =

    static type t : ‘a

    static abstract compare : t -> t -> comparison

 

type OrderedString() =

    interface ORDERED_TYPE<string> with

        member compare x y = if x = y then Equal else if x < y then Less else Greater

 

and our set signature with only the add function gets simplified to the following.

 

type Set<’con> when ‘con :> ORDERED_TYPE<con.t> () =

    member me.add (x : con.t) (s : con.t list) =

        let rec add (x : con.t) (s : con.t list) =

            match s with

            | [] -> [x]

            | hd::tl ->

                match con.compare x hd with

                | Equal   -> s         (* x is already in s *)

                | Less    -> x :: s    (* x is smaller than all elements of s *)

                | Greater -> hd :: add x tl

        add x s

 

By allowing functions to be passed around with type parameters, we now only have to pass a single type parameter because we can extract the underlying type by a call to t.  Also, we no longer have to pass constrained types into our add function.  We can simply call the static compare function on our con type parameter.

 

Of course, we don’t have “fancy” type level programming in F# so we’re forced to solve the problem at the instance level.

 

OCaml Functors at the Instance Level

 

Type constraints seem of little use when you can’t perform type level programming.  So let’s move the type constraint from the parameter list to the constructor.  Let’s redefine our interfaces and set type.

 

type ORDERED_TYPE<’a> =

    abstract compare : ‘a -> ‘a -> comparison

 

type OrderedString() =

    interface ORDERED_TYPE<string> with

        member me.compare x y = if x = y then Equal else if x < y then Less else Greater

 

type Set<’a> (cf : ORDERED_TYPE<’a>) =

    member me.empty : ‘a list = []

    member me.add (x : ‘a) (s : ‘a list) =

        let rec add (x : ‘a) (s : ‘a list) =

            match s with

            | [] -> [x]

            | hd::tl ->

                match cf.compare x hd with

                | Equal   -> s         (* x is already in s *)

                | Less    -> x :: s    (* x is smaller than all elements of s *)

                | Greater -> hd :: add x tl

        add x s

 

Just as with the type level example, we now only need a single type parameter and no longer have to constrain our functions with type constraints.  The use of the class really isn’t too bad.

 

let StringSet = Set<string>(OrderedString())

let r1 = StringSet.add “do” (StringSet.add “re” (StringSet.add “mi” StringSet.empty))

printfn “%A” r1

 

prints [“do”;”mi”;”re”] to the console we can easily compose a different version of our set.  For instance,

 

type OrderedStringReverse() =

    let reverse (s:string) = new string(s |> Seq.to_array |> Array.rev)

    interface ORDERED_TYPE<string> with

        member me.compare x y =

            let rev_x = reverse x

            let rev_y = reverse y

            if rev_x = rev_y then Equal else if rev_x < rev_y then Less else Greater

 

let StringSetReverse = Set<string>(OrderedStringReverse())

let r2 = StringSetReverse.add “do” (StringSetReverse.add “re” (StringSetReverse.add “mi” StringSetReverse.empty))

printfn “%A” r2

 

prints [“ro”;”mi”;”do”].  So by passing the constraint to the constructor we can change the structure our “functor” generates.

 

What Do We Lose?

 

Compossibility.   In the second example our StringSetReverse only exists at runtime.  The following declaration fails.

 

type StringSetReverse = Set<string>(OrderedStringReverse())

 

We cannot make StringSetReverse part of our type system and use it as a type in other areas of our program.  We’ve lost the ability to compose complex types from simpler ones.  How important you consider composing complex types from simple ones will determine how much you feel F# has lost compared to OCaml.