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 KAA19234; Wed, 28 Apr 2004 10:38:01 +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 KAA19243 for ; Wed, 28 Apr 2004 10:37:59 +0200 (MET DST) Received: from smtp3.adl2.internode.on.net (smtp3.adl2.internode.on.net [203.16.214.203]) by nez-perce.inria.fr (8.12.10/8.12.10) with ESMTP id i3S8bujq005444 for ; Wed, 28 Apr 2004 10:37:58 +0200 Received: from [192.168.1.200] (ppp119-113.lns1.syd2.internode.on.net [150.101.119.113]) by smtp3.adl2.internode.on.net (8.12.9/8.12.9) with ESMTP id i3S8bnk2002272; Wed, 28 Apr 2004 18:07:49 +0930 (CST) Subject: Re: [Caml-list] [ANN] The Missing Library From: skaller Reply-To: skaller@users.sourceforge.net To: Jon Harrop Cc: caml-list In-Reply-To: <200404280613.19547.jdh30@cam.ac.uk> References: <200404280613.19547.jdh30@cam.ac.uk> Content-Type: text/plain Message-Id: <1083141467.9537.845.camel@pelican.wigram> Mime-Version: 1.0 X-Mailer: Ximian Evolution 1.2.2 (1.2.2-4) Date: 28 Apr 2004 18:37:48 +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 2004:99 deque:01 exhibit:01 iterator:01 exhibit:01 ignoring:01 callback:01 iterator:01 generalise:01 generalised:01 9660:01 glebe:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Wed, 2004-04-28 at 15:13, Jon Harrop wrote: > On Wednesday 28 April 2004 5:31 am, Brian Hurt wrote: > > It's been too long since I've used the STL- what data structures and > > algorithms does it provide? > > The main thing is that it is iterator-centric, > This is quite useful for 1D containers, which the STL provides (list, slist, > vector, deque), but it doesn't lend itself well to many useful containers > (trees, matrices, higher-dimensional arrays) which exhibit more interesting > connectivities than a bidirectional iterator can represent and which do not > exhibit a clear notion of "sub". That isn't true. Computers can only do things in sequence (well, ignoring fledgling parallelism). Using iterators, your higher dimensional problem is factored into two halves: the sequential algorithm, and the sequence generator. There aint no other way (short of parallelism). Iterators simply enforce a control inversion boundary: the sequence generator is callback driven, the algorithm its driver: iterators mediate the control relation. Exactly how you define your iterator is up to you, but clearly the specification factors your problem as I described. Obvious examples include say 'depth first traversal' of a tree. However you process a tree, it can be done with an iterator. Perhaps it is necessary to generalise the concept of 'next': in STL you can +/- int for random iterators, but there is no reason next can't be generalised to take an arbitrary motion indicator. Clearly that reflects on the general structure of the container, so there are higher classes of iterators than just forward and random. The key concept is a 'current location' and 'movement instruction'. Sounds like Logo got it right with Turtle graphics :D -- 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