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@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@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries