Add NonEmptyMap and NonEmptySet to containers

[David Feuer]

The internals aren't sufficient, at present, to do this quite the way we
want. You're right that we should use the existing packages as guides.

On Sun, Apr 21, 2019, 3:46 PM Oleg Grenrus <oleg.grenrus at iki.fi> wrote:

> I’d like to see a package, which then could act as compat package,
> implementing these ideas. To my understanding `containers` exposes
> internals, so there shouldn’t be big technical challenges.
>
> I’d like an API to be validated first. Maybe the packages mentioned in the
> original post are such, in that case I’d think twice before adding anything
> that’s not there.
>
>
>
> 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:
>>
>>    1. 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.
>>    2. I made https://github.com/haskell/containers/pull/616 which just
>>    changes the types, to make sure UNPACK preserved the importance.
>>    3.
>>    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/1a4768b1/attachment.html>