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: Brian Hurt <bhurt@s...>
Subject: Re: [Caml-list] Polymorphic recursion


On Tue, 3 Apr 2007, 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);;
> (**)

This way lies GADTs, which are a really neat idea, but even the 
Haskeller's aren't 100% sure how to implement correctly yet.

In any case, there's a fairly simple work around which does work in the 
current type system, which Okasaki describes IIRC.  Basically, you just 
do:

type 'a tuple = Tuple of 'a tuple * 'a tuple | Leaf of 'a;;

type 'a seq = Unit | Set of 'a tuple * 'a seq;;

which is a bit of a pain, but works.

Brian