<div dir="auto">To be clear, I was only talking about module names and not implementation. NEMap/NESet don't sound so bad to me.</div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Fri, Apr 19, 2019, 12:17 AM David Feuer <<a href="mailto:david.feuer@gmail.com">david.feuer@gmail.com</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">Definitely sets as well.<div dir="auto"><br></div><div dir="auto">Set (a, b) ~= Map a (NonEmpty.??Set b)</div><div dir="auto"><br></div><div dir="auto">I'm leaning toward calling the types NEMap and NESet (or similar). Yes, that's a bit disgusting. It would be prettier, perhaps, to just use the names Map and Set, but that runs into a nasty implementation challenge with mutual recursion. I don't want .hs-boot or fancy backpack tricks in containers, and I don't want horribly awkward newtypes cluttering up the implementation if I can avoid it.</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Fri, Apr 19, 2019, 12:08 AM chessai . <<a href="mailto:chessai1996@gmail.com" target="_blank" rel="noreferrer">chessai1996@gmail.com</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">I'm also +1.<div dir="auto"><br></div><div dir="auto">Why not:</div><div dir="auto"><br></div><div dir="auto">Data.Map.NonEmpty</div><div dir="auto">Data.Map.NonEmpty.Lazy</div><div dir="auto">Data.Map.NonEmpty.Strict</div><div dir="auto"><br></div><div dir="auto">If sets are added as well:</div><div dir="auto"><br></div><div dir="auto">Data.Set.NonEmpty</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, Apr 18, 2019, 11:01 PM David Feuer <<a href="mailto:david.feuer@gmail.com" rel="noreferrer noreferrer" target="_blank">david.feuer@gmail.com</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'm in favor of the proposal. I find the isomorphism between Map (a,b) v and Map a (NonemptyMap b v) very pleasant. The fact that others have written less-performant implementations of this idea is rather convincing. The fact that doing this removes partial matches in the implementation is nice. And I'll take performance improvements where I can get them. The main question is the proper name of the type. Just Data.Map.Nonempty.Map, or .NonemptyMap? Should the empty be capitalized?<br><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_3671432618169455434m_2604097169053858666m_7838893762733659534m_5352604634035215918m_8248091223326010508moz-txt-link-freetext" href="https://github.com/haskell/containers/issues/608" rel="noreferrer noreferrer noreferrer 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_3671432618169455434m_2604097169053858666m_7838893762733659534m_5352604634035215918m_8248091223326010508moz-txt-link-freetext" href="https://github.com/mstksg/nonempty-containers" rel="noreferrer noreferrer noreferrer noreferrer noreferrer" target="_blank">https://github.com/mstksg/nonempty-containers</a>
and <a class="m_3671432618169455434m_2604097169053858666m_7838893762733659534m_5352604634035215918m_8248091223326010508moz-txt-link-freetext" href="https://github.com/andrewthad/non-empty-containers" rel="noreferrer noreferrer noreferrer 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 noreferrer 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_3671432618169455434m_2604097169053858666m_7838893762733659534m_5352604634035215918m_8248091223326010508moz-txt-link-freetext" href="https://github.com/haskell/containers/pull/616" rel="noreferrer noreferrer noreferrer 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 noreferrer 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 noreferrer noreferrer noreferrer" target="_blank">Libraries@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries" rel="noreferrer noreferrer noreferrer noreferrer noreferrer noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries</a><br>
</blockquote></div></div></div>
_______________________________________________<br>
Libraries mailing list<br>
<a href="mailto:Libraries@haskell.org" rel="noreferrer noreferrer noreferrer" target="_blank">Libraries@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries" rel="noreferrer noreferrer noreferrer noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries</a><br>
</blockquote></div>
</blockquote></div>
</blockquote></div>