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 discorde.inria.fr (discorde.inria.fr [192.93.2.38]) by yquem.inria.fr (Postfix) with ESMTP id C62C3BC0A for ; Sun, 24 Dec 2006 04:26:46 +0100 (CET) Received: from ipmail02.adl2.internode.on.net (ipmail02.adl2.internode.on.net [203.16.214.141]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id kBO3Qin9025233 for ; Sun, 24 Dec 2006 04:26:45 +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 13:56:40 +1030 X-IronPort-AV: i="4.12,208,1165152600"; d="scan'208"; a="64170981:sNHT23416827" 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:26:39 +1100 Message-Id: <1166930799.25424.32.camel@rosella.wigram> Mime-Version: 1.0 X-Mailer: Evolution 2.6.1 Content-Transfer-Encoding: 7bit X-Miltered: at discorde with ID 458DF374.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; 0100,:01 andrej:01 overloading:01 overloading:01 statically:01 ocaml:01 ocaml:01 compiler:01 compiler:01 generalise:01 camlp:01 typeclass:01 bool:01 typeclass:01 bool:01 On Sun, 2006-12-24 at 00:54 +0100, Andrej Bauer wrote: [] > I am not quite sure how skaller intended map to work Neither am I. My aim here is roughly: in Felix I have overloading, typeclasses and I also have tuples. Overloading provides 'generic' operations on primitive types in an ad hoc manner. Typeclasses provide 'generic' operations on primitive types in a uniform manner. Tuples are heterogenous lists with statically known types, more generally we'd have algebraic types but tuples will do for a start. There are many things I'd like to do with tuples. Too many. The operations are generic (polyadic) not merely polymorphic as for lists. In fact there is a correspondence: the Ocaml representation of a tuple is a list of terms, so run time generic operations are Ocaml time list polymorphic: so in the compiler, implementing generic operations is easy -- but end users can't do it, and 'easy' isn't the same as wanting to provide hundreds of compiler supported intrinsics. What I need to do is find some primitive, compiler supported operations, which can be *combined* in user library code to provide the others. Well, I obviously need things like fold zip (compose) split map and a host of other generic operations. In fact so far I have implemented memcount e // counts members _tuple_fold f i c // fold generic f _tuple_trans e // transpose tuple of tuples // subsumes zip and split but I have no idea (a) whether this set of operations is sufficient (b) how to combine them (c) how to generalise to all algebraic types so I'm trying to get a more theoretical picture of how these things relate. I have a picture that if you have fold, map comes for free, but just folding over the appropriate constructor. But really the question is deeper: I'm really asking how to design a programming language that supports generic programming, or more precisely, how to make practical progress towards that. I can do slightly more to Felix than Ocaml, since I can intervene in any part of the compiler. The tuple fold depends on type information, so it couldn't be implemented in Ocaml using camlp4. The users have an immediate need: right now we have typeclass Eq[t] { virtual fun eq: t * t -> bool; } instance Eq[int] { .. } instance Eq[double] { .. } ... so we have generic equality for primitives. There should be no need to manually instantiate the typeclass for each tuple of interest though: one definition should be enough to cover them all: fun eqa[t with Eq[t]]: bool * (t * t) -> bool = | ?result, (?a, ?b) => result and a == b; val x1 = ((1,1),(2.0,2.0),("3","3")); print$ _tuple_fold eqa true x1; endl; actually works now. Throw in transpose function to get the arguments in the right form, cover sum types as well, and we have second class generic equality operator: this is better than Ocaml's polymorphic equality in the sense that it also works with abstract types, and weaker in the sense it is only second class (compile time only, no closures). This is pretty hot stuff for a scripting language: much safer than Python etc. -- John Skaller Felix, successor to C++: http://felix.sf.net