<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">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 <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>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"><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">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">david.feuer@gmail.com</a>
          <br>
          > <mailto:<a href="mailto:david.feuer@gmail.com" rel="noreferrer noreferrer noreferrer" target="_blank">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">zemyla@gmail.com</a><br>
          >     <mailto:<a href="mailto:zemyla@gmail.com" rel="noreferrer noreferrer noreferrer" target="_blank">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">yom@artyom.me</a><br>
          >         <mailto:<a href="mailto:yom@artyom.me" rel="noreferrer noreferrer noreferrer" target="_blank">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">mblazevic@stilo.com</a>
          <mailto:<a href="mailto:mblazevic@stilo.com" rel="noreferrer noreferrer noreferrer" target="_blank">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"><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">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">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">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">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">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">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">Libraries@haskell.org</a><br>
          >                     <mailto:<a href="mailto:Libraries@haskell.org" rel="noreferrer noreferrer noreferrer" target="_blank">Libraries@haskell.org</a>><br>
          >                     <mailto:<a href="mailto:Libraries@haskell.org" rel="noreferrer noreferrer noreferrer" target="_blank">Libraries@haskell.org</a><br>
          >                     <mailto:<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>
          ><br>
          ><br>
          >                   
           _______________________________________________<br>
          >                     Libraries mailing list<br>
          >                     <a href="mailto:Libraries@haskell.org" rel="noreferrer noreferrer noreferrer" target="_blank">Libraries@haskell.org</a>
          <mailto:<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>
          ><br>
          ><br>
          >               
           _______________________________________________<br>
          >                 Libraries mailing list<br>
          >                 <a href="mailto:Libraries@haskell.org" rel="noreferrer noreferrer noreferrer" target="_blank">Libraries@haskell.org</a>
          <mailto:<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>
          ><br>
          >           
           _______________________________________________<br>
          >             Libraries mailing list<br>
          >             <a href="mailto:Libraries@haskell.org" rel="noreferrer noreferrer noreferrer" target="_blank">Libraries@haskell.org</a>
          <mailto:<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>
          ><br>
          >         _______________________________________________<br>
          >         Libraries mailing list<br>
          >         <a href="mailto:Libraries@haskell.org" rel="noreferrer noreferrer noreferrer" target="_blank">Libraries@haskell.org</a>
          <mailto:<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>
          ><br>
          ><br>
          > _______________________________________________<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>
</blockquote></div></div></div>