From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id BA388BBC4 for ; Sat, 21 Jan 2006 19:35:10 +0100 (CET) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id k0LIZAOI017254 for ; Sat, 21 Jan 2006 19:35:10 +0100 Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id TAA18648 for ; Sat, 21 Jan 2006 19:35:09 +0100 (MET) Received: from haka.fmf.uni-lj.si (haka.fmf.uni-lj.si [193.2.67.18]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id k0LIZ8O5001195 (version=TLSv1/SSLv3 cipher=AES256-SHA bits=256 verify=NO) for ; Sat, 21 Jan 2006 19:35:09 +0100 Received: from bsn-77-186-71.dsl.siol.net ([193.77.186.71] helo=[192.168.1.101]) by haka.fmf.uni-lj.si with esmtpa (Exim 4.50) id 1F0NZm-0005uK-Ea; Sat, 21 Jan 2006 19:35:07 +0100 Message-ID: <43D27F18.9030102@andrej.com> Date: Sat, 21 Jan 2006 19:36:08 +0100 From: Andrej Bauer Reply-To: Andrej.Bauer@andrej.com User-Agent: Debian Thunderbird 1.0.7 (X11/20051017) X-Accept-Language: en-us, en MIME-Version: 1.0 To: skaller , Caml list References: <43C51C33.2000206@andrej.com> <1137031853.3681.138.camel@rosella> <43C661AF.2080404@andrej.com> <1137102848.3681.268.camel@rosella> <1137163342.3681.533.camel@rosella> <1137594157.8943.106.camel@rosella> <20060120004948.GA2490@coruscant.stwing.upenn.edu> <43D0B413.1060806@andrej.com> <20060120185911.GA22920@coruscant.stwing.upenn.edu> <1137790790.15137.39.camel@rosella> In-Reply-To: <1137790790.15137.39.camel@rosella> Content-Type: text/plain; charset=ISO-8859-2 Content-Transfer-Encoding: 7bit X-SA-Exim-Connect-IP: 193.77.186.71 X-SA-Exim-Mail-From: Andrej.Bauer@andrej.com Subject: Re: [Caml-list] Coinductive semantics X-SA-Exim-Version: 4.2 (built Thu, 03 Mar 2005 10:44:12 +0100) X-SA-Exim-Scanned: Yes (on haka.fmf.uni-lj.si) X-Miltered: at nez-perce with ID 43D27EDE.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at concorde with ID 43D27EDC.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; andrej:01 andrej:01 caml-list:01 coinductive:01 semantics:01 algebra:01 denotes:01 manifests:01 rec:01 recursion:01 rec:01 variants:01 lazy:01 wrote:01 expression:01 X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.3 skaller wrote: > How would you decode an Andrej sum without a conditional > control transfer? The control is a consequence of the fact that natural numbers are an inital algebra (I am pretending that "int" denotes natural numbers). In a programming language the initiality of natural numbers manifests itself as an operation "rec" with which we may define function by simple recursion, i.e, given x : 'a and f : int -> 'a, the expression "rec x f" has they type int -> 'a and satisfies: rec x f 0 = x rec x f (n+1) = f (rec x f n) Since I suggested that we use 0 and 1 as tags for variants, we could define a deconstructor "match" for sums (i.e. the conditional control transfer for the sum type) using rec as follows: match g h (t, x, y) = rec (g x) (fun _ -> h y) t The above match has the property that match g h (0, x, y) = g x match g h (1, x, y) = h y There are a few details about eager/lazy evaluation of rec which I will let you sort out (in case rec is "too eager", we use thunking). Andrej