From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <yallop@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=2.8 required=5.0 tests=DNS_FROM_RFC_POST,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 mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82])
	by yquem.inria.fr (Postfix) with ESMTP id A29D4BC37
	for <caml-list@yquem.inria.fr>; Mon, 28 Sep 2009 22:56:26 +0200 (CEST)
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AmsBAAXAwErRVdvfkGdsb2JhbACRUIh5PwEBAQEJCQwHEwOrdoE0jkUBAwIFhBkF
X-IronPort-AV: E=Sophos;i="4.44,468,1249250400"; 
   d="scan'208";a="37030514"
Received: from mail-ew0-f223.google.com ([209.85.219.223])
  by mail1-smtp-roc.national.inria.fr with ESMTP; 28 Sep 2009 22:56:26 +0200
Received: by ewy23 with SMTP id 23so4685209ewy.26
        for <caml-list@inria.fr>; Mon, 28 Sep 2009 13:56:26 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=gamma;
        h=domainkey-signature:received:received:message-id:date:from
         :user-agent:mime-version:to:subject:content-type
         :content-transfer-encoding;
        bh=9NLDMqQLDflDrr8c1UrFBIADcu0o93/D5yrQSvCklmg=;
        b=Q35bU5JjEkyiet+bMZh/IETbxwB8L1qrcr6Kwdr42T5EE67WuDc0JkkNDdzKOzqUMP
         GUQchDkwB1N2/gnqyl9oieijcowOxv35lPgDtGyTqjQgwo1XRftJMlx/o/Adim0h6qt6
         sZUKDWFjPsiFMvscF8zgw7CuTy0fCGJUwNF3M=
DomainKey-Signature: a=rsa-sha1; c=nofws;
        d=gmail.com; s=gamma;
        h=message-id:date:from:user-agent:mime-version:to:subject
         :content-type:content-transfer-encoding;
        b=SSt5Dk7Cu5qcUopjVtaZ8Wei2RBWdoKd6eBI1joWBObHBK/yyIVElI+k3jXoEeHyVx
         Rzn5TbaUhn/CpKlpjGUe37KWvNQDix8CECPkP9h//Enno9xOE/XarmeKUA1E709UOR+J
         8F7Y/rCIbXy7dm0jRzTjtjNvsVxiUejHvH33c=
Received: by 10.211.159.15 with SMTP id l15mr4117790ebo.96.1254171386253;
        Mon, 28 Sep 2009 13:56:26 -0700 (PDT)
Received: from ?192.168.1.64? (host86-161-147-82.range86-161.btcentralplus.com [86.161.147.82])
        by mx.google.com with ESMTPS id 5sm249808eyh.40.2009.09.28.13.56.25
        (version=TLSv1/SSLv3 cipher=RC4-MD5);
        Mon, 28 Sep 2009 13:56:25 -0700 (PDT)
Message-ID: <4AC12336.1040703@gmail.com>
Date: Mon, 28 Sep 2009 21:57:26 +0100
From: Jeremy Yallop <yallop@gmail.com>
User-Agent: Mozilla-Thunderbird 2.0.0.22 (X11/20090701)
MIME-Version: 1.0
To: caml-list@inria.fr
Subject: ANN: pa_polyrec: syntax for polymorphic recursion
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-Spam: no; 0.00; syntax:01 recursion:01 syntax:01 recursion:01 ocaml:01 ocaml:01 quantified:01 recursive:01 okasaki's:01 notation:01 datatype:01 ross:98 polymorphic:01 polymorphic:01 rec:01 

I'm pleased to announce the initial release of pa_polyrec, a syntax extension 
for polymorphic recursion in OCaml.

    https://forge.ocamlcore.org/projects/pa-polyrec/

There are several methods for encoding polymorphic-recursive functions in OCaml; 
this extension allows them to be written directly, using a natural syntax.  For 
example, given the following type of perfectly-balanced trees we might wish to 
write a function for summing the leaves.

   type 'a perfect = Zero of 'a | Succ of ('a * 'a) perfect

In standard OCaml such a function can be written as follows:

   let sump f =
     (object (o)
         method sump : 'a. ('a -> int) -> 'a perfect -> int =
           fun f -> function
            | Zero x -> f x
            | Succ x -> o#sump (fun (a, b) -> f a + f b) x
      end)#sump f

   let sum_perfect = sump id

Using pa_polyrec one can write the function in the following less obfuscated style:

   let rec sump : 'a. ('a -> int) -> 'a perfect -> int =
     fun f -> function
      | Zero x -> f x
      | Succ x -> sump (fun (a, b) -> f a + f b) x

   let sum_perfect = sump id

Note that the type variable 'a in the type of the function is quantified: this 
is what differentiates polymorphic-recursive functions from standard OCaml 
recursive function definitions.

More complex usage is supported, including mutual recursion.  A number of 
examples are included in the distribution, including several modules from Chris 
Okasaki's thesis "Purely Functional Data Structures" and code from Richard Bird 
and Ross Paterson's paper "de Bruijn notation as a nested datatype".