From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <loup.vaillant@gmail.com>
X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr
X-Spam-Level: *
X-Spam-Status: No, score=1.0 required=5.0 tests=AWL,SPF_NEUTRAL 
	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 34129BC0A
	for <caml-list@yquem.inria.fr>; Tue,  3 Apr 2007 18:59:51 +0200 (CEST)
Received: from an-out-0708.google.com (an-out-0708.google.com [209.85.132.247])
	by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l33GxneS010804
	for <caml-list@yquem.inria.fr>; Tue, 3 Apr 2007 18:59:50 +0200
Received: by an-out-0708.google.com with SMTP id c24so1762695ana
        for <caml-list@yquem.inria.fr>; Tue, 03 Apr 2007 09:59:49 -0700 (PDT)
DKIM-Signature: a=rsa-sha1; c=relaxed/relaxed;
        d=gmail.com; s=beta;
        h=domainkey-signature:received:received:message-id:date:from:to:subject:mime-version:content-type:content-transfer-encoding:content-disposition;
        b=I+eO65mSTW/QGV2a8dglWB0/qm1ZDOzvG3wRaAO5d86Qqc8EavjwIKZ0YtCBQYOqipB42kFBYF0bY0FJCccyZ04dTwHrWaOdfkp+WIvKooqFRr4pB+EmEx1rD/J/S+8Mo8HnhlQYpvoqltRC/xWTIMxza8Q7+m97qhfCMq21LY4=
DomainKey-Signature: a=rsa-sha1; c=nofws;
        d=gmail.com; s=beta;
        h=received:message-id:date:from:to:subject:mime-version:content-type:content-transfer-encoding:content-disposition;
        b=VXcPzgR8Brjy/Sij+Rg/QMbWsJBuq+U7Fddb3N5RxECZ7gaxqU6gNkxFqDb5mlJvn26UsMNIIbWgFrGs61MjUBi4CgtLtSlN8+/kl2u1lYdmC+s/lasgy2AP3AXHsvdG7o9xf/aw3Ti2348g7fG8NI1mdgXU+ONgvzzbPfm1dt8=
Received: by 10.100.10.20 with SMTP id 20mr4583736anj.1175619588845;
        Tue, 03 Apr 2007 09:59:48 -0700 (PDT)
Received: by 10.100.111.13 with HTTP; Tue, 3 Apr 2007 09:59:43 -0700 (PDT)
Message-ID: <6f9f8f4a0704030959l8ebb155g8532e3ee6d31c66d@mail.gmail.com>
Date: Tue, 3 Apr 2007 18:59:43 +0200
From: "Loup Vaillant" <loup.vaillant@gmail.com>
To: caml-list@yquem.inria.fr
Subject: Polymorphic recursion
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
X-j-chkmail-Score: MSGID : 46128805.000 on discorde : j-chkmail score : X : 0/20 1 0.000 -> 1
X-Miltered: at discorde with ID 46128805.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 recursive:01 polymorphic:01 rec:01 data:02 purely:02 expression:02 structures:02 unit:03 unit:03 

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. Here is the error:
#
| Seq(_, b) -> 1 + 2 * size b;;
This expression (the last 'b') has type seq ('a * 'a) but is here used
with type seq 'a
#

Why?
Can't we design a type system which allow this "size" function?
Can't we implement non uniform recursive function (efficiently, or at all)?.

I suppose the problem is somewhat difficult, but I can't see where.

Regards,
Loup Vaillant