Does anybody need a try_flatten() method?

Hi,

So as part of quite some refactoring (in a not yet released version) of my fnmatch-regex crate, I built up an iterator of Result<Option<String>> values, with the knowledge that, due to the way the glob pattern is parsed, most of the Ok results will not contain any strings (None values for the option). Then I wanted to use collect::<Result<...>>()? to break on an error result, but I also wanted a way to skip all the empty objects. My first attempt was to collect everything into a vector (checking for errors), turn that into an iterator, and flatten it, but, as I mentioned, most of the values would be empty, so I did not really want to collect them into the vector. (Of course, when parsing a glob pattern, there cannot possibly be that many values, so this is basically a microoptimization, but still I wondered whether there was a way to do it for a significant number of values).

My second attempt was to write a whole new trait with a struct that implements it: https://gitlab.com/ppentchev/try-flatten/-/blob/main/src/lib.rs; maybe the best way to understand what it does is to look at the unit tests.

Of course, ten minutes later I figured out that, since I just discovered the neat trick of recursively calling self.next() in an interator's next() method, I could actually do that in the iterator that does the real work, and so it happened, so now fnmatch-regex will not use the try-flatten trait.

So my question here is, is it okay to assume that it should always be that easy to skip unwanted values, and that, therefore, there is no need to further pollute the crate namespace? Or would anybody actually use try-flatten, if I should upload it?

Thanks in advance, and sorry for wasting your time with something that I myself am on the verge of considering to be completely useless :slight_smile:

G'luck,
Peter

1 Like

I have several thoughts. First, you can get what you need with existing combinators:

.flat_map(Result::transpose).collect::<Result<Vec<_>, _>>()

Result::transpose puts the Option on the outside, and calling it from flat_map() takes advantage of the interpretation of Option as an iterable of zero or one item.


Second, I think the best thing to do with any iterator extension would be to contribute it to itertools. That way it doesn't need to be its own crate and trait, and people looking for just the right iterator combinator will be able to find it in a well-known location.

As it happens, itertools already has this, as flatten_ok().


Third, it's not in general a good idea to have your iterator recurse inside self.next(). Rust doesn't guarantee tail recursion elimination, so you could cause a stack overflow with sufficient attempts.

Instead, when you need to keep trying to find an item to return, you can use a loop {} inside your next() implementation.

impl Iterator for Foo {
    fn next(&mut self) -> Option<Self::Item> {
        loop {
            if time_to_give_up() {
                return None;
            }
            if let Some(item) = try_to_find_thing() {
                return Some(item);
            }
        }
    }
}
4 Likes

Thanks A LOT for this brief yet exhaustive and so, so informative answer!

OK, so I cannot believe that after all those years of writing Python it did not even cross my mind to check whether somebody had used the name "itertools" for a crate... Thanks an awful lot for pointing it out, it was lying right there, but I had missed it completely, and it is so, so, so useful! (Yes, of course, half of its functions may be implemented in two lines of code, but that's the whole point, right - not writing those two lines over and over and over again) It did simplify my fnmatch-regex parser quite a lot indeed, especially the partition_map() method.

And yeah, I have to admit that I did wonder for a moment whether I can really depend on tail-call optimization in Rust, and then... and then somehow I decided that I could, even with all those years of writing C and witnessing all the different ways in which the different compilers do all kinds of weird things, all the trouble with different modes of optimization, and so on. Thanks for bringing this up!

So, yeah, just in case you somehow missed that part - thanks a lot! :slight_smile:

G'luck,
Peter

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.