9 ms·

Creating an empty iterator of a certain type in Rust (2018)

35 points by airstrike 2y ago

claytonwramsey 2y ago
Another possible solution for this use case: let each capacity graph store a “dummy” `HashMap<N,(u128, u128)>` for the case where the key is missing. Then, return an iterator over the empty dummy to get an iterator of the same type. I will however note that simply using an option in the return value is probably the best choice both API- and performance-wise. The consumer may want to do different things if the key doesn’t exist versus if the key has no neighbors. Additionally, returning an Option means there’s only one check for whether the retrieval was correct, rather than checking at every call to `next`.
kd5bjo 2y ago
Because `OptionIterator` implements the `Iterator` trait, the function signature can be simplified to return just `impl Iterator<…>` like the original version did, leaving the additional type as an implementation detail. Also, a similar solution is provided by the `either` crate [1], where the function body can return `Either::Left(std::iter::empty())` in one case and `Either::Right(…)` in the other, also hiding all of this behind an `impl Iterator<…>` return type. [1] https://docs.rs/either/latest/either/enum.Either.html https://docs.rs/either/latest/either/enum.Either.html
kawogi 2y ago
> However, this solution is not very ergonomic, as it requires the user of the function to first check if the returned value is Some(iterator) and only then iterate over the iterator. I'd use `flatten()` to iterate over this nested type.
sk11001 2y ago
I don't understand the people who look at this and go "yep, we should have more of this language". It's complexity for its own sake.
- ryanjshaw 2y ago
  I'm really confused... Is all of this just the equivalent of `Enumerable.Empty<T>` or `yield return` in C#?
  - sk11001 2y ago
    So you do agree that other languages achieve the same thing with much less complexity?
    - tcfhgj 2y ago
      Not exactly the same thing though
  - MereInterest 2y ago
    Not quite, because the user of those would need to perform dynamic dispatch in order to iterate over the result. In the article, the returned iterator has a type that is known to the compiler, and so the caller’s code can be optimized much more effectively.
  - Measter 2y ago
    I'll ignore the option of returning a Vec or Option, as the article already went over why these options were rejected, and concentrate on the later options. Firstly the `std::iter::empty()` attempt: The issue they had here came down to the signature of the function. What they wanted to do was return an `impl Iterator<Item=&N>`. This means that the function isn't naming the specific type it returns[1], only stating that it's an Iterator that gives some `&N`s. However, the return type of this function is still one, specific type. You cannot return two different types that are both iterators. That's why this one failed. Boxing: Instead, we can return a `Box<dyn Iterator<Item=&N>>`. This is roughly equivalent to a function in C# returning an `IEnumerabale<N>`, in that the actual type is hidden, and the work is done doing dynamic dispatch. This allows you to return different kinds of iterators, because the specific type is hidden away inside the Box. The downside here is that you're doing a heap allocation. OptionIterator: This one is actually basically just the first Option case from earlier but wrapped up in a nicer-to-use interface for the user because it implements Iterator in a way that transparently handles the Option. [1] Additionally, it's not even possible to name the type of the iterator here due to the filter closure being unnamable.
Patryk27 2y ago
fwiw, Option already implements iterator (well, IntoIterator) - calling .into_iter() on an Option will get you an iterator, no need to create anything custom.
- antonvs 2y ago
  I wonder if that existed when this article was written in 2018.
  - MereInterest 2y ago
    The footnotes mention that this solution was suggested by Reddit comments at the time.
orlp 2y ago
There is another alternative which may be significantly more efficient as it means the caller always gets back a direct iterator instead of an enum it must branch on: make a dummy empty hashmap with a static lifetime you can refer to. Then the implementation becomes static DUMMY: LazyLock<HashMap<N, (u128, u128)>> = LazyLock::new(HashMap::new()); fn neighbors_with_send_capacity_option(&self, a: N, capacity: u128) -> impl Iterator<Item=&N> { let node = self.nodes.get(&a).unwrap_or_else(|| &*DUMMY); node.keys().filter(move |b| self.get_send_capacity(&a, b) >= capacity) } Unfortunately we have to use a LazyLock for the static because HashMap::new isn't const. It only adds a single always-correctly-predicted branch that checks for initialization on access though, so it's fine.
blumenkraft 2y ago
Performance or not, this language is borderline unreadable.
the_mitsuhiko 2y ago
You don't need to do all that much, you can use `Option` with `into_iter` paired with `flatten` instead: fn neighbors_with_send_capacity(&self, a: N, capacity: u128) -> impl Iterator<Item = &N> + '_ { self.nodes .get(&a) .map(|m| m.keys()) .into_iter() .flatten() .filter(move |b| self.get_send_capacity(&a, b) >= capacity) } The only downside is that I believe `size_hint` is not properly forwarded.
- OptionOfT 2y ago
  Forgive the non-versioned link: https://doc.rust-lang.org/1.81.0/src/core/iter/adapters/flatten.rs.html#618 https://doc.rust-lang.org/1.81.0/src/core/iter/adapters/flat... I think it does work correctly.
realcr 2y ago
I stumbled upon this article today. My first thought was that this is an interesting question, then I continued reading and thought that the solution ideas are kind of crude. Then I noticed it was written at 2018, so I realized we should give the author a break. Finally I realized that it was me who wrote this, 6 years ago! So much has changed, but I believe the easy solution already existed back then. As people wrote in the comments here, one can iterate over an Option and then use flatten. Strange experience indeed.

35 points by airstrike 2y ago

Another possible solution for this use case: let each capacity graph store a “dummy” `HashMap<N,(u128, u128)>` for the case where the key is missing. Then, return an iterator over the empty dummy to get an iterator of the same type. I will however note that simply using an option in the return value is probably the best choice both API- and performance-wise. The consumer may want to do different things if the key doesn’t exist versus if the key has no neighbors. Additionally, returning an Option means there’s only one check for whether the retrieval was correct, rather than checking at every call to `next`.

kd5bjo 2y ago

Because `OptionIterator` implements the `Iterator` trait, the function signature can be simplified to return just `impl Iterator<…>` like the original version did, leaving the additional type as an implementation detail. Also, a similar solution is provided by the `either` crate [1], where the function body can return `Either::Left(std::iter::empty())` in one case and `Either::Right(…)` in the other, also hiding all of this behind an `impl Iterator<…>` return type. [1] https://docs.rs/either/latest/either/enum.Either.html https://docs.rs/either/latest/either/enum.Either.html

kawogi 2y ago

> However, this solution is not very ergonomic, as it requires the user of the function to first check if the returned value is Some(iterator) and only then iterate over the iterator. I'd use `flatten()` to iterate over this nested type.

sk11001 2y ago

I don't understand the people who look at this and go "yep, we should have more of this language". It's complexity for its own sake.

ryanjshaw 2y ago
I'm really confused... Is all of this just the equivalent of `Enumerable.Empty<T>` or `yield return` in C#?
- sk11001 2y ago
  So you do agree that other languages achieve the same thing with much less complexity?
  - tcfhgj 2y ago
    Not exactly the same thing though
- MereInterest 2y ago
  Not quite, because the user of those would need to perform dynamic dispatch in order to iterate over the result. In the article, the returned iterator has a type that is known to the compiler, and so the caller’s code can be optimized much more effectively.
- Measter 2y ago
  I'll ignore the option of returning a Vec or Option, as the article already went over why these options were rejected, and concentrate on the later options. Firstly the `std::iter::empty()` attempt: The issue they had here came down to the signature of the function. What they wanted to do was return an `impl Iterator<Item=&N>`. This means that the function isn't naming the specific type it returns[1], only stating that it's an Iterator that gives some `&N`s. However, the return type of this function is still one, specific type. You cannot return two different types that are both iterators. That's why this one failed. Boxing: Instead, we can return a `Box<dyn Iterator<Item=&N>>`. This is roughly equivalent to a function in C# returning an `IEnumerabale<N>`, in that the actual type is hidden, and the work is done doing dynamic dispatch. This allows you to return different kinds of iterators, because the specific type is hidden away inside the Box. The downside here is that you're doing a heap allocation. OptionIterator: This one is actually basically just the first Option case from earlier but wrapped up in a nicer-to-use interface for the user because it implements Iterator in a way that transparently handles the Option. [1] Additionally, it's not even possible to name the type of the iterator here due to the filter closure being unnamable.

Patryk27 2y ago

fwiw, Option already implements iterator (well, IntoIterator) - calling .into_iter() on an Option will get you an iterator, no need to create anything custom.

antonvs 2y ago
I wonder if that existed when this article was written in 2018.
- MereInterest 2y ago
  The footnotes mention that this solution was suggested by Reddit comments at the time.

orlp 2y ago

There is another alternative which may be significantly more efficient as it means the caller always gets back a direct iterator instead of an enum it must branch on: make a dummy empty hashmap with a static lifetime you can refer to. Then the implementation becomes static DUMMY: LazyLock<HashMap<N, (u128, u128)>> = LazyLock::new(HashMap::new()); fn neighbors_with_send_capacity_option(&self, a: N, capacity: u128) -> impl Iterator<Item=&N> { let node = self.nodes.get(&a).unwrap_or_else(|| &*DUMMY); node.keys().filter(move |b| self.get_send_capacity(&a, b) >= capacity) } Unfortunately we have to use a LazyLock for the static because HashMap::new isn't const. It only adds a single always-correctly-predicted branch that checks for initialization on access though, so it's fine.

blumenkraft 2y ago

Performance or not, this language is borderline unreadable.

the_mitsuhiko 2y ago

You don't need to do all that much, you can use `Option` with `into_iter` paired with `flatten` instead: fn neighbors_with_send_capacity(&self, a: N, capacity: u128) -> impl Iterator<Item = &N> + '_ { self.nodes .get(&a) .map(|m| m.keys()) .into_iter() .flatten() .filter(move |b| self.get_send_capacity(&a, b) >= capacity) } The only downside is that I believe `size_hint` is not properly forwarded.

OptionOfT 2y ago
Forgive the non-versioned link: https://doc.rust-lang.org/1.81.0/src/core/iter/adapters/flatten.rs.html#618 https://doc.rust-lang.org/1.81.0/src/core/iter/adapters/flat... I think it does work correctly.

realcr 2y ago

I stumbled upon this article today. My first thought was that this is an interesting question, then I continued reading and thought that the solution ideas are kind of crude. Then I noticed it was written at 2018, so I realized we should give the author a break. Finally I realized that it was me who wrote this, 6 years ago! So much has changed, but I believe the easy solution already existed back then. As people wrote in the comments here, one can iterate over an Option and then use flatten. Strange experience indeed.