Talk:Iterator

From Wikipedia, the free encyclopedia

Concerning the removed text in the Python section by User:Fredrik on 14 Dec 2004:

 "It should be noted that non-sequence collection types, such as dict
  (an associative mapping), do not support iteration directly.  To iterate over
  these collection the user first must convert them to sequence types."

That limitation in the language was only removed as of Python version 2.2. In all versions of Python prior to that it was/is still true that you can not directly iterate over dictionaries. - Dmeranda 01:18, 17 Dec 2004 (UTC)

Contents 1 Iterators as in CLU or Ruby 2 Iterators in JavaScript 3 Generators 4 Why do I get a redirecton from enumerator ? 5 Sounds like catch up to APLs to me 6 Elements disambiguation 7 Concerning merging Iterators to this article

[edit] Iterators as in CLU or Ruby

The mentioned Python (unknown to me) seems to support "generators". Apart from this the way iterators were introduced by CLU has been forgotten. There these are free-standing procedures which have (invisible and implicitly) the loop body as a parameter. This kind of iterators is supported directly by the above mentioned programming languages.

We have developed the functional equivalent of a CLU iterator in Delphi (16 and 32 bit) using knowledge of the compiler output, and we are using this successfully for years. With some auxiliary routines (e.g. iterating, see below) the call of an iterator is essentially as follows:

iterator(parameters); while iterating do body;

The usual applications are: Stepping through containers (tree, list, registry, ...; possibly with premature loop end), and the "perverted" case where only one callback occurs, e.g. allocate and deallocate resources, wait and signal of semaphores, synchronize (run in main thread).

There is no real alternative to such iterators since with means of the high languages (e.g. Delphi, C++, Java) the iterator can not transfer the local scope and can only call a method or a global procedure. This leads to unattractive effort to feed an auxiliary object (this could be the current object as well) with parameters and local variables, call the iterator and finally transfer back all these variables. An iterator supported by the language does not meet such problems!

The Japanese Wikipedia page for this subject seems to contain at least a reference to Ruby...

-- Jasper1711 15:49, 27 July 2005 (UTC)

There should be something about Alphard in this article as well. 131.155.99.235 10:58, 26 January 2006 (UTC)

[edit] Iterators in JavaScript

Is someone likely to mention JavaScript iterators? In JavaScript, iteration can easily break if someone pollutes an object in the prototype chain and the code doing the iteration assumes that all iterated elements come from the object and not its prototype chain.

I don't think JavaScript's iteration qualifies. As far as i understand it, the for ... in construct can only iterate over the keys of an object/array; you can't even use it to iterate over the contents of JavaScript's builtin arrays, let alone user-defined containers and sequences. --Piet Delport 09:59, 24 March 2006 (UTC)

[edit] Generators

I rewrote the article's description of generators, to clear up some misconceptions. For the record, here's the original version, with my objections:

"A generator is a special kind of iterator in which the container object is not fully realized. This allows abstract or even infinite collections to be processed one element at a time."

This is a vacuous truth. Just like conventional iterators, generators support both finite container traversal and lazy/infinite sequence realization equally. There's simply no difference between them at all, as far as this is concerned. (What does distinguish generators and conventional iterators is how their state is maintained; an analogous relationship exists between closures and function objects.)

"Generators are common in functional programming languages, or languages which borrow some functional concepts."

I'm not sure where this idea comes from. Generators are very much a procedural/imperative concept, as opposed to functional. Perhaps the author was thinking of list comprehension syntax?

"Generators are often implemented in terms of continuations."

While (like every other control structure :) generators can be implemented in terms of continuations, this is not the case with any generator-supporting language i know of.

--Piet Delport 17:41, 24 March 2006 (UTC)

While your observations are correct, and I do appreciate cutting most of the details in favor of the separate generators article, I think that perhaps it is still quite useful here to still explain that generators are often used in cases where the collection is inifinite or expensive to compute or store. True, an iterator can do that too, but it is far less common to see them used that way. I see nothing wrong with mentioning this common practical difference between generators and iterators, even if it's not a technical absolute. -- Dmeranda 05:20, 29 March 2006 (UTC)

That's precisely what the practical difference between them isn't, though. If you read the motivation for adding generators to Python, you'll find that it doesn't even mention lazy computation (of infinite/expensive-to-calculate sequences) at all, but is instead entirely concerned with how iterators that usually need cumbersome, explicit state maintenance (state machines, manual recursion stacks) are much more clearly and naturally expressed as generators. Looking at real-life Python code (such as the standard library) confirms this: large/infinite iterations with simple or no state, like computing large/infinite number sequences (xrange, count), or lazily iterating through large files, lists, dicts, or other simply-structured data sets, are actually implemented using plain (non-generator) iterators, while more complex, stateful things like iterating though hierarchical/recursive collections, parsing/tokenization, and algorithms like diff, are usually expressed as generators, even though those are all finite, and aren't any less expensive to calculate due to being generators.

In other words, in practice, the decision between generator and non-generator iterators is entirely governed by state management, not computational laziness. If the iterator doesn't need to manage state, then there's very little practical difference between the two choices, regardless of how infinite/expensive the computed sequence is; if anything, the non-generator versions are sometimes slightly smaller and clearer than the generator version.

In other words, saying "Generators are often used for infinite/expensive sequence computation" is just as technically correct, and just as misleading, as saying "Automatic (as opposed to manual) transmission cars are often used for long-distance driving". It's true, but entirely besides the point of what the distinction is actually about.

--Piet Delport 14:05, 29 March 2006 (UTC)

[edit] Why do I get a redirecton from enumerator ?

Hi. Tried to look up Enumerator and got a redirection to Iterator. They are definitely not the same as far as I understand. While an Iterator allows me to move over a set of Objects. An enumerator defines a named collection of objects or variables. Or do I get that wrong ?

Are you thinking of a particular programming language, or in general? While some languages might assign different meanings to "iterator" and "enumerator", i doubt there's any generalizable difference that Wikipedia can reflect. --Piet Delport 12:35, 4 May 2006 (UTC)

An enumeration is a type construct (such as an enum in Java or C). Enumerator is synonymous to iterator. Wouter Lievens 14:19, 4 May 2006 (UTC)

You're right mixed it up with enumeration...

An enumerator is really a specialized kind of iterator rather than being synomymous with it, and is so-named because of the mathematical concept enumeration, the mapping of the natural number sequence onto a set. The distinction is that an enumerator usually consecutively numbers the items as the iteration proceeds, whereas an iterator only must produce a sequence, numbered or not. Consider Python's enumerate(), which indexes a sequence. And enumerated type is a different programming concept altogether. Dmeranda 15:20, 5 May 2006 (UTC)

Good point. Sadly, though, Python is the only programming language (that i'm familiar with) that uses the term in this more correct sense, instead of as another word for "iterator/iteration". --Piet Delport 02:39, 7 May 2006 (UTC)

[edit] Sounds like catch up to APLs to me

Since the 1960s the vocabularies of APL languages descended from Ken Iverson's work have been composed almost completely of iterators as I understand the term being expressed here. The fundamental objects are arrays or lists of lists and even the elementary functions like + or = iterate over all items in their arguments. Beyond this, are the operators like / ( across ), and ' ( each ) which perform iterations of arbitrary functions on lists.

For that matter, Lisp's map operators ought to be mentioned --CoSyBob 07:55, 8 June 2006 (UTC)

Those are all ways of mapping, folding, or otherwise distributing operations across collections, which is distinct from what this article discusses: ways of representing (abstract or realized) collections as "item sources". (These are sometimes distinguished as "internal" and "external" iteration, respectively.)

While these two approaches have some amount of functional overlap, they are quite distinct in terms of how they work, and what situations they handle well. (Specifically: while the mapping approach is more terse, specialized and appropriate for stateless/independent operations across concrete data structures, the iterator approach is more flexible, allowing much easier expression of things like in-iteration state management, abstract sequence/operation composition, and dynamically-realized/infinite sequences.)

--Piet Delport 12:45, 8 June 2006 (UTC)

[edit] Elements disambiguation

I've been clearing up links to the element page, and for this one I have redirected to element (mathematics). If this is wrong, please correct. If the link was aiming at "element" to mean "fundamental part" then there is no such link in WP, please delete the link. LeeG 12:13, 12 June 2006 (UTC)

The term is used here more or less as a general, open-ended synonym for "item" or "member". While element (mathematics) is not far from the intended meaning, in many cases, none of the set theoretic concepts and connotations described there need apply here, so i'll unlink it. Thanks for the heads-up. --Piet Delport 21:52, 13 June 2006 (UTC)

[edit] Concerning merging Iterators to this article

I definitely agree with merging Iterators into this article. However it doesn't really appear to offer any additional information not already covered here—with the possible exception of mentioning that stack and queue don't usually require iterators; something I'm not sure needs mentioned anyway. So I'm really more for just turning Iterators into a redirect to here. --Dmeranda 18:07, 29 July 2006 (UTC)

Agreed. Chip Zero 18:45, 24 October 2006 (UTC)

Thirded. This article (Iterator) to me is a clearer explanation as well. hateless 20:03, 17 November 2006 (UTC)

Resolved. I changed the Iterators article into a simple redirect to this one. I had checked that article again to make sure no new content had been added, which none had. I still saw nothing worthy of merging, so this article, Iterator, has not been changed other than to remove the MergeFrom tag. Dmeranda 22:11, 17 November 2006 (UTC)