From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id OAA28334; Mon, 27 Sep 2004 14:14:19 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f 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 OAA27716 for ; Mon, 27 Sep 2004 14:14:18 +0200 (MET DST) Received: from smtp3.adl2.internode.on.net (smtp3.adl2.internode.on.net [203.16.214.203]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id i8RCEFW2030169 for ; Mon, 27 Sep 2004 14:14:17 +0200 Received: from [192.168.1.200] (ppp202-133.lns1.syd3.internode.on.net [203.122.202.133]) by smtp3.adl2.internode.on.net (8.12.9/8.12.9) with ESMTP id i8RCE9OU048011; Mon, 27 Sep 2004 21:44:10 +0930 (CST) Subject: Re: [Caml-list] C++ STL and template features compared with OCaml parametric polymorphism and OO features From: skaller Reply-To: skaller@users.sourceforge.net To: Radu Grigore Cc: Jon Harrop , caml-list In-Reply-To: <7f8e92aa0409270350ce0eed2@mail.gmail.com> References: <20040925225246.48566.qmail@web53010.mail.yahoo.com> <200409261951.52609.jon@jdh30.plus.com> <7f8e92aa04092613141479823e@mail.gmail.com> <200409270259.43863.jon@jdh30.plus.com> <7f8e92aa0409270350ce0eed2@mail.gmail.com> Content-Type: text/plain Message-Id: <1096287248.28613.606.camel@pelican.wigram> Mime-Version: 1.0 X-Mailer: Ximian Evolution 1.2.2 (1.2.2-4) Date: 27 Sep 2004 22:14:09 +1000 Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 41580417.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 sourceforge:01 2004:99 2004:99 generic:01 mapmap:99 mapmap:99 generic:01 functorial:01 int':01 float':01 haskell:01 generalised:01 functor:01 jacques:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Mon, 2004-09-27 at 20:50, Radu Grigore wrote: > On Mon, 27 Sep 2004 02:59:43 +0100, Jon Harrop wrote: > > > What is the difference between a generic function and a function which > > dispatches to appropriate specialised functions? > > For the client of the function there is no difference. .. unless you try to apply a function to an argument for which there is no specialisation.. > The good news is that the > OCaml library gives you those specialized functions (fold) for common > data structures like List and Array. The bad news is that you are on > your own if you define new data structures that can be viewed as > sequences. Its much worse than that. Consider map. You have List.map and Array.map. Now consider mapmap: let mapmap F g f x = F.map g (F.map f x) This is just two maps in a row. Except you have to write: let List.mapmap g f x = List.map g (List.map f x) let Array.mapmap g f x = Array.map g (Array.map f x) So you have to duplicate not just the basic algorithms, but also every generic algorithm defined compositinally. The lack of functorial polymorphism propagates. This is the same as needing 'list_of_int' and 'list_of_float' in C because there is no polymorphism, only one level up. Haskell partially solves this problem with type classes. > The meaning of "fold" is "apply this function repeatedly for each > element of the data-structure and accumulate the result". I'd like to > be able to write this in code _once_ for every data-structure that can > be seen as a sequence (i.e. a set of totaly ordered elements). A generalised fold doesn't require either a sequence or any ordering -- it just applies to all the elements of a container in any order (so it works for a tree too). The result isn't deterministic unless the accumulation function 'add' is order independent ie: add (add acc x) y = add (add acc y) x > However, John said that talking about "sequences" means that we are > actually artificially limiting a more general concept: shape. But I > don't quite understand this idea fully. Me either but -- clearly you need that concept to deal with multi-dimensional arrays and trees, neither of which are sequences. The basic idea is a data type can be broken up into two parts -- the shape and the value. Shape is a functor, value is a type. As Jacques said, using the type variable in an ML type annotation: type 'a F = ... to distinguish the value type 'a and shape F is artificial. -- John Skaller, mailto:skaller@users.sf.net voice: 061-2-9660-0850, snail: PO BOX 401 Glebe NSW 2037 Australia Checkout the Felix programming language http://felix.sf.net ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners