Re: popCount is a method of Bits, not a FiniteBits

3 Dec 2019

      I made two MRs for GHC:

- new class Bits b => Complement b in 
https://gitlab.haskell.org/ghc/ghc/merge_requests/2261
- or also class Bits b => PopCount b in 
https://gitlab.haskell.org/ghc/ghc/merge_requests/2270

The patches are quite direct, nothing surprising. GHC compiles fine 
itself, Few tests are failing: I'll fix them, if  we decide to go with 
either.

- Oleg

On 2.12.2019 18.47, Edward Kmett wrote:
...
I'm not averse to the idea of factoring out complementation into a 
separate class to make the Bits instance for Natural total. It strikes 
me as a laudable goal and it comes very close to encoding what Stone 
called a "Generalized Boolean Algebra" in the 30s, which hints to me 
that we might be onto the right abstraction here. Consider me a 
weak +1 there.
-Edward
On Mon, Dec 2, 2019 at 6:01 AM Oleg Grenrus mailto:oleg.grenrus@iki.fi> wrote:
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.
    Than many things work out, except complementInteger is actually used.
It's not a big change codewise:
    https://gitlab.haskell.org/ghc/ghc/merge_requests/2261 (GHC
    actually uses complementInteger for something itself).
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:
-- instance can be defined for Integer
    class Bits b => Complement b where
        complement :: b -> b
-- instance can be defined for Natural
    class Bits b => PopCount b where
        popCount :: b -> b
class Complement b => FiniteBits b where
        ...
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.
So, we made warts by both adding popCount to Bits and adding
    Natural Bits instance. Let's just fix them.
- Oleg
On 1.12.2019 5.21, Brent Yorgey wrote:
...
A few points:
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.
    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.
    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.
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.
-Brent
On Sat, Nov 30, 2019 at 10:10 AM Zemyla mailto:zemyla@gmail.com> wrote:
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.
On Sat, Nov 30, 2019, 09:21 Oleg Grenrus mailto:oleg.grenrus@iki.fi> wrote:
Although, popCount for Integer/Natural kind of makes
            sense, as they
            aren't infinite list of [Bit]s, but smarter structure.
On 30.11.2019 17.17, Oleg Grenrus wrote:
            > I propose to change it to be member of FiniteBits
            >
            > I recall, there was a proposal to remove bitSize from
            Bits, so it's an
            > opportunity to introduce another small, yet breaking
            change at the
            > same time.
            >
            > Discussion time 2 week.
            >
            > - Oleg
            >
            > _______________________________________________
            > Libraries mailing list
            > Libraries@haskell.org mailto:Libraries@haskell.org
            > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
            _______________________________________________
            Libraries mailing list
            Libraries@haskell.org mailto:Libraries@haskell.org
            http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
        Libraries mailing list
        Libraries@haskell.org mailto:Libraries@haskell.org
        http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
    Libraries mailing list
    Libraries@haskell.org mailto:Libraries@haskell.org
    http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries