Add NonEmptyMap and NonEmptySet to containers

[Oleg Grenrus]

Btw `partition` should return `These (NESet a) (NESet a)`: all match, all don’t match, or some match and some don’t.

http://hackage.haskell.org/package/nonempty-containers-0.1.1.0/docs/Data-Set-NonEmpty.html#v:partition

As said, I’d think twice before changing that API. Yet, These is problematic type. (I’m all in to put it into `base`, but I won’t write a proposal).

> On 19 Apr 2019, at 22.02, David Feuer <david.feuer at gmail.com> wrote:
> 
> There are a few functions that need names and places. In addition to
> 
>     insert :: Ord a => a -> NESet a -> NESet a -- or whatever type name
>     union :: Ord a => NESet a -> NESet a -> NESet a
> 
> we need
> 
>     insert?? :: Ord a => a -> Set a -> NESet a
>     union?? :: Ord a => Set a -> NESet a -> NESet a
> 
> For maps, we probably need unions on both sides to take care of different biases, and also need to deal with unionWith.
> 
> Another question: we currently have
> 
>     powerSet :: Set a -> Set (Set a)
> 
> Should we change that to
> 
>     powerSet :: Set a -> NESet (Set a)
> 
> or add a new function for that (where and by what name)?
> 
> For power sets of nonempty sets, there are several options, the most fundamental of which is probably
> 
>     ??? :: NESet a -> NESet (NESet a)
> 
> Splitting functions for nonempty sets/maps can produce results of various shapes. In particular, spanAntitone and partition for nonempty sets will produce two sets, at least one of which is non-empty. Do we want something like
> 
>     partition :: (a -> Bool) -> NESet a
>        -> Either (NESet a, Set a) (Set a, NESet a)
> 
> or should we stick with
> 
>     partition :: (a -> Bool) -> NESet a ->
>       (Set a, Set a)
> 
> or offer both by different names?
> 
>> On Thu, Apr 18, 2019, 7:15 PM John Cotton Ericson <John.Ericson at obsidian.systems> wrote:
>> In https://github.com/haskell/containers/issues/608 I proposed adding non-empty variants of Map and Set, analogous to Data.List.NonEmpty for List, to containers. semigroupoids demonstrates the many uses and structure of non-empty containers in general, and libraries such as https://github.com/mstksg/nonempty-containers and https://github.com/andrewthad/non-empty-containers demonstrate the interest in non-empty maps and sets in particular. My favorite use-case is that they're needed to "curry" containers: for example, Map (k0, k1) v is isomorphic not to Map k0 (Map k1 v) but to Map k0 (NonEmptyMap k1 v). I like this use-case because it comes from the containers       themselves.
>> 
>> Importantly, there's no good way to do this outside of containers; doing so leads to imbalancing / extra indirection, or massive code duplication. If one wraps the container was an extra value like Data.List.NonEmpty, one's left with an unavoidable extra indirection/imbalance. One can rectify this by copying and modifying the implementation of containers, but that's hardly maintainable; even as though the algorithms are the same, enough lines are touched that merging upstream containers is nigh impossible.
>> 
>> On the other hand, the non-empty containers can be elegantly and sufficiently implemented alongside their originals by taking the Bin constructor and breaking it out into it's own type, mutually recursive with the original. This avoids the indirection/imbalancing and code duplication problems: the algorithms work exactly as before creating the same trees (remember the UNPACK), and no code duplicated since the functions become mutually recursive matching the types.
>> 
>> To briefly summarize the thread:
>> 
>> I proposed the issue after performing this same refactor on the dependent-map package: https://github.com/obsidiansystems/dependent-map/tree/non-empty, a fork of containers.
>> I made https://github.com/haskell/containers/pull/616 which just changes the types, to make sure UNPACK preserved the importance.
>> https://gist.github.com/Ericson2314/58709d0d99e0c0e83ad266701cd71841 the benchmarks showed rather than degrading performance, PR 616 actually improved it.
>>  If there is preliminary consensus, I'll make a second PR on top which generalizes the functions like on my dependent-map branch.
>> Thanks,
>> 
>> John
>> 
>> _______________________________________________
>> Libraries mailing list
>> Libraries at haskell.org
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20190421/f5545408/attachment.html>