<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<p>I think the concrete benefit to GADTs is that the tags are not
monomorphized wrt the equality constraints. So I'd view this or
the unpacking sums things as two ways to end up with the 3 variant
tag and no extra indirection or partiality. So for those goals,
it's, adopt GADTs or modify GHC, pick your poison! :)</p>
<p>John<br>
</p>
<div class="moz-cite-prefix">On 4/25/19 2:04 PM, David Feuer wrote:<br>
</div>
<blockquote type="cite"
cite="mid:CAMgWh9thZvCC2dikDL4M8ShFc9iha4WTojqDefGZGMo2G73EzA@mail.gmail.com">
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<div dir="auto">
<div>Oh, I see what you mean. But then containers would depend
on GADTs, which is rather counter to tradition. And I don't
really see the benefit over a newtype and smart constructors
around the existing Seq type.<br>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">On Thu, Apr 25, 2019, 1:41
PM Zemyla <<a href="mailto:zemyla@gmail.com"
moz-do-not-send="true">zemyla@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">We could have a GADT for the FingerTree:
<div dir="auto"><br>
</div>
<div dir="auto">data Emptiness = E | NE</div>
<div dir="auto"><br>
</div>
<div dir="auto">data FingerTree e a where</div>
<div dir="auto"> EmptyT :: FingerTree 'E a</div>
<div dir="auto"> SingleT :: a -> FingerTree e a</div>
<div dir="auto"> DeepT :: !(Digit a) -> FingerTree
e' (Node a) -> !(Digit a) -> FingerTree e a</div>
<div dir="auto"><br>
</div>
<div dir="auto">And because Seq is a newtype wrapper
around FingerTree (Elem a) anyway, Seq and NonEmptySeq
would become newtype wrappers around FingerTree 'E
(Elem a) and FingerTree 'NE (Elem a). This avoids the
majority of the code duplication.</div>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">On Thu, Apr 25, 2019,
12:34 John Ericson
<a class="moz-txt-link-rfc2396E" href="mailto:john.ericson@obsidian.systems"><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>Thanks for the clarification, David. Sounds like
a good wait-and-see thing: after this lands,
Zemyla's proposal and the experience with
NonEmpty{Map,Set} can inform what Seq should end
up looking like.</p>
<p>John<br>
</p>
<div
class="m_-7438978158085895756m_6236643941480220562moz-cite-prefix">On
4/25/19 1:28 PM, David Feuer wrote:<br>
</div>
<blockquote type="cite">
<div dir="auto">No, a Seq can be Empty at the
bottom too. It's definitely not a mutually
recursive situation like Set or Map, and it's
not immediately a top-level one like IntSet or
IntMap. A nonempty sequence type would need
somewhat different functions for everything. In
most cases, the changes seem fairly
straightforward. I'm not sure about weird
functions like inits and tails. Some extra care
might be required for replicate.
<div dir="auto"><br>
</div>
<div dir="auto">I believe it would be possible
to restructure things to make the distinction
a top-level one, by using a possibly-empty
type for the top and a nonempty one below.
Zemyla has already identified some very solid
unrelated reasons to want to separate the tops
from the rest, but I'm somewhat concerned
about source code duplication with that
general approach. Even if we do that, it's not
clear to me that we can make a
non-empty/possibly-empty distinction without
incurring a performance penalty.</div>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">On Thu, Apr
25, 2019, 1:17 PM John Ericson <a
class="m_-7438978158085895756m_6236643941480220562moz-txt-link-rfc2396E"
href="mailto:john.ericson@obsidian.systems"
rel="noreferrer noreferrer" target="_blank"
moz-do-not-send="true"><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">I haven't looked into
`Seq` in addition to `Map` and `Set`, just <br>
`IntSet` and `IntMap`. But it might be a
similar thing? I take it that <br>
with `Seq` today only the root can be empty
and everything else is <br>
single or deep? That means we *would* just use
a single Maybe-like thing <br>
at the top level, no mutual recursion. But on
the other hand to make <br>
that to make that work efficiently we would
would need GHC to support <br>
unboxing sums, so 1 + 2 variants can become a
flat 3.<br>
<br>
Also, <a
href="https://github.com/haskell/containers/pull/616"
rel="noreferrer noreferrer noreferrer
noreferrer" target="_blank"
moz-do-not-send="true">https://github.com/haskell/containers/pull/616</a>
is now where the <br>
actual implementation is happening, not just
the datatype changes as <br>
before. Feel free to comment on the concrete
work in progress, everyone!<br>
<br>
John<br>
<br>
On 4/25/19 11:36 AM, Zemyla wrote:<br>
> A Seq has either Empty, Single, or Deep.
A NonEmptySeq would have just <br>
> Single or Deep.<br>
><br>
> On Thu, Apr 25, 2019, 09:55 David Feuer
<<a href="mailto:david.feuer@gmail.com"
rel="noreferrer noreferrer noreferrer"
target="_blank" moz-do-not-send="true">david.feuer@gmail.com</a>
<br>
> <mailto:<a
href="mailto:david.feuer@gmail.com"
rel="noreferrer noreferrer noreferrer"
target="_blank" moz-do-not-send="true">david.feuer@gmail.com</a>>>
wrote:<br>
><br>
> I don't see the benefit there, unless
you see a way to work it<br>
> into the representation.<br>
><br>
> On Thu, Apr 25, 2019, 10:53 AM Zemyla
<<a href="mailto:zemyla@gmail.com"
rel="noreferrer noreferrer noreferrer"
target="_blank" moz-do-not-send="true">zemyla@gmail.com</a><br>
> <mailto:<a
href="mailto:zemyla@gmail.com"
rel="noreferrer noreferrer noreferrer"
target="_blank" moz-do-not-send="true">zemyla@gmail.com</a>>>
wrote:<br>
><br>
> As long as we're doing this, can
we also add NonEmptySeq as well?<br>
><br>
> On Thu, Apr 25, 2019, 09:11
Artyom Kazak <<a
href="mailto:yom@artyom.me" rel="noreferrer
noreferrer noreferrer" target="_blank"
moz-do-not-send="true">yom@artyom.me</a><br>
> <mailto:<a
href="mailto:yom@artyom.me" rel="noreferrer
noreferrer noreferrer" target="_blank"
moz-do-not-send="true">yom@artyom.me</a>>>
wrote:<br>
><br>
> I'm -1 on any kind of |Map =
NEMap|.<br>
><br>
> An ordinary map and a
non-empty map are semantically<br>
> different. I believe that if
I non-empty maps were already<br>
> in |containers|, I would
pretty much always care whether a<br>
> |Map| I see in code is a
0-map or 1-map.<br>
><br>
> Similarly, I prefer |Int| and
|Word| instead of |Int| and<br>
> |Unsigned.Int|. (Luckily
that's already the case.)<br>
><br>
> We already have a precedent
with |Text| and |ByteString|,<br>
> where the lazy and the strict
versions are only<br>
> distinguished by the module
prefix. In my experience,<br>
> modules where both are used
are pretty common, and I end<br>
> up just introducing |type
LByteString = Lazy.ByteString|<br>
> in all my projects, because
otherwise I need to scroll to<br>
> the imports section whenever
I need to know which flavor<br>
> of bytestring is being used.
(Or if I'm reading haddocks,<br>
> I have to look at the link
because Haddock hides module<br>
> prefixes.)<br>
><br>
> "why not both" is even worse.
I still can't trust the<br>
> |Map|, but now I also have to
learn and remember that two<br>
> modules are the same.
Speaking from experience again –<br>
> most people seem to be
surprised by the fact that<br>
> |Data.Map.Lazy| and
|Data.Map.Strict| export the same<br>
> |Map| type. The proposed
module hierarchy would move<br>
> |containers| to the top of my
"packages that confuse<br>
> beginners" list, beating even
|aeson|.<br>
><br>
> As an aside, I wish we had a
proper interface for<br>
> container-like structures, or
at least a solution to name<br>
> scoping. I really like the
way Rust does it, for instance,<br>
> where certain functions can
be "attached" to a type – I'm<br>
> hesitant to call them
"methods" because Rust is not an OOP<br>
> language.<br>
> On Apr 25 2019, at 2:49 pm,
Mario Blažević<br>
> <<a
href="mailto:mblazevic@stilo.com"
rel="noreferrer noreferrer noreferrer"
target="_blank" moz-do-not-send="true">mblazevic@stilo.com</a>
<mailto:<a
href="mailto:mblazevic@stilo.com"
rel="noreferrer noreferrer noreferrer"
target="_blank" moz-do-not-send="true">mblazevic@stilo.com</a>>>
wrote:<br>
><br>
> On 2019-04-18 11:00 p.m.,
David Feuer wrote:<br>
><br>
> I'm in favor of the
proposal. I find the<br>
> isomorphism between
Map (a,b) v<br>
> and Map a
(NonemptyMap b v) very pleasant. The<br>
> fact that others have<br>
> written
less-performant implementations of this<br>
> idea is rather<br>
> convincing. The fact
that doing this removes<br>
> partial matches in
the<br>
> implementation is
nice. And I'll take performance<br>
> improvements where I<br>
> can get them. The
main question is the proper name<br>
> of the type. Just<br>
>
Data.Map.Nonempty.Map, or .NonemptyMap?
Should the<br>
> empty be capitalized?<br>
><br>
><br>
> There seems to be a
consensus for<br>
> Data.Map.NonEmpty.NEMap,
with the<br>
> type and the functions
slightly off the regular ones.<br>
> This design would<br>
> make it easier to use
regular and non-empty containers<br>
> together, but it<br>
> be annoying for the use
case of replacing all uses of<br>
> an existing<br>
> regular container with a
non-empty one. I'd rather<br>
> change just the<br>
> import declaration than
all occurrences of the type<br>
> name and functions.<br>
><br>
> I don't want to derail
the implementation with<br>
> bikeshedding, so I'm<br>
> just going to ask why not
both? The library can both<br>
> export the tweaked<br>
> names and add a module,
say Data.NonEmpty.Map.Lazy,<br>
> that exports the<br>
> type synonym Map = NEMap.
It would also rename all the<br>
> functions back to<br>
> their names from
Data.Map.Lazy.<br>
><br>
><br>
><br>
> On Thu, Apr 18, 2019,
7:15 PM John Cotton Ericson<br>
> <a
class="m_-7438978158085895756m_6236643941480220562moz-txt-link-rfc2396E"
href="mailto:John.Ericson@obsidian.systems"
rel="noreferrer noreferrer" target="_blank"
moz-do-not-send="true"><John.Ericson@obsidian.systems></a>
wrote:<br>
><br>
> In<br>
> <a
href="https://github.com/haskell/containers/issues/608"
rel="noreferrer noreferrer noreferrer
noreferrer" target="_blank"
moz-do-not-send="true">https://github.com/haskell/containers/issues/608</a>
I<br>
> proposed<br>
> adding non-empty
variants of Map and Set, analogous to<br>
> Data.List.NonEmpty
for List, to containers.<br>
> semigroupoids<br>
> demonstrates the many
uses and structure of<br>
> non-empty containers
in<br>
> general, and
libraries such as<br>
> <a
href="https://github.com/mstksg/nonempty-containers"
rel="noreferrer noreferrer noreferrer
noreferrer" target="_blank"
moz-do-not-send="true">https://github.com/mstksg/nonempty-containers</a>
and<br>
> <a
href="https://github.com/andrewthad/non-empty-containers"
rel="noreferrer noreferrer noreferrer
noreferrer" target="_blank"
moz-do-not-send="true">https://github.com/andrewthad/non-empty-containers</a><br>
> demonstrate the<br>
> interest in non-empty
maps and sets in particular.<br>
> My favorite<br>
> use-case is that
they're needed to "curry"<br>
> containers: for
example,<br>
> |Map (k0, k1) v| is
isomorphic not to |Map k0 (Map<br>
> k1 v)| but to<br>
> |Map k0 (NonEmptyMap
k1 v)|. I like this use-case<br>
> because it comes<br>
> from the containers
themselves.<br>
><br>
> Importantly, there's
no good way to do this<br>
> outside of
containers;<br>
> doing so leads to
imbalancing / extra indirection,<br>
> or massive code<br>
> duplication. If one
wraps the container was an<br>
> extra value like<br>
> Data.List.NonEmpty,
one's left with an unavoidable<br>
> extra<br>
>
indirection/imbalance. One can rectify this
by<br>
> copying and modifying<br>
> the implementation of
containers, but that's<br>
> hardly maintainable;<br>
> even as though the
algorithms are the same, enough<br>
> lines are touched<br>
> that merging upstream
containers is nigh impossible.<br>
><br>
> On the other hand,
the non-empty containers can be<br>
> elegantly and<br>
> sufficiently
implemented alongside their originals<br>
> by taking the Bin<br>
> constructor and
breaking it out into it's own<br>
> type, mutually<br>
> recursive with the
original. This avoids the<br>
>
indirection/imbalancing<br>
> and code duplication
problems: the algorithms work<br>
> exactly as before<br>
> creating the same
trees (remember the UNPACK), and<br>
> no code<br>
> duplicated since the
functions become mutually<br>
> recursive matching<br>
> the types.<br>
><br>
> To briefly summarize
the thread:<br>
><br>
> 1. I proposed the
issue after performing this same<br>
> refactor on the<br>
> dependent-map
package:<br>
> <a
href="https://github.com/obsidiansystems/dependent-map/tree/non-empty"
rel="noreferrer noreferrer noreferrer
noreferrer" target="_blank"
moz-do-not-send="true">https://github.com/obsidiansystems/dependent-map/tree/non-empty</a>,<br>
> a fork of containers.<br>
> 2. I made<br>
> <a
href="https://github.com/haskell/containers/pull/616"
rel="noreferrer noreferrer noreferrer
noreferrer" target="_blank"
moz-do-not-send="true">https://github.com/haskell/containers/pull/616</a><br>
> which just<br>
> changes the types, to
make sure UNPACK preserved<br>
> the importance.<br>
> 3.<br>
> <a
href="https://gist.github.com/Ericson2314/58709d0d99e0c0e83ad266701cd71841"
rel="noreferrer noreferrer noreferrer
noreferrer" target="_blank"
moz-do-not-send="true">https://gist.github.com/Ericson2314/58709d0d99e0c0e83ad266701cd71841</a><br>
> the benchmarks showed
rather than degrading<br>
> performance, PR 616<br>
> actually /improved/
it.<br>
><br>
> If there is
preliminary consensus, I'll make a<br>
> second PR on top<br>
> which generalizes the
functions like on my<br>
> dependent-map branch.<br>
><br>
> Thanks,<br>
><br>
> John<br>
><br>
>
_______________________________________________<br>
> Libraries mailing
list<br>
> <a
href="mailto:Libraries@haskell.org"
rel="noreferrer noreferrer noreferrer"
target="_blank" moz-do-not-send="true">Libraries@haskell.org</a><br>
> <mailto:<a
href="mailto:Libraries@haskell.org"
rel="noreferrer noreferrer noreferrer"
target="_blank" moz-do-not-send="true">Libraries@haskell.org</a>><br>
> <mailto:<a
href="mailto:Libraries@haskell.org"
rel="noreferrer noreferrer noreferrer"
target="_blank" moz-do-not-send="true">Libraries@haskell.org</a><br>
> <mailto:<a
href="mailto:Libraries@haskell.org"
rel="noreferrer noreferrer noreferrer"
target="_blank" moz-do-not-send="true">Libraries@haskell.org</a>>><br>
> <a
href="http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries"
rel="noreferrer noreferrer noreferrer
noreferrer" target="_blank"
moz-do-not-send="true">http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries</a><br>
><br>
><br>
>
_______________________________________________<br>
> Libraries mailing
list<br>
> <a
href="mailto:Libraries@haskell.org"
rel="noreferrer noreferrer noreferrer"
target="_blank" moz-do-not-send="true">Libraries@haskell.org</a>
<mailto:<a
href="mailto:Libraries@haskell.org"
rel="noreferrer noreferrer noreferrer"
target="_blank" moz-do-not-send="true">Libraries@haskell.org</a>><br>
> <a
href="http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries"
rel="noreferrer noreferrer noreferrer
noreferrer" target="_blank"
moz-do-not-send="true">http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries</a><br>
><br>
><br>
>
_______________________________________________<br>
> Libraries mailing list<br>
> <a
href="mailto:Libraries@haskell.org"
rel="noreferrer noreferrer noreferrer"
target="_blank" moz-do-not-send="true">Libraries@haskell.org</a>
<mailto:<a
href="mailto:Libraries@haskell.org"
rel="noreferrer noreferrer noreferrer"
target="_blank" moz-do-not-send="true">Libraries@haskell.org</a>><br>
> <a
href="http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries"
rel="noreferrer noreferrer noreferrer
noreferrer" target="_blank"
moz-do-not-send="true">http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries</a><br>
><br>
>
_______________________________________________<br>
> Libraries mailing list<br>
> <a
href="mailto:Libraries@haskell.org"
rel="noreferrer noreferrer noreferrer"
target="_blank" moz-do-not-send="true">Libraries@haskell.org</a>
<mailto:<a
href="mailto:Libraries@haskell.org"
rel="noreferrer noreferrer noreferrer"
target="_blank" moz-do-not-send="true">Libraries@haskell.org</a>><br>
> <a
href="http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries"
rel="noreferrer noreferrer noreferrer
noreferrer" target="_blank"
moz-do-not-send="true">http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries</a><br>
><br>
>
_______________________________________________<br>
> Libraries mailing list<br>
> <a
href="mailto:Libraries@haskell.org"
rel="noreferrer noreferrer noreferrer"
target="_blank" moz-do-not-send="true">Libraries@haskell.org</a>
<mailto:<a
href="mailto:Libraries@haskell.org"
rel="noreferrer noreferrer noreferrer"
target="_blank" moz-do-not-send="true">Libraries@haskell.org</a>><br>
> <a
href="http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries"
rel="noreferrer noreferrer noreferrer
noreferrer" target="_blank"
moz-do-not-send="true">http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries</a><br>
><br>
><br>
>
_______________________________________________<br>
> Libraries mailing list<br>
> <a href="mailto:Libraries@haskell.org"
rel="noreferrer noreferrer noreferrer"
target="_blank" moz-do-not-send="true">Libraries@haskell.org</a><br>
> <a
href="http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries"
rel="noreferrer noreferrer noreferrer
noreferrer" target="_blank"
moz-do-not-send="true">http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries</a><br>
</blockquote>
</div>
</blockquote>
</div>
</blockquote>
</div>
</blockquote>
</div>
</div>
</div>
</blockquote>
</body>
</html>