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 PAA30584; Mon, 27 Sep 2004 15:16:16 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id PAA30453 for ; Mon, 27 Sep 2004 15:16:15 +0200 (MET DST) Received: from ptb-relay03.plus.net (ptb-relay03.plus.net [212.159.14.214]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id i8RDGE6E008094 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Mon, 27 Sep 2004 15:16:14 +0200 Received: from [80.229.56.224] (helo=chetara) by ptb-relay03.plus.net with esmtp (Exim) id 1CBvMT-000BZn-Hy for caml-list@inria.fr; Mon, 27 Sep 2004 13:16:13 +0000 From: Jon Harrop To: caml-list Subject: Re: [Caml-list] C++ STL and template features compared with OCaml parametric polymorphism and OO features Date: Mon, 27 Sep 2004 14:11:30 +0100 User-Agent: KMail/1.6.2 References: <20040925225246.48566.qmail@web53010.mail.yahoo.com> <200409270259.43863.jon@jdh30.plus.com> <7f8e92aa0409270350ce0eed2@mail.gmail.com> In-Reply-To: <7f8e92aa0409270350ce0eed2@mail.gmail.com> MIME-Version: 1.0 Content-Disposition: inline Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit Message-Id: <200409271411.30384.jon@jdh30.plus.com> X-Miltered: at nez-perce with ID 4158129E.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 2004:99 2004:99 generic:01 iterator:01 iterator:01 splay:01 equivalently:01 extensively:01 stepanov:01 reinvented:01 mapmap:99 mapmap:99 generic:01 generalised:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Monday 27 September 2004 11: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. > > For the writter of the function there is a big difference, especially > if it has to write the specialized versions. The equivalent to the writer of fold is the writer of an iterator. You have to write specialized versions for each type of iterator just as you would have to write your own fold. Check out vector::iterator and set::iterator. Consider writing a splay tree in C++ using iterators. You would have to rewrite most of what's in the STL for "set" by hand... > 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. Right, like Set, which has a completely different fold to array and list. Equivalently, the implementations for vector, list and set iterators in C++ will be completely different. I don't think iterators buy you anything. > 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). Why not write fold once "for every data structure..." seeing as they have next to nothing in common? > You can > do this with iterators. As the article cited by Vasili shows there is > an analogue of iterators in functional languages. Presumably the benefit of iterators in a functional language would be bidirectional traversal of a sequence container. But iterators fall apart on general trees, matrices and anything which isn't just a sequence of elements. In many such cases you want mapi... > So we are not really talking here about > differences between OCaml and C++; we are talking about library > design. I think we are, because I think iterators are only really useful in an imperative setting. Hence C++ programmers use them extensively but OCaml programmers do not. Folds are simply not feasible in C++. I'm sure Stepanov would have reinvented them if they had been... ;-) On Monday 27 September 2004 13:14, skaller wrote: > 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) No, you don't have to write that. You can write a generic function which accepts a map as an argument: let map_2 map f g c = map f (map g c) or better still, the deforested: let map_2 map f g c = map (fun x -> f (g x)) c You can't write map_n without some jiggery pokery though. > ... > A generalised fold doesn't require either a sequence or any > ordering Folds with a particular direction are much more useful, IMHO. Hence the folds in the core library are left or right for arrays and lists and up for sets and maps. > -- it just applies to all the elements of a container > in any order (so it works for a tree too). A lexicographically ordered traversal can be defined for any data structure in OCaml - that's how hash and compare work. Cheers, Jon. ------------------- 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