Darwin Help

Iterators

     Iterators are a mechanism to loop over non-trivial structures, for example the leaves of a Tree or the Sequences of a database or over the Prime numbers. Darwin provides a few basic iterators which are all implemented in Darwin code. Users can create iterators for any Class. In its simplest form, that is using an existing iterator, the protocol is the following:

# build a tree by some mechanism, e.g.
t := LeastSquaresTree( .... );
for z in Leaves(t) do
    #  z is a leaf of t, handle z
    lprint( 'This is a leaf:', z );
od:

     That is, the iterator is defined inside a for-in loop. Iterators are normally named with plurals, e.g. Leaves, Primes, Entries, Sequences, etc. The iterator may require an argument (like Leaves(t), the argument must be a Tree), or the argument may be implicit, (like Entries(), which implies using the entries in the default database pointed by the global variable DB), or may not have arguments at all (like Primes(), which is the infinite sequence of primes numbers).

SumPrimes1000 := 0:
for p in Primes() while p < 1000 do
    SumPrimes1000 := SumPrimes1000 + p
od:

     Notice that in the above loop we need a while condition to terminate it, as the loop over the primes will never terminate, there is an infinite number of primes. This example is also useful to distinguish an essential feature of iterators in Darwin, which is that the iteration values are computed and used one at a time. So if few are used, few are computed. It is obvious that computing all the iterators ahead of using them would not be possible for Primes(). This is all what a user needs to know about iterators to use them.

Defining new iterators

     To define a new iterator, the user must implement a function with the name of the iterator and the suffix "_iterator". Such a function will take control when a for-in statement with the given iterator is used. We illustrate the definition of iterators first with a trivial example and then using two real examples, Leaves and Primes. The use of these iterators has been shown above.

PositiveIntegers_iterator := proc()
  for i do iterate(i) od
end:

# used as
for z in PositiveIntegers() do ... od;

     The above iterator produces the infinite sequence of positive integers, one after the other. The iterator function has to be viewed as taking control between the for-in statement and the body of the loop, and feeding one by one the values to the loop (through the function iterate). This is slightly different than the iterators found in other languages and has the big advantage of being able to preserve the state from one iteration to the next. The Primes iterator is only slightly more complicated than the above, namely:

Primes_iterator := proc()
  iterate(2);
  for i from 3 by 2 do
      lim := ceil(sqrt(i));
      for z from 3 by 2 to lim while mod(i,z) > 0 do od;
      if z > lim then iterate(i) fi;
  od
end:

     The prime 2 is produced first, then then all the odd integers are tested for divisibility using the standard arithmetic brute-force method. Notice that the iterator function never terminates, in both cases the sequences are infinite. If the iterator function returns, this terminates the for-in loop. The for-in loop may be terminated for other reasons, namely failure of a while-condition, use of the token "break" or any type of untrapped error. Next we show the iterator for Leaves.

Leaves_iterator := proc( t:Leaves(Tree) )
  if type(t[1],Leaf) then iterate(t[1])
  else procname( Leaves(t[1,Left]) );
       procname( Leaves(t[1,Right]) )
  fi
end:

     The iterator is called with the entire object found in the for-in clause. This is convenient when there are several arguments and is done to be uniform with other polymorphic methods. So the actual tree is in t[1], the argument of Leaves. This example shows that the iterator could be called recursively (or could call other functions). For the execution of the for-in loop, the only two events that matter are the calling of iterate(xxx) (which will run the body of the loop with the for-variable assigned the value xxx) and exiting the iterator, which will cause the loop to terminate.

See Also: