[ANN] Non-empty Collections

Hi everyone, I'm happy to announce the release of nonempty-collections, which provides three powerful types, NEVec, NESet, and NEMap, as well as macros for constructing them, nev!, nes!, and nem!. These types are guaranteed to never be empty.

While other libraries related to non-emptiness exist, their main focus is on vectors. This new crate extends the idea to other types, and also provides NonEmptyIterator for iterating while preserving non-emptiness. So something like this "just works":

let v: NEVec<_> = nev![1, 2, 3].into_nonempty_iter().map(|n| n + 1).collect();


1 Like

The NonEmptyIterator API is a bit confusing to me, since after a call to next, the iterator can actually become empty. I don’t have concrete API design improvement suggestions, but with the current API, at least the documentation should clearly point out that you’re not supposed to call first after any calls to next, and looking through a handful of implementors, it seems like doing so will indeed result in a variety of (safe but) unexpected behavior, depending on the iterator type in question.


The implementation of impl<I> IntoIterator for Take<I> looks wrong to me, as it ignores the size and returns the full inner iterator.

Looking through the crate it seems like it might be a reasonable idea to think about whether IntoIterator should be a super-trait of NonEmptyIterator in general. This would avoid creating issues like currently FlatMap not implementing IntoIterator, (even though it could, I think…), or FlatMap’s NonEmptyIterator implementation having stricter bounds than the .flat_map method of NonEmptyIterator method.

Also, I’m confused as to why Once<T> uses Vec<T> instead of something without heap allocations, since it’s only ever going to have at most one element, if I’m not mistaken… right?

This is certainly a known flaw. In certain other docstrings the user is indeed warned not to call first after manually advancing the Iterator. The main use of first is in FromNonEmptyIterator and is not really intended to be called by the user.

The Take impl there might be a bug, let me check. Yup, a bug. Fixed.

FlatMap missing IntoIterator is probably an oversight. Yup, fixed.

Once uses a Vec was a change I made this morning. It used to be a bare T but had an extra T: Default constraint on it due to a use of std::mem::take, which I did not like. Using a Vec instead was an attempted solution.

Overall, I had explored a number of different designs for the relationship between the Iterator world of types and the NonEmptyIterator world. In the end I settled on "reimplement the API", although that's not to say that there isn't some superior representation floating in the mathematical ether.

Using Option<T> is fine in this case.

1 Like

I've fixed the issues and released 0.1.1.

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.