popCount is a method of Bits, not a FiniteBits

[Edward Kmett]

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 <oleg.grenrus at 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 <zemyla at 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 <oleg.grenrus at 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 at haskell.org
>>> > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>> _______________________________________________
>>> Libraries mailing list
>>> Libraries at haskell.org
>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>>
>> _______________________________________________
>> Libraries mailing list
>> Libraries at haskell.org
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20191202/6fae9501/attachment.html>