#Problem
Currently, there is no way in Rust to specify a trait to the effect of “this has an iterator”. This makes it impossible to generically acquire an iterator, and consequently makes it impossible to generically glue together collections. If and when associated types land, this shouldn’t be an issue. But that’s post 1.0, and for now, we have nothing.
But, it is possible to generically tell something to iterate over itself using a provided function. Enter: the Traversable traits (shout outs to Scala for the name).
#Traversable
The traversable traits are a very simple shim. They each provide a single method for “give me some code to run on all of my elements”. They can be implemented today by just dropping this code in iter.rs:
pub trait Traversable <T> {
fn foreach(&self, f: |&T| -> bool);
}
pub trait MutTraversable <T> {
fn foreach_mut(&mut self, f: |&mut T| -> bool);
}
pub trait MoveTraversable <T> {
fn foreach_move(self, f: |T| -> bool);
}
(the bool is to signal that you wish to break early)
And here’s a full implementation for a Vec:
impl <T> Traversable<T> for Vec<T> {
fn foreach(&self, f: |&T| -> bool) {
for x in self.iter() {
if f(x) { break; }
}
}
}
impl <T> MutTraversable<T> for Vec<T> {
fn foreach_mut(&mut self, f: |&mut T| -> bool) {
for x in self.mut_iter() {
if f(x) { break; }
}
}
}
impl <T> MoveTraversable<T> for Vec<T> {
fn foreach_move(self, f: |T| -> bool) {
for x in self.move_iter() {
if f(x) { break; }
}
}
}
Super easy. Now we can write methods for collections like insert_all, which takes a collection, and inserts all of its contents. In fact, we can take anything that implements this interface. Like this:
fn insert_all <C: MoveTraversable<T>> (&mut self, other:C){
other.foreach_move(|x|{
self.insert(x); false
});
}
Once RFC 24 (which is a 1.0 blocker) lands, we should also be able to drop this into iter.rs, and have all iterators be traversable:
impl <'a, T, I:Iterator<&'a T> + Clone> Traversable <T> for I {
fn foreach(&self, f: |&T| -> bool) {
for x in self.clone() {
if f(x) { break; }
}
}
}
impl <'a, T, I:Iterator<&'a mut T> + Clone> MutTraversable <T> for I {
fn foreach_mut(&mut self, f: |&mut T| -> bool) {
for x in self.clone() {
if f(x) { break; }
}
}
}
impl <T, I:Iterator<T>> MoveTraversable <T> for I {
fn foreach_move(mut self, f: |T| -> bool) {
for x in self {
if f(x) { break; }
}
}
}
Then we’ll have generic methods which take either a collection or an iterator, and process their contents.
Here’s all of this working right now in the playpen. Currently without RFC 24, you can only impl all iterators, or individual concrete structures. In this example I’ve opted to impl iterators since that’s way cooler.
Bonus Round
Once associated types land, and we can implement Iterable traits, we can make Iterable inherit Traversable, and provide default Traversable impls for Iterables. Then we can rip out all the individual Traversable implementations, and kindly direct people to use the more flexible and effecient Iterables, without breaking any code! APIs can individually be migrated to use Iterable where desirable. Pretty much everything that is Traversable should be Iterable anyway.
Do we want this?
So it’s like 3am right now, so I’ve probably overlooked something serious, but this seems super easy and useful to implement (literally the entire implementation is in this post). So does everyone agree that this is worthwhile? Or is this an awful idea? Anything you’d like to see included/removed/changed?