<div dir="auto">There are a few functions that need names and places. In addition to<div dir="auto"><br></div><div dir="auto">    insert :: Ord a => a -> NESet a -> NESet a -- or whatever type name</div><div dir="auto">    union :: Ord a => NESet a -> NESet a -> NESet a</div><div dir="auto"><br></div><div dir="auto">we need</div><div dir="auto"><br></div><div dir="auto">    insert?? :: Ord a => a -> Set a -> NESet a</div><div dir="auto">    union?? :: Ord a => Set a -> NESet a -> NESet a</div><div dir="auto"><br></div><div dir="auto">For maps, we probably need unions on both sides to take care of different biases, and also need to deal with unionWith.</div><div dir="auto"><br></div><div dir="auto">Another question: we currently have</div><div dir="auto"><br></div><div dir="auto">    powerSet :: Set a -> Set (Set a)</div><div dir="auto"><br></div><div dir="auto">Should we change that to</div><div dir="auto"><br></div><div dir="auto"><span style="font-family:sans-serif">    powerSet :: Set a -> NESet (Set a)</span><br></div><div dir="auto"><span style="font-family:sans-serif"><br></span></div><div dir="auto"><span style="font-family:sans-serif">or add a new function for that (where and by what name)?</span></div><div dir="auto"><span style="font-family:sans-serif"><br></span></div><div dir="auto"><span style="font-family:sans-serif">For power sets of nonempty sets, there are several options, the most fundamental of which is probably</span></div><div dir="auto"><span style="font-family:sans-serif"><br></span></div><div dir="auto"><span style="font-family:sans-serif">    ??? :: NESet a -> NESet (NESet a)</span></div><div dir="auto"><span style="font-family:sans-serif"><br></span></div><div dir="auto"><font face="sans-serif">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</font></div><div dir="auto"><font face="sans-serif"><br></font></div><div dir="auto"><font face="sans-serif">    partition :: (a -> Bool) -> NESet a</font></div><div dir="auto"><font face="sans-serif">       -> Either (NESet a, Set a) (Set a, NESet a)</font></div><div dir="auto"><font face="sans-serif"><br></font></div><div dir="auto"><font face="sans-serif">or should we stick with</font></div><div dir="auto"><font face="sans-serif"><br></font></div><div dir="auto"><span style="font-family:sans-serif">    partition :: (a -> Bool) -> NESet a -></span><font face="sans-serif"><br></font></div><div dir="auto"><span style="font-family:sans-serif">      (Set a, Set a)</span></div><div dir="auto"><span style="font-family:sans-serif"><br></span></div><div dir="auto"><span style="font-family:sans-serif">or offer both by different names?</span></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, Apr 18, 2019, 7:15 PM John Cotton Ericson <John.Ericson@obsidian.systems> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
  
    
  
  <div text="#000000" bgcolor="#FFFFFF">
    <p>In <a class="m_8248091223326010508moz-txt-link-freetext" href="https://github.com/haskell/containers/issues/608" target="_blank" rel="noreferrer">https://github.com/haskell/containers/issues/608</a>
      I proposed adding non-empty variants of <tt>Map</tt> and <tt>Set</tt>,
      analogous to <tt> Data.List.NonEmpty</tt> for List, to <tt>containers</tt>.
      <tt>semigroupoids</tt> demonstrates the many uses and structure of
      non-empty containers in general, and libraries such as <a class="m_8248091223326010508moz-txt-link-freetext" href="https://github.com/mstksg/nonempty-containers" target="_blank" rel="noreferrer">https://github.com/mstksg/nonempty-containers</a>
      and <a class="m_8248091223326010508moz-txt-link-freetext" href="https://github.com/andrewthad/non-empty-containers" target="_blank" rel="noreferrer">https://github.com/andrewthad/non-empty-containers</a>
      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, <code>Map (k0, k1) v</code> is isomorphic not to <code>Map
        k0 (Map k1 v)</code> but to <code>Map k0 (NonEmptyMap k1 v)</code>.
      I like this use-case because it comes from the containers
      themselves. </p>
    <ul>
    </ul>
    <ul>
    </ul>
    <p>Importantly, there's no good way to do this outside of <tt>containers</tt>;
      doing so leads to imbalancing / extra indirection, or massive code
      duplication. If one wraps the container was an extra value like <tt>
        Data.List.NonEmpty</tt>, 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.<br>
    </p>
    <p>On the other hand, the non-empty containers can be elegantly and
      sufficiently implemented alongside their originals by taking the <tt>Bin</tt>
      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.</p>
    <p>To briefly summarize the thread:<br>
    </p>
    <ol>
      <li>I proposed the issue after performing this same refactor on
        the <tt>dependent-map</tt> package: <a href="https://github.com/obsidiansystems/dependent-map/tree/non-empty" target="_blank" rel="noreferrer">https://github.com/obsidiansystems/dependent-map/tree/non-empty</a>,
        a fork of <tt>containers</tt>.</li>
      <li>I made <a class="m_8248091223326010508moz-txt-link-freetext" href="https://github.com/haskell/containers/pull/616" target="_blank" rel="noreferrer">https://github.com/haskell/containers/pull/616</a>
        which just changes the types, to make sure UNPACK preserved the
        importance.</li>
      <li><a href="https://gist.github.com/Ericson2314/58709d0d99e0c0e83ad266701cd71841" target="_blank" rel="noreferrer">https://gist.github.com/Ericson2314/58709d0d99e0c0e83ad266701cd71841</a>
        the benchmarks showed rather than degrading performance, PR 616
        actually <i>improved</i> it.<br>
      </li>
    </ol>
     If there is preliminary consensus, I'll make a second PR on top
    which generalizes the functions like on my <tt>dependent-map</tt>
    branch.<br>
    <p>Thanks,</p>
    <p>John<br>
    </p>
  </div>

_______________________________________________<br>
Libraries mailing list<br>
<a href="mailto:Libraries@haskell.org" target="_blank" rel="noreferrer">Libraries@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries" rel="noreferrer noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries</a><br>
</blockquote></div>