Re: [Caml-list] Polymorphic recursion

[Jeremy Yallop <jeremy.yallop@ed.ac.uk>]

Loup Vaillant wrote:
> I was reading Okasaki's book, "Purely functionnal data structures",
> and discovered that ML (and Ocaml) doesn't support non uniforms
> function definitions.
> 
> So, even if:
> 
> (**)
> type 'a seq = Unit | Seq of ('a * ('a * 'a)seq);;
> (**)
> 
> is correct,
> 
> (**)
> let rec size = fun
>   | Unit -> 0
>   | Seq(_, b) -> 1 + 2 * size b;;
> (**)
> 
> is not.

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

Hope this helps,

Jeremy.