Thank, Jeremy, for the great explanation and possible work around.
Unfortunately for me, the workaround won't be possible to use for the
js_of_ocaml use case I have in mind. At least not without sprinkling
Obj.magic everywhere, which is what I'm trying to avoid.

Based on your workaround, I thought I might be able to create my own
workaround with code that looked something like this:

  module rec R : sig
    class type ['a] container1 = object
      method map : ('a -> 'b) -> 'b R.container2
    end
    class type ['a] container2 = object
      method op : 'a R.container1
    end
  end = struct
    ...
  end

But of course the type system complained that:

  Error: In the definition of R.container2, type
       'b R.container1
       should be
       'a R.container1

I thought this might be for a different than the one you mentioned, but
upon further reflection and a single unrolling of the types, it seems to be
the regular type constraint that's causing this error as well.

Well, back to drawing board. Thanks again.

On Mon, Oct 19, 2015 at 2:14 PM, Jeremy Yallop <yallop@gmail.com> wrote:

> 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>
>