Iterator Pattern In Ruby

Moved from IwannaLearnRuby

One thing really bugged me; they said that they support VisitorPattern because Ruby has foreach. That struck me as remarkably obtuse.

I think they were just using foreach as an example of VisitorPattern usage. Ruby supports visitor, because it allows functions to be first class objects. Can you point me to the actual text you're talking about so I can read it in context?

I dunno, it seems pretty clear: "The Visitor Pattern: It's the method each." http://www.rubycentral.com/book/lib_patterns.html

The implication on that page that each captures 100% of the Visitor pattern is what annoyed me.

According to http://wiki.rubygarden.org/Ruby/page/show/VisitorPattern, that line in the ProgrammingRuby book is a typo. It is meant to read IteratorPattern.

---

They mean code like this:

 def do_something( element ); ...; end
 a_collection.each { |element| do_something( element ) }

which does implement VisitorPattern in a sense, though in a fairly simple way. In particular, the iterator semantics of "each" is predefined in most collection types such as arrays or hashes. If you have a more complex structure, you might want to define new iterators, so you can have code like:

 a_binary_tree.depth_first { |element| do_something( element ) }

you'd have to define "depth_first" on your BinaryTree class, but defining iterators isn't particularly difficult. -- francis

Does your example imply that you can't have multiple simultaneous iterators over the same data structure? E.g. traverse a tree right-to-left and left-to-right simultaneously, to see if the tree is symmetric and a palindrome or some such.

Well, that's the way iterators are generally written because that's the way you need them 99% of the time. If by "simultaneous" you mean having fine-grained control of stepping through a collection, then "each" or other block-driven iterators won't get you that. I suppose for something like that you could write a custom BinaryTreeIterator? class that would traverse nodes with calls to "next" and store state between those calls. For some reason, I've never had to do this ... -- francis

Real iterators are separate objects with their own state, not a service offered by a collection object, precisely so that there can be more than one active. A less fanciful example of why it is needed: Do a full traversal, calling some function on each element. That function needs to make some decision (like, say, whether the element is duplicated), and to do so, it needs to do its own full traversal of the collection, so you have a need for nested traversals. It's even more obviously needed if the code is multi-threaded; this perhaps arises less often, but if the language has designed iterators incorrectly, you're potentially screwed when it does arise. -- DougMerritt

Well, it's not a problem in that sense. For example, this code would work:

 found_duplicate = false
 array.each_index { |i|
   array.each_index{ |j|
     if i != j && array[i] == array[j]
       found_duplicate = true
     end
   }
 }

Each individual invocation of "each" or "each_index" (both are iterators, one iterates elements, the other iterates the indices) maintains a separate state from the others. (I avoid "each_index" when I can, but in this case it's needed since you don't want element 5 comparing itself to element 5.)

So I don't know if that satisfies your definition of a "real" iterator.

It does (as long as there aren't gotchas). Thanks for explaining.

I can simply say that I've personally used Ruby for a lot of non-trivial projects, and iterating through collections is not a problem I have. I can imagine edge cases where you'd need something more stateful, but for whatever reason they don't come up for me much. In fact, with the "each" iterator I never make FencePostErrors anymore, so that's a big gain. -- francis

You guys might benefit from looking at the difference between InternalIteration and ExternalIteration as well as the works of ThomasKuehne and JamesNoble in this area. As always, with fairly esoteric comp-sci, CiteSeer is your friend.

Thanks for the useful links. In such a parlance, built-in Ruby iterators like "each" and "each_index" would be InternalIterators. If you wanted ExternalIterators, you'd have to build them yourself, though it wouldn't be too difficult. -- francis

It's actually possible to do ExternalIterationUsingContinuations - you can create a general-purpose ExternalIterator class to transform an InternalIterator into an ExternalIterator. It's about 20 lines of Ruby code (without comments ;). It's certainly not easy to understand, so I wouldn't want to post it on a page for Ruby beginners, but it might be interesting for people to know that it's possible. -- AdamSpitz

---

Hmmmm. I thought the main point of the VisitorPattern was the double dispatch, and that the traversal was somewhat incidental. -- PeterSeibel

---

CategoryRuby