Should NonEmptyList have its own data type?

[coltfred]

NonEmptyList is currently type NonEmptyList[A] = OneAnd[A, List]. There has been discussion about writing a version of it that is more so that we could support a more list like interface (++, tails, sortBy, etc).

How does everyone feel about it? Is it worth doing?

[julien-truffaut]

it will be convenient to define custom methods but what about NonEmptySet, NonEmptyMap, NonEmptyVector ...

I recall that @stew wanted to use a separate project for "fancy" data structure

[aryairani]

I'm not necessarily suggesting it, but another possibility would be to define List-like syntax for OneAnd[A, List] etc.

[coltfred]

@refried I had thought about that... Doesn't seem like an awful idea. Does anyone have reasons why that's an awful idea?

[aryairani]

@coltfred The main down-side I can think of is that it requires a non-obvious import to get the NonEmptyList syntax and another import to get the List TC instances. (Maybe they could be combined). Up-side is not having to define NonEmptyList TC instances.

[stew]

@julien-truffaut I did recently start the https://github.com/stew/dogs project, but I think NonEmptyList is going to end up staying here, because we want to use it in cats itself.

[aryairani]

@stew lol at bird beaks

[julien-truffaut]

@stew could we use OneAnd[List] within cats and define all NonEmpty classes in dogs? I don't know if it makes sense

[adelbertc]

On a related note I wonder if NonEmpty would be a better name than OneAnd

[aryairani]

@adelbertc I like this.

[adelbertc]

Going back, I think NonEmptyList has enough usages to warrant it being in Cats. If people agree with that, I don't think it's a stretch to want to include Vector, if only for it's faster ++ operation in the case of say, using it as the Semigroup for Validated (in which case maybe we change (or add) ValidatedNel with ValidatedNev) and it's fast random access properties.

Personally I've only found myself reaching for a non-empty Set once, and never for a NonEmptyMap. On that note, both of those have unique characteristics that may warrant their own special implementation instead of using something like OneAnd.

Perhaps we can (somehow) just abstract between List and Vector and provide a data type for NonEmpty versions of those, and then move the OneAnd/NonEmpty data type out to an alternative library, perhaps along with a NonEmptySet and/or NonEmptyMap (which probably covers most usages of non-empty data structures).

Thoughts?

[non]

@adelbertc I think you might be right. I would say that we should not be putting data types in cats-core unless we need to use them to implement the type classes, instances, or similar.

So maybe a good place to start would be trying to add all these types to Dogs and then seeing which seem the most useful in Cats? For example, I'm working on a non-empty linked list which interoperates efficiently with a related possibly-empty linked list type.

We can always "promote" data types from Dogs to Cats if we want to use them there, or if there is broad consensus that they would be useful to almost everyone.

[coltfred]

Ok, it sounds like @non has taken over the quest for NonEmptyList and that NonEmptySet is no longer a Cats related concern. I've successfully pawned my work off! 😆

You guys should close #123 and I pushed my NonEmptySet changes (which are incomplete) to a branch so they can live on in case we want to pull them into @stew's dogs. https://github.com/coltfred/cats/tree/nonEmptySet

[non]

For a first-pass at what I'm imagining (at least for list) see here: typelevel/cats-collections#5

[aryairani]

My 2¢, NonEmptySet is every bit as important as NonEmptyList. Here's an 8 month old version as syntax on OneAnd. https://gist.github.com/refried/9b68a08ff24640b86fb2

[paulp]

I trust that everyone realizes there are a ton of hidden costs to using type aliases when compared with an "equivalent" trait. You embrace a raft of additional compiler bugs - any given decision within the compiler which is made based on the type has a decent chance of failing to see through a type alias, or failing to see through a singleton type in a type alias, or a type alias in a singleton type, or etc etc. The more of these are fixed, the more unpleasant the remaining ones become, because you get that much further in some ill-fated design before the walls close in on you.

It is especially debilitating when substitution is involved. See for instance one of my personal favorites, SI-8177. JIRA is presently refusing to load the 60ish older comments, but if it comes around they're worth reading so as not to underestimate what's at stake.

[aryairani]

@paulp I didn't realize it, although I guess I've seen hints of it.

@non Indirectly related, I recently wished for a distinct: NonEmptyList[A] method on scalaz.NonEmptyList[A], and realized it could be implemented more generally on scalaz.Foldable1 (but still returning a NonEmptyList[A]).

How would you see a method like this fitting into the cats ecosystem (i.e. cats.Reducible) given that NonEmptyList is tentatively in dogs. Options I see are:

• add implicit syntax on Reducible to another library
  • the library is dogs
  • the library isn't dogs
• have a NonEmptyList in cats, and then the method could be added to Reducible
• no NonEmptyList in cats, and the method could be added to Reducible but it needs Applicative and SemigroupK and Foldable1 to decide its return type
• CanBuildFrom 😭
• other? :-)

[coltfred]

Cats should definitely have NEL in it IMO. The more I've been using it the more I find the OneAnd solution lacking.

[ceedubs]

Yesterday @non and I discussed this for quite a while, and we both seemed to settle on the idea that there should be a cats.data.NonEmptyList class specialized to List.

The OneAnd approach is lacking, more difficult to reason about, and isn't really a very general solution (it doesn't work for Set or Map, and treating Vector like a Cons isn't very efficient). We'd be in favor of removing OneAnd from cats once there is a specialized NonEmptyList.

Since ValidatedNel is so commonly used, we think that this should be addressed before cats 1.0. We'd be open to the idea of NonEmptyVector (though for performance reasons we may not want this to be a Cons-like case class as it is with OneAnd) and perhaps some other NonEmpty* types, but we wouldn't block a 1.0 release on them.

[mpilquist]

👍 I'd like NonEmptyVector to stay though, even if in 1.0 it is a cons.

[ceedubs]

It sounds like we've arrived at a decision here. I'm closing in favor of #1087, #1088, and #1089.

[vn971]

// If it's not clear, NonEmptyList is a case class now. Hence the closed issue.

[boggle]

I'm encountering NonEmptySets all the time; is there a particular reason why we get NEList and NEVector but not a NESet? I've yet to see a real-world case for NEMap though. Of course that's just my corner of the world.

[vn971]

@boggle you should probably raise a separate ticket for that..? (This one is from Sep 2015.)

[adelbertc]

@boggle see: #123