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 NAA31650; Wed, 28 Apr 2004 13:41:58 +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 NAA31639 for ; Wed, 28 Apr 2004 13:41:57 +0200 (MET DST) Received: from smtp1.adl2.internode.on.net (smtp1.adl2.internode.on.net [203.16.214.181]) by nez-perce.inria.fr (8.12.10/8.12.10) with ESMTP id i3SBfsjq029358 for ; Wed, 28 Apr 2004 13:41:55 +0200 Received: from [192.168.1.200] (ppp119-113.lns1.syd2.internode.on.net [150.101.119.113]) by smtp1.adl2.internode.on.net (8.12.9/8.12.9) with ESMTP id i3SBc5Zq008075; Wed, 28 Apr 2004 21:08:06 +0930 (CST) Subject: Re: [Caml-list] [ANN] The Missing Library From: skaller Reply-To: skaller@users.sourceforge.net To: Martin Berger Cc: The Caml Trade In-Reply-To: <408F6E8A.9060605@dcs.qmul.ac.uk> References: <1083140676.9537.831.camel@pelican.wigram> <408F6E8A.9060605@dcs.qmul.ac.uk> Content-Type: text/plain Message-Id: <1083152284.9537.931.camel@pelican.wigram> Mime-Version: 1.0 X-Mailer: Ximian Evolution 1.2.2 (1.2.2-4) Date: 28 Apr 2004 21:38:05 +1000 Content-Transfer-Encoding: 7bit X-Miltered: at nez-perce 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 iterator:01 generalised:01 iterator:01 9660:01 glebe:01 ocaml:01 nsw:01 snail:02 complexity:02 tree:02 iterators:02 iterators:02 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Wed, 2004-04-28 at 18:42, Martin Berger wrote: > >>I'm wondering what concepts Ocaml can't express/enforce? > > > > > > Iterators. > > it's been a long time since i used C++, but i seem to remember that > complexity guarantees are also part of the STL specification: something > like "to go from element x to element x+n" using a linear iterator takes > at most O(n) steps". Yes, that's true of C++ Standard Library iterators. However, in the more abstract context, I'd say that important idea is a design guide, not a requirement. Clearly a single fixed iteration technique for a given data structure is not enough for all problems, any more than a fixed set of algorithms. In particular if you consider more general tree navigation, you can certainly do anything with iterators, but clearly the movement instructions may have to be generalised. You may need 'goto_parent' as well as 'goto_next_child' for example.. The key thing characterising an iterator appears to be that it is some state representing a position in a data structure. -- 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