OCaml Functors as Interfaces

The following page describes in detail the differences between the OCaml and F# languages. It’s a good read for anyone familiar with OCaml and an even better read for those who are not.  For the first line of the summary declares

 

Functors, OCaml-style objects, labels and option arguments are not supported.  Some common functors like Set.Make and Hashtbl.Make are simulated by returning records of functions.

 

Simulating functors by returning records of functions sounds interesting.  Let’s take a closer look at what functors in OCaml are.

 

OCaml Functors

 

Chapter 2 of the OCaml manual has a pretty good example of using functors.  I have to admit that just finding a good example was somewhat of a chore, which suggests either functors aren’t used a whole lot by OCaml programmers or nobody understands them.

 

The example starts by declaring a signature to represent types that are orderable.

 

#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

 

We’ll fall back on our object oriented upbringing and use an interface to model the same signature in F#.

 

type comparison = Less | Equal | Greater

 

type ORDERED_TYPE<’a> =

    abstract t : ‘a

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

 

Now a structure is created for strings. Notice how there is no explicit connection between the structure and the signature.

 

#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

 

We have no choice but to explicitly implement our interface signature.

 

type OrderedString(t : string) =

    interface ORDERED_TYPE<string> with

        member me.t = t

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

 

For those paying attention you’ll see a subtle difference between the two OrderedString declarations.  The F# declaration returns an instance of a string for t instead of the type of string.  In fact, whereas the F# definition appears to be an instance of type the OCaml version appears to be a type of a type.

 

Implementing Set as a Functor

 

The type signature are done, let’s move on to the meat of building our functor.  We’ll start with the signature.

 

module Set :

  functor (Elt : ORDERED_TYPE) ->

    sig

      type element = Elt.t

      type set = element list

      val empty : ‘a list

      val add : Elt.t -> Elt.t list -> Elt.t list

      val member : Elt.t -> Elt.t list -> bool

    end

 

And examine the implementation of the signature piece by piece.

 

#module Set =

   functor (Elt: ORDERED_TYPE) ->

     struct

       type element = Elt.t

       type set = element list

 

So a set is a functor that takes an ordered type as a parameter.  The type is then extracted and stored in the element type.  I have a feeling our F# definition will have to be quite different.

 

type Set<’a,’con> when ‘con :> ORDERED_TYPE<’a> () =

 

And so it is.  With F# we can’t combine the constraint and underlying type as a single parameter.  Unlike OCaml we have no way of extracting the underlying type from the container type.  This results in an unfortunate redundant construction.

 

So the construction of our types are different, let’s analyze the functions.

 

let empty = []

let rec add x s =

  match s with

    [] -> [x]

  | hd::tl ->

     match Elt.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

let rec member x s =

  match s with

    [] -> false

   | hd::tl ->

      match Elt.compare x hd with

        Equal   -> true     (* x belongs to s *)

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

      | Greater -> member x tl

 

And the corresponding F# implementation.

 

member me.empty : ‘con list = []

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

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

        match s with

        | [] -> [x]

        | hd::tl ->

            match x.compare x.t hd.t 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   

member me.is_member (x : ‘con) (s : ‘con list) =

    let rec is_member (x : ‘con) (s : ‘con list) =

        match s with

        | [] -> false

        | hd::tl ->

            match x.compare x.t hd.t with

            | Equal   -> true     (* x belongs to s *)

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

            | Greater -> is_member x tl

    is_member x s

 

The fundamental difference with the F# code is we’re forced to work with the constraint instead of the underlying type.  Because the compare function is only available on instances of ordered types we can only pass those types into our set.

 

The compare function in the OCaml example however is attached to type itself instead of an instance of the type.  Remember how our OCaml structure was more analogous to a type of type rather than an instance of a type?  This allows us to solve problems at the type level instead of always relying on runtime dispatch for polymorphism.

 

Applying the Set Functor

 

So we’ve built a signature for an ORDERED_TYPE.  We’ve created a structure for a string type that implements the signature.  We’ve created a functor called Set that can be applied to the structure.  So let’s finish this off and do the application.

 

#module StringSet = Set(OrderedString);;

module StringSet :

  sig

    type element = OrderedString.t

    type set = element list

    val empty : ‘a list

    val add : OrderedString.t -> OrderedString.t list -> OrderedString.t list

    val member : OrderedString.t -> OrderedString.t list -> bool

  end

 

The application of the functor creates a new set for ordered strings.  We can now use this set with functions that only work with strings.

 

#StringSet.member “bar” (StringSet.add “foo” StringSet.empty);;

- : bool = false

 

The application of our F# “functor” is slightly messier because of the inherent redundancy.

 

let StringSet = Set<string,OrderedString>()

 

And of course we have to wrap our strings in OrderedStrings.

 

let result = StringSet.is_member (OrderedString(“bar”)) (StringSet.add (OrderedString(“foo”)) StringSet.empty)

 

Does F# Compete Against Java or Other Functional Languages

 

Some further tricks with interfaces or a record of functions may solve the problem encountered above, but we continue to get the sense that .Net really just isn’t designed with functional languages in mind.  Here’s another situation where the F# type system doesn’t appear to be up to snuff with a fellow functional friend.  I think most people would agree .Net was created to compete with Java and it shows. 

 

So will this legacy be the stone around F#’s neck that prevents it from ever really being able to compete with Haskell or OCaml?  F# may become a great replacement for C# or Java programs, but will the .Net type system ever evolve to the point where F# can solve problems at the type level?  With the mutable nature of the .Net API’s and the large legacy code base that must be supported, maybe F# would have been better off staying in the lab and forging the way forward for a proper .Net 2.0.

 

Full Source Code

 

#light

 

type comparison = Less | Equal | Greater

 

type ORDERED_TYPE<’a> =

    abstract t : ‘a

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

 

type OrderedString(t : string) =

    interface ORDERED_TYPE<string> with

        member me.t = t

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

       

type Set<’a,’con> when ‘con :> ORDERED_TYPE<’a> () =

    member me.empty : ‘con list = []

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

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

            match s with

            | [] -> [x]

            | hd::tl ->

                match x.compare x.t hd.t 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

    member me.is_member (x : ‘con) (s : ‘con list) =

        let rec is_member (x : ‘con) (s : ‘con list) =

            match s with

            | [] -> false

            | hd::tl ->

                match x.compare x.t hd.t with

                | Equal   -> true     (* x belongs to s *)

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

                | Greater -> is_member x tl

        is_member x s

 

//By applying the Set functor to a structure implementing an ordered type, we obtain set operations for this type

let StringSet = Set<string,OrderedString>()

let result = StringSet.is_member (OrderedString(“bar”)) (StringSet.add (OrderedString(“foo”)) StringSet.empty)

 

printfn “%A” result

System.Console.ReadLine()