<html>
  <head>
    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
  </head>
  <body text="#000000" bgcolor="#FFFFFF">
    <p>I'd refine the documentation of `Bits` class to say that it's a
      class for integral types with finite count of bits toggled, i.e.
      finite popCount.<br>
      Than many things work out, except complementInteger is actually
      used.<br>
      <br>
      It's not a big change codewise: <a
        href="https://gitlab.haskell.org/ghc/ghc/merge_requests/2261">https://gitlab.haskell.org/ghc/ghc/merge_requests/2261</a>
      (GHC actually uses complementInteger for something itself).<br>
      <br>
      Without complement, Bits Natural would total instance, without
      partial methods. If complement for Integer is very important, then
      I'd propose to introduce classes to form diamond shape:<br>
      <br>
      -- instance can be defined for Integer<br>
      class Bits b => Complement b where<br>
          complement :: b -> b<br>
      <br>
      -- instance can be defined for Natural<br>
      class Bits b => PopCount b where<br>
          popCount :: b -> b<br>
      <br>
      class Complement b => FiniteBits b where<br>
          ...<br>
      <br>
      I think this is worth the trouble, this wart should been fixed
      when Natural was brought to base. And in fact, because of
      complement is in Bits, clearBit :: Natural -> Natural is broken
      in base-4.9.0.0 bundled with GHC-8.0: It went unnoticed, because
      there were default implementation using complement. If Haskell2020
      will happen, it really should explain what the complement ::
      Natural -> Natural does otherwise. Haskell2010 just mentions
      that there is Bits Integer. For the report defense, popCount isn't
      in its Bits version.<br>
      <br>
      So, we made warts by both adding popCount to Bits and adding
      Natural Bits instance. Let's just fix them.<br>
      <br>
      - Oleg<br>
    </p>
    <div class="moz-cite-prefix">On 1.12.2019 5.21, Brent Yorgey wrote:<br>
    </div>
    <blockquote type="cite"
cite="mid:CAH0njdvfaLSSDXe7UWQBddXqoz06bLjYu3Q-0yFmH302mYJ13w@mail.gmail.com">
      <meta http-equiv="content-type" content="text/html; charset=UTF-8">
      <div dir="ltr">
        <div>A few points:</div>
        <div><br>
        </div>
        <div>1. The Bits instance for Integer essentially already
          behaves as if they are the 2-adic numbers.  For example, if
          you use testBit you can discover that (-2 :: Integer) is
          treated as if it were an infinite sequence of 1's followed by
          a single 0.</div>
        <div>2. However, because testBit takes an Int index, instances
          of Bits actually can't have an infinite number of 1 bits---at
          least not in practice---since you cannot observe anything past
          the (maxBound :: Int)th bit.</div>
        <div>3. Currently, popCount on negative Integer values satisfies
          popCount (-x) = -(popCount x)  which does not seem very well
          motivated and does not match the way negative values are
          presented via testBit.</div>
        <div><br>
        </div>
        <div>I am strongly -1 on moving popCount to FiniteBits. 
          popCount on positive Integers is useful and well-defined.  I
          am mildly +1 on Zemlya's proposal to change the behavior of
          popCount for negative Integer values, though I am not sure it
          is really worth the trouble.</div>
        <div><br>
        </div>
        <div>-Brent<br>
        </div>
      </div>
      <br>
      <div class="gmail_quote">
        <div dir="ltr" class="gmail_attr">On Sat, Nov 30, 2019 at 10:10
          AM 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:0px 0px 0px
          0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
          <div dir="auto">popCount is a perfectly sensible method for
            Natural, and it could theoretically become one for Integer
            as well if we say that, whenever there's an infinite number
            of 1s and a finite number of 0s, then the result is -(1 +
            count of 0s), as though it were maxBound :: Word bits in
            size and merely converted to an Int (a sensible assumption,
            considering memory limits). The results for types where
            there can be both infinite 0s and 1s should still be an
            error.</div>
          <br>
          <div class="gmail_quote">
            <div dir="ltr" class="gmail_attr">On Sat, Nov 30, 2019,
              09:21 Oleg Grenrus <<a
                href="mailto:oleg.grenrus@iki.fi" target="_blank"
                moz-do-not-send="true">oleg.grenrus@iki.fi</a>>
              wrote:<br>
            </div>
            <blockquote class="gmail_quote" style="margin:0px 0px 0px
              0.8ex;border-left:1px solid
              rgb(204,204,204);padding-left:1ex">Although, popCount for
              Integer/Natural kind of makes sense, as they <br>
              aren't infinite list of [Bit]s, but smarter structure.<br>
              <br>
              On 30.11.2019 17.17, Oleg Grenrus wrote:<br>
              > I propose to change it to be member of FiniteBits<br>
              ><br>
              > I recall, there was a proposal to remove bitSize from
              Bits, so it's an <br>
              > opportunity to introduce another small, yet breaking
              change at the <br>
              > same time.<br>
              ><br>
              > Discussion time 2 week.<br>
              ><br>
              > - Oleg<br>
              ><br>
              > _______________________________________________<br>
              > Libraries mailing list<br>
              > <a href="mailto:Libraries@haskell.org"
                rel="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" target="_blank"
                moz-do-not-send="true">http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries</a><br>
              _______________________________________________<br>
              Libraries mailing list<br>
              <a href="mailto:Libraries@haskell.org" rel="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" target="_blank"
                moz-do-not-send="true">http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries</a><br>
            </blockquote>
          </div>
          _______________________________________________<br>
          Libraries mailing list<br>
          <a href="mailto:Libraries@haskell.org" 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" target="_blank" moz-do-not-send="true">http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries</a><br>
        </blockquote>
      </div>
    </blockquote>
  </body>
</html>