Re: [Caml-list] Manipulating Modules Modularly

[Leo White <lpw25@cam.ac.uk>]

> module type M = sig  type t  val u:t  val p:t->t->t  end
>
> And a functor:
>
> module type ME = sig  type t  val ps:t list -> t  end
> module ME (M:M) : ME with type t := M.t
>
> All good and well. I now want to reuse my functor for list, which are a monoid.
> What I really want is a module
>
> module LE : ME with type t := 'a list
>
> So here's my question: how do you/would you solve this problem. If the solution is compatible with 3.12, it's a plus.
>

Moving quantifiers around is awkward in the module system, but is also
not safe in general. We can clearly illustrate this by reencoding your
example without modules:

First we define `m` as a record type and create one for lists:

    # type 'a m = { u : 'a; p : 'a -> 'a -> 'a };;
    type 'a m = { u : 'a; p : 'a -> 'a -> 'a; }

    # let list = { u = []; p = (@) };;
    val list : 'a list m = {u = []; p = <fun>}

Then we define the `me` as another record type and create a simple
function for creating them from monoids:

    # type 'a me = { ps : 'a list -> 'a };;
    type 'a me = { ps : 'a list -> 'a; }

    # let me (m : 'a m) = { ps = List.fold_left m.p m.u };;
    val me : 'a m -> 'a me = <fun>

Now we can apply the `me` function to the `list` monoid:

    # let mel = me list;;
    val mel : '_a list me = {ps = <fun>}

But what we get is only weakly polymophic because of the value
restriction. This hints at the unsafety of what we are trying to
do. Whilst the above definition of `me` happens to be safe, consider the
following version:

    # let me (m : 'a m) =
        let r = ref m.u in
        let ps = function
        | [] -> !r
        | x :: xs ->
            let old = !r in
              r := x;
              List.fold_left m.p m.u (old :: xs)
        in
          {ps};;
                      val me : 'a m -> 'a me = <fun>

    # let mel = me list;;
    val mel : '_a list me = {ps = <fun>}

Here we use a reference to preserve elements of the monoid across
different calls to `ps`. If this were allowed to be polymorphic we could
end up mixing elements of different list types together. For example, if
we use `Obj.magic` to pretend that `mel` is polymorphic we can quickly
get a segfault:

    # let meli : int list me = Obj.magic mel;;
    val meli : int list me = {ps = <fun>}

    # let melf : float list me = Obj.magic mel;;
    val melf : float list me = {ps = <fun>}

    # meli.ps [[1; 2; 3]; [2; 3; 4]];;
    - : int list = [2; 3; 4]

    # melf.ps [[1.0; 2.0; 3.0]; [2.0; 3.0; 4.0]];;

    Process ocaml-toplevel segmentation fault

So hopefully, this illustrates why you cannot easily get what you want
in a language with side-effects. Since what you are fundementally trying
to do is safe, I suspect that a language with good support for
higher-rank polymorphism, higher-kinded polymorphism, and kind
polymorphism might be apply to encode it safely even in the presence of
side-effects, but the encoding is likely to be a bit involved.

Regards,

Leo