How to use std::iter::Iterator::map for tree-like structures in Rust?

user_7499787 0
Viewed 228

As I understand the idiomatic way to apply a function to each element of a structure in Rust, is to implement IntoIterator and FromIterator and use map and collect. Like this:

enum F<A> {
    // fields omitted
}

impl<A> IntoIterator for F<A> {
    // implementation omitted
}

impl<A> FromIterator<A> for F<A> {
    // implementation omitted
}

fn mapF<A, B>(x : F<A>, f) -> F<B> 
    where f : Fn(A) -> B 
{
    x.into_iter().map(f).collect()
}

However it doesn't seem possible to implement FromIterator for a tree, because there are multiple ways to organize a sequence of values into a tree. Is there some way around this?

rust
2 Answers

the idiomatic way to apply a function to each element of a structure in Rust, is to implement IntoIterator and FromIterator

This is not quite true. The idiomatic way is to provide one iterator, but you don't have to implement these traits.

Take for example &str: there isn't a canonical way to iterate on a string. You could iterate on its bytes or its characters, therefore it doesn't implement IntoIterator but has two methods bytes and chars returning a different type of iterator.

A tree would be similar: there isn't a single way to iterate a tree, so it could have a depth_first_search method returning a DepthFirstSearch iterator and a breadth_first_search method returning a BreadthFirstSearch iterator.

Similarly a String can be constructed from an iterator of &str or and iterator of char so String implements both FromIterator<&str> and FromIterator<char>, but it does not implement FromIterator<u8> because random bytes are unlikely to form a valid UTF-8 string.

That is, there isn't always a one-to-one relation between a collection, and its iterator.

and use […] collect

This is (mostly) incorrect. Collecting is not a good way to consume an iterator, unless you actually want to use the collected result afterwards. If you only want to execute the effect of an iterator, use for of the for_each method.

user_27338510

You could include information about tree structure into the iterator, something like

impl F {
    pub fn path_iter(self) -> impl Iterator<Iter=(TreePath, A)> { ... }
    // rest of impl
}

impl<A> FromIterator<(TreePath, A)> for F<A> {
    // implementation omitted
}

fn mapF<A, B>(x : F<A>, f) -> F<B> 
    where f : Fn(A) -> B 
{
    x.path_iter().map(|pair| (pair.0, f(pair.1))).collect()
}

With TreePath a type specific for your tree. Probably better representing not the path itself but how to move to the next node.

I originally suggested implementing IntoIterator with Item = (TreePath, A) but on further thought the default iterator should still have Item = A.

alexey_r_92040
Related