This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

Polymorphic recursion
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2007-04-04 (05:27) From: Alain Frisch Subject: Re: [Caml-list] Polymorphic recursion
```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

```