<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<p>In <a class="moz-txt-link-freetext"
href="https://github.com/haskell/containers/issues/608">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="moz-txt-link-freetext"
href="https://github.com/mstksg/nonempty-containers">https://github.com/mstksg/nonempty-containers</a>
and <a class="moz-txt-link-freetext"
href="https://github.com/andrewthad/non-empty-containers">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">https://github.com/obsidiansystems/dependent-map/tree/non-empty</a>,
a fork of <tt>containers</tt>.</li>
<li>I made <a class="moz-txt-link-freetext"
href="https://github.com/haskell/containers/pull/616">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">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>
</body>
</html>