From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <jeremy.yallop@ed.ac.uk>
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=AWL 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 D5BA8BC0A
	for <caml-list@yquem.inria.fr>; Tue,  3 Apr 2007 19:21:12 +0200 (CEST)
Received: from mcr-smtp-001.bulldogdsl.com (smtp.bulldogdsl.com [212.158.248.7])
	by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l33HLCSi014889
	for <caml-list@yquem.inria.fr>; Tue, 3 Apr 2007 19:21:12 +0200
Received: by mcr-smtp-001.bulldogdsl.com (Postfix, from userid 1005)
	id 352A070C5FC; Tue,  3 Apr 2007 18:21:09 +0100 (BST)
Received: from [192.168.123.191] (host-84-9-235-163.bulldogdsl.com [84.9.235.163])
	by mcr-smtp-001.bulldogdsl.com (Postfix) with ESMTP id DECC670C304
	for <caml-list@yquem.inria.fr>; Tue,  3 Apr 2007 18:21:07 +0100 (BST)
Message-ID: <46128CEE.2090704@ed.ac.uk>
Date: Tue, 03 Apr 2007 18:20:46 +0100
From: Jeremy Yallop <jeremy.yallop@ed.ac.uk>
User-Agent: Icedove 1.5.0.10 (X11/20070307)
MIME-Version: 1.0
To: caml-list@yquem.inria.fr
Subject: Re: [Caml-list] Polymorphic recursion
References: <6f9f8f4a0704030959l8ebb155g8532e3ee6d31c66d@mail.gmail.com>
In-Reply-To: <6f9f8f4a0704030959l8ebb155g8532e3ee6d31c66d@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-Miltered: at discorde with ID 46128D08.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 sig:01 val:01 struct:01 polymorphic:01 wrote:01 rec:01 rec:01 caml-list:01 

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.