popCount is a method of Bits, not a FiniteBits

[Brent Yorgey]

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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20191130/75791d03/attachment.html>