Re: [Caml-list] Polymorphic recursion

[Alain Frisch <Alain.Frisch@inria.fr>]

Jeremy Yallop wrote:
> Right.  You can write polymorphic-recursive functions if you wrap them
> in recursive modules, though:
> 
>   module rec Size : sig val size : 'a seq -> int end = struct
>     let rec size = function
>       | Unit -> 0
>       | Seq (_, b) -> 1 + 2 * Size.size b
>   end

Note that you don't even need the "rec" in this example, and that the
same idiom would support mutually recursive functions. To make an
automatic translation simpler, you can simply "open Size" at the
beginning of the structure to avoid rewriting self-references in the
function's body. To support local definitions, you can of course rely on
local modules:

let rec f : 'a 'b. t = E1 in E2

becomes:

let module X = struct
  module rec Y : sig val f : t end = struct
    open Y
    let f = E1
  end
  open Y
  let v = E2
end in
X.v

However, this encoding has an important drawback: you cannot use type
variables currently in scope in t, E1, E2 (as a consequence, we don't
need to explicitly quantify over variables in the function prototype,
the encoding forces all the variables in the function's type to be
universally quantified). By changing the encoding, you can allow
references to those type variables in E2:

let f =
 let module X = struct
   module rec Y : sig val f : t end = struct
     open Y
     let f = E1
   end
 end in
 X.Y.f
in
E2


-- Alain