Re: [Caml-list] "map"-ing parameterized class types

[Jeremy Yallop <yallop@gmail.com>]

On 19 October 2015 at 17:58, Spiros Eliopoulos <seliopou@gmail.com> wrote:
> I'm trying to create a "container" class[0] that can store a value of type
> 'a, and transform that value to another value of type 'b. I'm trying to do
> this by including a "map" method in the container that applies a function to
> the value and returns a new instance of container with the transformed
> value. Despite the annotations, the types aren't working out as I expected:
>
>   class ['a] container (v:'a) = object
>     method map (f:'a -> 'b) : 'b container = new container (f v)
>   end;;
>   (* class ['a] container : 'a -> object method map : ('a -> 'a) -> 'a
> container end  *)
>
> I gather I'm either doing something wrong, or it's not possible. I suppose
> my question, which one is it?

It's not exactly possible, but there are workarounds.

The reason the types don't work out as you expect is that structural
types (objects, classes, polymorphic variants) in OCaml are required
to be "regular".  A parameterised type t is regular if every
occurrence of t within its own definition is instantiated with the
parameters.  For example, the following type (t1) is regular:

   # type ('a, 'b) t1 = [`A of ('a, 'b) t1];;
   type ('a, 'b) t1 = [ `A of ('a, 'b) t1 ]
     type ('a, 'b) t1 = [`A of ('a, 'b) t1]

but this one (t2) isn't, because the order of parameters is reversed

   # type ('a, 'b) t2 = [`A of ('b, 'a) t2];;
   Characters 5-38:
     type ('a, 'b) t2 = [`A of ('b, 'a) t2];;
          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   Error: In the definition of t2, type ('b, 'a) t2 should be ('a, 'b) t2
     type ('a, 'b) t2 = [`A of ('b, 'a) t2]

and this one (t3) isn't, either, because the parameters are
instantiated with concrete types

   # type ('a, 'b) t3 = [`A of (int, string) t3];;
   Characters 5-43:
     type ('a, 'b) t3 = [`A of (int, string) t3];;
          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   Error: In the definition of t3, type (int, string) t3 should be ('a, 'b) t3

As the output shows, OCaml rejects the non-regular definitions for t2
and t3.  Your example code also attempts to define a non-regular type,
but since the type variable 'b is available for unification, OCaml
doesn't need to reject the definition altogether.  Instead, 'b is
unified with the class parameter 'a to produce a regular type which is
acceptable to OCaml (but which doesn't do what you want).

How might we side-step the regularity constraint?  One approach is to
arrange things so that the recursion passes through a non-structural
type, such as a variant or record.  In an imaginary extension to OCaml
with support for groups of mutually-recursive types and classes we
could write something like this:

   class ['a] container (v:'a) = object
     method map : 'b. ('a -> 'b) -> 'b container_aux =
       fun f -> { container = new container (f v) }
   end
   and 'a container_aux = { container: 'a container }

In today's OCaml we can achieve a similar effect by routing all the
recursive references through a recursive module, albeit at a rather
heavy syntactic cost:

   module rec R:
   sig
     class ['a] container : 'a ->
       object
         method map : 'b. ('a -> 'b) -> 'b R.container_aux
       end
     type 'a container_aux = { container: 'a container }
   end =
   struct
     class ['a] container (v:'a) = object
       method map : 'b. ('a -> 'b) -> 'b R.container_aux =
         fun f -> { R.container = new R.container (f v) }
     end
     type 'a container_aux = { container: 'a container }
   end

which at least achieves the desired effect:

   # let c = new R.container 3;;
   val c : int R.container = <obj>
   # (c#map string_of_int).R.container;;
   - : string R.container = <obj>