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=AWL autolearn=disabled version=3.1.3 Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id E95D0BC0A for ; Sun, 24 Dec 2006 04:42:21 +0100 (CET) Received: from ipmail02.adl2.internode.on.net (ipmail02.adl2.internode.on.net [203.16.214.141]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id kBO3gJ1X018040 for ; Sun, 24 Dec 2006 04:42:21 +0100 Received: from ppp14-213.lns2.syd7.internode.on.net (HELO rosella) ([59.167.14.213]) by ipmail02.adl2.internode.on.net with ESMTP; 24 Dec 2006 14:12:18 +1030 X-IronPort-AV: i="4.12,208,1165152600"; d="scan'208"; a="64173423:sNHT122592435" Subject: Re: [Caml-list] map and fold From: skaller To: Andrej.Bauer@andrej.com Cc: caml-list@yquem.inria.fr In-Reply-To: <458DC1BC.5090802@fmf.uni-lj.si> References: <1166786286.6549.24.camel@rosella.wigram> <458DC1BC.5090802@fmf.uni-lj.si> Content-Type: text/plain Date: Sun, 24 Dec 2006 14:42:14 +1100 Message-Id: <1166931734.25424.41.camel@rosella.wigram> Mime-Version: 1.0 X-Mailer: Evolution 2.6.1 Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 458DF71B.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; 0100,:01 andrej:01 node:01 node:01 ocaml:01 ocaml:01 sourceforge:01 wrote:01 wrote:01 caml-list:01 unsafe:01 define:01 data:02 data:02 defined:02 On Sun, 2006-12-24 at 00:54 +0100, Andrej Bauer wrote: > skaller wrote: > Furthermore if t is inductively defined, we can express map in terms of > fold. Examples: > > 1) Lists: > > type 'a list = Nil | Cons of 'a * 'a list > > let map f = fold Nil (fun u _ x -> Cons (f u, x)) > > 2) Trees: > > type 'a tree = Empty | Node of 'a * 'a tree * 'a tree > > let map f = fold Empty (fun u _ _ x y -> Node (f u, x, y)) However in Ocaml at least you cannot actually write a single definition for map in terms of a single fold -- you have to write out fold for each data type, and worse, even given that you still need to write out map for each data type too, following an idiomatic pattern. How could Ocaml be extended to get rid of this unsafe verbosity? Even if the resulting generic operators weren't first class, it would still be useful to define 'map' once and be done with it. -- John Skaller Felix, successor to C++: http://felix.sf.net