Creating an empty iterator of a certain type in Rust (2018)
freedomlayer.org
freedomlayer.org
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.
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.
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)
}
https://doc.rust-lang.org/1.81.0/src/core/iter/adapters/flat...
I think it does work correctly.
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`.
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)
}
I'd use `flatten()` to iterate over this nested type.
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.
If you want slow dynamic dispatch and extra heap allocs like in Java or C# or whatever, that option is available. But Rust would be laughed out of the systems programming table if its iterator abstraction were that inefficient.
In the future, please avoid resorting to strawman arguments stemming from ignorance.
The thing that I find baffling is when people start throwing Rust at problems that don't need it like backend services and APIs, CLI tooling, games. I'll take your word that the complexity is necessary in systems programming - the problem is that people are carrying that complexity everywhere else too, and it doesn't seem like a tradeoff that's worth it. Rust doesn't gradually expose you to concepts depending on your use case for the language, once something is needed for the lowest level use case, it becomes additional complexity which contaminates all other use cases.
Great. Use those languages. Don't criticise rust for not being one of those languages
> people are carrying that complexity everywhere else too, and it doesn't seem like a tradeoff that's worth it.
Yes, there are people who have used Rust in places where a higher level language would be more appropriate. However rust has characteristics beyond raw performance that make it often a compelling choice in areas outside of systems programming. The complexity of the language brings benefits that may or may not suit a particular use case. Any criticism of necessity or otherwise of its complexity is just noise without talking about what you want to use it for.
I do. I'm not criticizing Rust, I'm failing to understand the people who choose to use it in places where it doesn't belong. Over time that's becoming an increasingly larger part of all the people who use it.
I opened with this, yes. I think people who use Rust for everyhing have poor taste.
I guess, once you know it, the linked problem really doesn't seem that complex. Once you know it, you know the idiomatic solution will look like this commenter's: https://news.ycombinator.com/item?id=41472874
If it were any simpler to write, I'm not sure you'd have any confidence the code was doing what it should be doing/what you thought was on the label.
But I also strongly disagree with the quoted notion. One would usually ease their way into returning iterators. Much more likely is one would do the simple thing and allocate an empty Vec for awhile, or an Option<Vec<T>>, like the author even tried first, and then decide you want to be fast or, more likely, ask whether this is what was holding you back, and try to decide how to do that.
> It's complexity for its own sake.
I do agree that Rust can be complex, but this is not complex. This is just the Rust way. Right now, complex Rust, to me, is refactoring the code of others. The code of others has a certain weight/concreteness in Rust that sometimes makes it hard to mold into something else. Rust makes small refactorings a breeze. It makes some large refactorings feel almost impossible.
The underlying type systems allows you to implement the same monomorphized iterators like in Rust, which some third-party libraries do.
The main limitations are at the language level - the lack of associated types and high order functions being opaque means that for nested iterators you may end up writing unwieldy generic signature by hand, and instead of lambda - manually writing a value-delegate-like struct. In a brighter tomorrow, it will be a matter of the language doing so on your behalf, but in either case there is nothing preventing another guest language or even C# itself in the future having identical iterator abstraction implementation to Rust within the existing type system (unlikely to happen in C# as-is because it would be a huge breaking change, the compiler is getting better at inlining and devirtualization so in the simpler cases it may become not needed).
You can optimize it later if it actually matters.
I've done this type of thing plenty of times when working on non-critical code where I just wanted to get something to quickly work without thinking about it too hard.
Perhaps famous for how well they optimize away the extrinsic overhead of the iterator concept. Not really famous for how well they optimize compared to just writing the loop and iterate code naively with indices or what have you.
And the latter makes it far easier to adapt to use SIMD, sentinel values, etc.
Please avoid implying that Rust has the objectively best tradeoffs for all situations. (See how annoying it is to be on the receiving end of condescension?)
Not really famous for how well they optimize compared to just writing
the loop and iterate code naively with indices or what have you.
Hey, let's talk about the complexity here, I think there's reason for it! They wanted to use static dispatch so that the return type has more information on the logic being returned and is able to optimize better while also avoiding allocations at all. Reduced the original example (that doesn't compile) here: https://play.rust-lang.org/?version=stable&mode=debug&editio...
If you want to do what other languages do, you can just use dyn Trait (trait objects, dynamic dispatch) instead of impl Trait (concrete objects, static dispatch). It's less efficient and requires allocations, which is what other languages usually do, but all you have to do is wrap it in a Box. Example: https://play.rust-lang.org/?version=stable&mode=debug&editio...
If you want to use static dispatch, then you have to look a bit more into it, there's a lot of discussion in the comments already but for this specific case Option's into_iter + flatten works fine, while Either is a more generic solution or you could even implement your own iterator for this use-case if you wanted to.
I'd say the complexity here comes from the explicitness and being forced to make a choice: Don't care about performance? Ok, just wrap it in a Box and call it a day. Wants to take the most out of it? Then you'll have to look deeper into it.