Instanciating functor types with extra parameters

Instanciating functor types with extra parameters

[Arnaud Spiwack]

Hi caml list !

The recent, or rather current, thread on priority queues, raised back an 
issue that've I've been really infuriated with a couple of time the 
past, like, 2 years.

When I have a functor type, like for example (not too innocent I'm afraid) :

module type OrderedType =
  sig
    type t
    val compare : t -> t -> int
  end


Something that naive intuition would allow you to do is something like :

module GenOrder : OrderedType =
  struct
    type t = 'a
    let compare = compare
  end


Though this is more or less nonsense. And is not currently possible 
under OCaml type system.

My point is that I know absolutely no way of doing such a thing. Hence I 
can't make a set with total or partial genericity. If I want to add type 
parameters I have to rewrite the *whole* set library. Actually... I've 
got to copy past it, and replace all occurences of    t   with an 'a t 
for instance. Or ('a,'b) t if I have two arguments. I really had to do 
that once, and almost a couple of other time. That's why it infuriates 
me as I said earlier.

The whole issue is that it totaly breaks the purpose of functors to have 
to recast it for a very small type variation.

Thus I'm raising the question : is there a good reason (I mean a good 
reason from the user point of view here, I kinda understand it may make 
things much more complicated). An other question would be : is there a 
way to work around this issue ? Yet another question would be : should 
there be a separated syntax to mean that the type can have arbitrary 
arguments encapsulated ?


PS : I'm aware that there is (several) available implementation of 
unfunctorized Set and Map, the questions are about the more general case 
though. I very often give up the idea of writing something in a 
functorized style, because it's too fragile, which is a bit paradoxal to me.





Arnaud Spiwack

Re: [Caml-list] Instanciating functor types with extra parameters

[Denis Bueno]

On 8/4/07, Arnaud Spiwack <aspiwack@lix.polytechnique.fr> wrote:
> When I have a functor type, like for example (not too innocent I'm afraid) :
>
> module type OrderedType =
>   sig
>     type t
>     val compare : t -> t -> int
>   end
>
>
> Something that naive intuition would allow you to do is something like :
>
> module GenOrder : OrderedType =
>   struct
>     type t = 'a
>     let compare = compare
>   end
>
[... snip ...]
> My point is that I know absolutely no way of doing such a thing. Hence I
> can't make a set with total or partial genericity. If I want to add type
> parameters I have to rewrite the *whole* set library. Actually... I've
> got to copy past it, and replace all occurences of    t   with an 'a t
> for instance. Or ('a,'b) t if I have two arguments. I really had to do
> that once, and almost a couple of other time. That's why it infuriates
> me as I said earlier.

You can do something slightly less general that certainly doesn't
require rewriting the whole set library:  One comparator definition
per set you'd like to create.

module StringOrder : OrderedType = struct
  type t = string
  (* just to be clear about which compare to capture)
  let compare = Pervasives.compare
end

module IntOrder : OrderedType = struct
  type t = int
  let compare = Pervasives.compare
end

... and so on.  You can use these to create functors, of course:

module StringSet = Set.Make (StringOrder)
module IntSet = Set.Make (IntSet)

I think you'll find, though, as time goes on that you'll use special
comparators: that is, not just generic string comparison, but some
other total order on strings.  And you'll want to name
MySpecialStringCompare accordnigly.

module CaseInsensitiveStrOrder : OrderedType = struct
  type t = string
  let compare x y = Pervasives.compare (downcase x) (downcase y)
end
module CaseInsensitiveSet = Set.Make (CaseInsensitiveStrOrder)

                      Denis
--
"Program testing can be used to show the presence of bugs, but never to show
their absence." -- Edsger Dijkstra

Re: [Caml-list] Instanciating functor types with extra parameters

[rossberg]

From: "Arnaud Spiwack" <aspiwack@lix.polytechnique.fr>
>
> When I have a functor type, like for example (not too innocent
> I'm afraid) :
>
> module type OrderedType =
>   sig
>     type t
>     val compare : t -> t -> int
>   end
>
> Something that naive intuition would allow you to do is something like :
>
> module GenOrder : OrderedType =
>   struct
>     type t = 'a
>     let compare = compare
>   end
>
> Though this is more or less nonsense. And is not currently possible
> under OCaml type system.
>
> My point is that I know absolutely no way of doing such a thing.

If you have control over the functor type then you can do this:

  module type OrderedPolyType =
  sig
     type 'a t
     val compare : 'a t -> 'a t -> int
  end

  module GenOrder : OrdererPolyType =
  struct
     type 'a t = 'a
     let compare = compare
  end

  module InvIntOrder : OrdererPolyType =
  struct
     type 'a t = int
     let compare x y = compare y x
  end

Not a general solution, but one that's often good enough.

- Andreas

Re: [Caml-list] Instanciating functor types with extra parameters

[Oliver Bandel]

Hello,


Zitat von Arnaud Spiwack <aspiwack@lix.polytechnique.fr>:

> Hi caml list !
>
> The recent, or rather current, thread on priority queues, raised back an
> issue that've I've been really infuriated with a couple of time the
> past, like, 2 years.
>
> When I have a functor type, like for example (not too innocent I'm afraid) :
>
> module type OrderedType =
>   sig
>     type t
>     val compare : t -> t -> int
>   end
>
>
> Something that naive intuition would allow you to do is something like :
>
> module GenOrder : OrderedType =
>   struct
>     type t = 'a
>     let compare = compare
>   end
[...]

I don't know if this is flexible/generic enough for you,
but at least for me it seems to be what you are looking for,
and it compiles:


===================================================
oliver@siouxsie2:~$ cat cmp.ml
module type OT2 =
  sig
    type 'a t
   val compare: 'a t -> 'a t -> int
  end


module GenOrder : OT2 =
  struct
    type 'a t = 'a
  let compare = compare
  end
oliver@siouxsie2:~$ ocamlc -i cmp.ml
module type OT2 = sig type 'a t val compare : 'a t -> 'a t -> int end
module GenOrder : OT2
oliver@siouxsie2:~$
===================================================


Ciao,
   Oliver

Re: [Caml-list] Instanciating functor types with extra parameters

[Mike Furr]

Arnaud Spiwack wrote:

> Something that naive intuition would allow you to do is something like :
> 
> module GenOrder : OrderedType =
>  struct
>    type t = 'a
>    let compare = compare
>  end

I had a similar problem while developing my OCaml-Reins data structure 
library (first release will be "real-soon-now").  Stephen Weeks offered 
the following solution:  the main idea is that you build a generic core 
module that is parameterized by the maximum number of type variables 
desired.  So for a set, you might define

module BaseSet = struct
   type 'a elt_
   type 'a set_ = Empty | Node of 'a set_ * 'a elt_ * 'a set_
   val empty : 'a set_
   val add : 'a elt_ -> 'a set_ -> 'a set_
   ...
   val compare_ : ('a elt_ -> 'a elt_ -> int) ->
      'a set_ -> 'a set_ -> int
   ...
end

Then, you can create a polymorphic version
module PolySet = struct
   include BaseSet
   type 'a t = 'a set_
   type 'a elt = 'a
   let compare = compare_ Pervasives.compare
   ...
end

or a monomorphic version:
module MonoSet(C : OrderedType) = struct
   type elt = C.t
   type 'a elt_ = elt
   type t = C.t set_
   let compare = compare_ C.compare
end

Thus allowing you to share all of the underlying code with only a little 
boilerplate.

Cheers,
-mike