<div dir="auto">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.</div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sun, Apr 21, 2019, 3:46 PM Oleg Grenrus <<a href="mailto:oleg.grenrus@iki.fi">oleg.grenrus@iki.fi</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto"><div>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.</div><div><br></div><div>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.</div><div><br></div><div><br></div><div><div dir="ltr"><br>On 19 Apr 2019, at 22.02, David Feuer <<a href="mailto:david.feuer@gmail.com" target="_blank" rel="noreferrer">david.feuer@gmail.com</a>> wrote:<br><br></div><blockquote type="cite"><div dir="ltr"><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 <<a href="mailto:John.Ericson@obsidian.systems" target="_blank" rel="noreferrer">John.Ericson@obsidian.systems</a>> 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_3330698600717114880m_8248091223326010508moz-txt-link-freetext" href="https://github.com/haskell/containers/issues/608" rel="noreferrer noreferrer" target="_blank">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_3330698600717114880m_8248091223326010508moz-txt-link-freetext" href="https://github.com/mstksg/nonempty-containers" rel="noreferrer noreferrer" target="_blank">https://github.com/mstksg/nonempty-containers</a>
and <a class="m_3330698600717114880m_8248091223326010508moz-txt-link-freetext" href="https://github.com/andrewthad/non-empty-containers" rel="noreferrer noreferrer" target="_blank">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" rel="noreferrer noreferrer" target="_blank">https://github.com/obsidiansystems/dependent-map/tree/non-empty</a>,
a fork of <tt>containers</tt>.</li>
<li>I made <a class="m_3330698600717114880m_8248091223326010508moz-txt-link-freetext" href="https://github.com/haskell/containers/pull/616" rel="noreferrer noreferrer" target="_blank">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" rel="noreferrer noreferrer" target="_blank">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" rel="noreferrer noreferrer" target="_blank">Libraries@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries" rel="noreferrer noreferrer noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries</a><br>
</blockquote></div>
</div></blockquote><blockquote type="cite"><div dir="ltr"><span>_______________________________________________</span><br><span>Libraries mailing list</span><br><span><a href="mailto:Libraries@haskell.org" target="_blank" rel="noreferrer">Libraries@haskell.org</a></span><br><span><a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries" target="_blank" rel="noreferrer">http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries</a></span><br></div></blockquote></div></div></blockquote></div>