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 SAA07815; Mon, 27 Sep 2004 18:58:41 +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 SAA08936 for ; Mon, 27 Sep 2004 18:58:40 +0200 (MET DST) Received: from ptb-relay02.plus.net (ptb-relay02.plus.net [212.159.14.213]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id i8RGwdEU008729 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Mon, 27 Sep 2004 18:58:39 +0200 Received: from [80.229.56.224] (helo=chetara) by ptb-relay02.plus.net with esmtp (Exim) id 1CBypj-000GY9-55 for caml-list@inria.fr; Mon, 27 Sep 2004 16:58:39 +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 17:54:35 +0100 User-Agent: KMail/1.6.2 References: <20040925225246.48566.qmail@web53010.mail.yahoo.com> <200409271411.30384.jon@jdh30.plus.com> <7f8e92aa04092706317dae6556@mail.gmail.com> In-Reply-To: <7f8e92aa04092706317dae6556@mail.gmail.com> MIME-Version: 1.0 Content-Disposition: inline Message-Id: <200409271754.36040.jon@jdh30.plus.com> Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 415846BF.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 generic:01 splay:01 complexities:01 terrible:01 splay:01 equivalently:01 accu:01 accu:01 commonality:01 commonality:01 templated:01 iterator:01 implemented:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Monday 27 September 2004 14:31, Radu Grigore wrote: > The > difference is that after you write the iterators code for a new > sequence-like data structure all the "generic" functions, not only > fold but also map and others, will automagically work on them. I think this is the core of what we disagree on. I believe you'll be implementing a new data structure (e.g. splay trees) because you want to use different algorithms under the hood so that you get different asymptotic complexities for different operations. Therefore, the "automagically" generated ones will be useless because they'll have terrible performance - they'll need replacing. The different functions (e.g. insert, find for a splay tree) require completely different algorithms so iterators are useless. For example, "find" on a "set" in the STL does not use iterators. Equivalently, the HOF fold is useless, e.g. "find" in "Set" in OCaml does not use fold: let rec fold f s accu = match s with Empty -> accu | Node(l, v, r, _) -> fold f l (f v (fold f r accu)) The similar functions (e.g. accumulate for a splay tree) do have commonality which can be factored out. This commonality is factored out as functions templated over iterators in the STL. In OCaml, this can be factored out by writing these functions in terms of fold: let sum fold c = fold ( +. ) 0. c let list_sum = sum List.fold_left The automagic effect will only be worthwhile if you are implementing a lot of data structures (which is very unlikely) in which case you can use a tuple of functions: let common fold = (fun fold c -> fold ( +. ) 0. c), ... let list_sum, list_... = common List.fold_left > You should really check out the article cited by Vasili. It seems that > we understend different things by "functional equivalent of an > iterator", I read it yesterday and, indeed, we did not mean the same thing by that term. I was referring to how I would go about rewriting a C++/iterators program in OCaml. I wouldn't begin by implementing iterators. I think you were referring to how iterators could be implemented in a functional language. Is that right? 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