From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from discorde.inria.fr (discorde.inria.fr [192.93.2.38]) by yquem.inria.fr (Postfix) with ESMTP id 2E29FBC0A for ; Thu, 5 Apr 2007 01:36:37 +0200 (CEST) Received: from bsd4.nyct.net (mail-out4.nyct.net [216.139.141.4]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l34NaZQu024948 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Thu, 5 Apr 2007 01:36:36 +0200 Received: from [192.168.42.2] ([216.139.135.144]) by bsd4.nyct.net (8.13.4/8.13.4) with ESMTP id l34NaXEG051057; Wed, 4 Apr 2007 19:36:34 -0400 (EDT) (envelope-from bhurt@spnz.org) Date: Wed, 4 Apr 2007 19:36:52 -0400 (EDT) From: Brian Hurt X-X-Sender: bhurt@localhost To: Loup Vaillant Cc: caml-list@yquem.inria.fr Subject: Re: [Caml-list] Polymorphic recursion In-Reply-To: <6f9f8f4a0704030959l8ebb155g8532e3ee6d31c66d@mail.gmail.com> Message-ID: References: <6f9f8f4a0704030959l8ebb155g8532e3ee6d31c66d@mail.gmail.com> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed X-Miltered: at discorde with ID 46143683.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; recursion:01 okasaki's:01 functionnal:01 ocaml:01 seq:01 seq:01 okasaki:01 iirc:01 2007,:98 polymorphic:01 wrote:01 caml-list:01 data:02 tuple:02 tuple:02 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