[rust-dev] iter library

Niko Matsakis niko at alum.mit.edu
Fri Apr 27 19:05:51 PDT 2012


I just pushed a rather different version of the iter library to master.  
The existing approach wasn't really working out.  The new one is 
simpler, and I think it will work out quite well, especially as we start 
making better use of slices.  It is also plays nicely with the `for` 
loop syntax.  Lemme know what you think.

To implement an iterable type, you have to implement this interface:

     iface base_iter<A> {
         // invoke f() on each item, stopping if it returns false
         fn each(f: fn(A) -> bool);

         // returns the number of items in your collection, if you know it,
         // or none otherwise.
         fn size_hint() -> option<uint>;
     }

There are then a variety of various helper methods that you get "for 
free" (to_vec(), foldl(), contains(), map_to_vec() and so forth).  
Unfortunately, since we don't have traits, I have to resort to a clever 
trick that Brian came up with to share these methods.  I have defined 
two instances so far: vec and option.  If you want to see how to 
implement such a type, check out iter-trait.rs and iter-trait/vec.rs.  
The magic also relies on various #[path] attributes in core.rc.  It's 
deep voodoo, let me tell you.

## Future plans

Later, I would like to add str, map, and a variety of other types.  For 
types (like str and map) where there are multiple possibilities for how 
to iterate, my plan is to use wrapper types like so:

     enum keys<K,V,M:map<K,V>> = &M;

This wrapper would allow you to iterate over the keys in a map.  You 
would use it something like:

     for keys(&map).each { |k| ... }

This also allows things like

      keys(&map).map_to_vec { |k| ... }

Another example where I think such wrapper types would be helpful is for 
iterating over two slices in parallel.  I planned to have an enum like:

     enum zip<A,B> {
         zip([A]/&, [B]/&)
     }

which would implement the iterable interface for the type (&A, &B).  And 
so forth.

I also wanted to replace (or supplement) the `eachi()` method with 
something like

     enum enumerate<A,IA:iterable<A>> = IA;

where `enumerate` implements the iface for the type `(uint, IA)`.  This 
would then allow you to write:

     for enumerate(keys(&map)).each { |(i, k)| ... }

(This requires support for irrefutable patterns in argument types, but 
we should add those)

## Possible far future plans

If we added support for higher-kinded types, we could support a `map()` 
method in the iteration trait.  But until then we have `map_to_vec()`, 
which always results in a type of `[A]`.  Maybe we should find a shorter 
name, to just do `iterable.to_vec().map()`.  I dunno.


Niko


More information about the Rust-dev mailing list