Browse thread
Polymorphic recursion
[
Home
]
[ Index:
by date
|
by threads
]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: | 2007-04-04 (05:27) |
From: | Alain Frisch <Alain.Frisch@i...> |
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