Version française
Home     About     Download     Resources     Contact us    
Browse thread
Polymorphic recursion
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Jeremy Yallop <jeremy.yallop@e...>
Subject: Re: [Caml-list] Polymorphic recursion
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.