NonEmptyVector and NonEmptyMap

[TimPigden]

Hi, My data models make extensive use of NonEmptyVector from cats. And I have desire for NonEmptyMap that's not based on sorted data. Would they have a place?
I notice the NonEmptySet here is not based on TreeSet - unlike cats where for reasons I don't really understand they can't use Set
"The problem is that the std lib Set type is unparametric and a non-empty version purely based on that one wouldn't find a place in cats. Any set based on hashing would have to take a Hash[A]."
Could predude NonEmptyVector and Map simply wrap the default Scala ones?
(in which case I could knock it up pretty easily)

[adamgfraser]

ZIO already has a NonEmptyChunk data type that you can use as a replacement for NonEmptyVector. A NonEmptyMap that wraps a Map similar to how NonEmptySet wraps a Set would certainly be welcome.

[TimPigden]

Adam - if you remember I had a shot at benchmarking Chunk for a hackathon about a year ago (sadly I never got to finish). at the time the result was that performance of chunk could be better or much worse than vector for random access, depending on how the Chunks were created - whereas Vector is consistent. Has that changed?

[adamgfraser]

There has been significant work on performance since then though random access will always be faster if you materialize it first.

[TimPigden]

ok, nice - I've just been looking at chunk. I'm planning a big cats->prelude splurge on my code base for a few weeks time. I'll do the NonEmptyMap then

[adamgfraser]

Great! Let me know if you need any help!

[TimPigden]

I'm looking at this now. I've been thinking, I ought to do the NonEmptyVector at the same time - the reason being anyone coming over to prelude from cats may be using NonEmptyVector and not be entirely trusting that Chunks are going to give them exactly the same or better performance characteristics.
And - a weakness in the cats NonEmptySet implementation is it entirely based on TreeSet, which is
a) less efficient and b) requires creating of an ordering.
You've gone the other way and only create a HashSet implementation. So if I can make it without too much disruption I'll see if we can have a NonEmpty TreeSet and TreeMap as alternative implementations.
@adamgfraser

[TimPigden]

@adamgfraser ok, a bit of help required.
I downloaded master
I've written all the code, I've absolutely no idea what I'm doing with respect to cross-compiles and so on (we simply don't need it at work)
or what version of zio I should be running.
Is there a simple hack for the build environment so I can compile and test under my current dev setup without all this scalanative and js stuff? And how am I supposed to make it work with scala3?
i'm currently running 2.13.8 and either zio2 or 3
I think I can manage to ensure the actual collection stuff is compatible with 2.12 style collections

[adamgfraser]

If you just run SBT and go to one of the JVM projects you can test that on just the JVM and the latest Scala version. Eventually it will need to pass on all Scala versions but I don't think there should be a lot of issues there.

I worry that a NonEmptyVector is not really a data type we recommend using (we should just use NonEmptyChunk instead) and there is significant boilerplate code there in re-exporting all the collection methods. I would rather just make our optimal solution for a general purpose collection type fast than have two implementations for essentially the same thing.

For NonEmptySet, I think a NonEmptySet should just wrap anything that honors the Set interface and it doesn't really need to care what implementation is used under the hood, through when we construct our own set we would probably use a hash set. If you wanted to implemented a NonEmptySortedSet that provides additional operators when the set is sorted I think that could make sense.

[TimPigden]

__so what I've done atm is have an object NonEmptySet.NonEmptySortedSet that has a similar set of constructors to NonEmptySet, though each with an implicit scala.math.ordering. As it constructs the NonEmptySortedSet it constructs with a TreeSet which is otherwise invisible. So the functional difference is that the iterators (or .toChunk or whatever) come out sorted - and obviously use a different internal structure. The way stuff is made internally uses the fact that library operations on treeSet generate another TreeSet automatically__ This is good enough for my purposes And fine - yes agree about NonEmptyVector - there'd be a lot of boilerplate

[TimPigden]

wrt to the NonEmptyMap - I can't replicate (or don't know how to) the set of methods like ``` implicit val NonEmptySetCommutativeEither: CommutativeEither[NonEmptySet] ``` because Map as a pair of type params. Any suggestions (other than not bothering)

…

On Sat, 19 Feb 2022 at 17:54, Tim Pigden ***@***.***> wrote: so what I've done atm is have an object NonEmptySet.NonEmptySortedSet that has a similar set of constructors to NonEmptySet, though each with an implicit scala.math.ordering. As it constructs the NonEmptySortedSet it constructs with a TreeSet which is otherwise invisible. So the functional difference is that the iterators (or .toChunk or whatever) come out sorted - and obviously use a different internal structure. The way stuff is made internally uses the fact that library operations on treeSet generate another TreeSet automatically On Sat, 19 Feb 2022 at 17:00, Adam Fraser ***@***.***> wrote: > If you just run SBT and go to one of the JVM projects you can test that > on just the JVM and the latest Scala version. Eventually it will need to > pass on all Scala versions but I don't think there should be a lot of > issues there. > > I worry that a NonEmptyVector is not really a data type we recommend > using (we should just use NonEmptyChunk instead) and there is > significant boilerplate code there in re-exporting all the collection > methods. I would rather just make our optimal solution for a general > purpose collection type fast than have two implementations for essentially > the same thing. > > For NonEmptySet, I think a NonEmptySet should just wrap anything that > honors the Set interface and it doesn't really need to care what > implementation is used under the hood, through when we construct our own > set we would probably use a hash set. If you wanted to implemented a > NonEmptySortedSet that provides additional operators when the set is > sorted I think that could make sense. > > — > Reply to this email directly, view it on GitHub > <#836 (comment)>, > or unsubscribe > <https://github.com/notifications/unsubscribe-auth/AAJWHJ64DGO3CCAM6QYQ23TU37EC3ANCNFSM5KVBDGDA> > . > Triage notifications on the go with GitHub Mobile for iOS > <https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> > or Android > <https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub>. > > You are receiving this because you authored the thread.Message ID: > ***@***.***> > -- Tim Pigden Optrak Distribution Software Limited +44 (0)1992 517100 http://www.linkedin.com/in/timpigden http://optrak.com Optrak Distribution Software Ltd is a limited company registered in England and Wales. Company Registration No. 2327613 Registered Offices: Suite 6,The Maltings, Hoe Lane, Ware, SG12 9LR England This email and any attachments to it may be confidential and are intended solely for the use of the individual to whom it is addressed. Any views or opinions expressed are solely those of the author and do not necessarily represent those of Optrak Distribution Software Ltd. If you are not the intended recipient of this email, you must neither take any action based upon its contents, nor copy or show it to anyone. Please contact the sender if you believe you have received this email in error.

-- Tim Pigden Optrak Distribution Software Limited +44 (0)1992 517100 http://www.linkedin.com/in/timpigden http://optrak.com Optrak Distribution Software Ltd is a limited company registered in England and Wales. Company Registration No. 2327613 Registered Offices: Suite 6,The Maltings, Hoe Lane, Ware, SG12 9LR England This email and any attachments to it may be confidential and are intended solely for the use of the individual to whom it is addressed. Any views or opinions expressed are solely those of the author and do not necessarily represent those of Optrak Distribution Software Ltd. If you are not the intended recipient of this email, you must neither take any action based upon its contents, nor copy or show it to anyone. Please contact the sender if you believe you have received this email in error.

[TimPigden]

Actually on second thoughts I ought do the range stuff, so I'll need a parallel full implementation

[TimPigden]

oops - ignore the pull request. I forgot the additional tree methods!

[TimPigden]

ok, just to note what's been done:
3 new things added NonEmptySortedSet, NonEmptyMap and NonEmptySortedMap
NonEmptySortedSet is almost exactly the same as NonEmptySet - I tried to factor out the common stuff but all the types became an unreadable nightmare and I gave up. Likewise NonEmptyMap and NonEmptySortedMap are mostly the same.
NonEmpySortedSet has 2 todos in the code - I couldn't figure out what to do with CommutativeEither and Invariant with the implicit needed for the SortedSet.
And I didn't really understand any of that bit or the NonEmptySortedSetSyntax - so they will need to be checked I think.

sorted.. max/min and range type operations didn't need anything because they all subset the parent object and thus can produce empty collections - so defaulting to the underlying type is the correct behaviour there.

Finally I added some groupBy operations to NonEmptyMap - because groupby, will by definition produce things of NonEmpty type and so it seemed useful (I have such operations in my current codebase)