Lambda the Ultimate

From that article and your Haskell, I've managed to develop a Tcl version. [Edit: Moved code to the Tcl wiki, and fixed many bugs...]

Well, it all seems to work for lists. However, the current version is terribly inefficient in Tcl. Now to see if I can optimise it, but it's going to take a lot of work to be a practical technique in Tcl (on my laptop the last comparison shows the stream/fold version takes 998.12 microseconds per iteration vs 6.38 for the standard lrange, i.e. ~156X longer).

For one thing, Ruby doesn't have Icon-like generators.

Perhaps not (I don't know Ruby). It seems Ruby uses enumerator functions much like those described in the article. This discussion even hints at a continuation based implementation of an enumerator->iterator conversion, which I guess is similar to the Scheme one.

For another, to say that callbacks are faster than iterators, using Java System.arraycopy() as an example, is... well, ridiculous.

Not callbacks, as such, but enumerator functions. The point of enumerator functions is that they are whole-collection operations which encapsulate a complete traversal. System.arraycopy() is an example of such a whole-collection enumerator function in that it encapsulates a traversal of an array performing a copy. Because of this encapsulation, it is therefore possible to employ a specialised efficient implementation (e.g. using memcpy()), without changing the interface.

However, I take your point that it doesn't really demonstrate why a fold is more efficient than an iterator, as it is hard to imagine how implementing arraycopy() in terms of fold() would be any faster than implementing it in terms of an iterator. Indeed arraycopy() is an example of having to traverse two collections at once (source and destination) which is tricky for a fold. In general, though, I do think folds provide more opportunities for optimisation than iterators.

There are other advantages to enumerator functions than just speed, such as generally working at a higher level of abstraction, and not exposing any state to clients. Streams/lazy sequences also share some of these benefits, and can be a good choice in certain cases. For instance, the problems with combining enumerations over multiple containers seem to translate into general problems with composition of enumerations, whereas with streams this is not the case. For instance, consider code like the following:

check [parse [lex $spec]] [parse [lex $source]]

If lex/parse etc all return streams (or iterators) then this is straight-forward enough. However, it is hard to see how to implement this as a fold. You could define a foldl2 for iterating over two collections of the same type, e.g. for lists:

foldl2 :: (a -> b -> c -> a) -> a -> [b] -> [c] -> a
foldl2 f z [] []         = z
foldl2 f z (x:xs) (y:ys) = foldl2 f (f z x y) xs ys

But then each collection has to define a foldl, foldl2, foldl3, etc up to some arbitrary limit (or a variadic version, if your language allows), and it still doesn't address what to do if the collections are of different types (or even of different lengths). So, there is still clearly an occassional need for an iterator-style interface (in the form of streams, preferably), but I'd still agree with the central point of the article that a left-fold enumerator function is the best default, especially if you can convert between such a function and a stream easily.