popCount is a method of Bits, not a FiniteBits

[Carter Schonwald]

I’d wanna first see how that factoring plays out,

Strong -1 on dropping pop count  instance

Curious to poke at / think about the class refactoring.

There’s definitely some ways this stuff could be evolved.  Just need
clarity on the cost vs benefits etc.

On Mon, Dec 2, 2019 at 11:48 AM Edward Kmett <ekmett at gmail.com> 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 <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
>>
> _______________________________________________
> 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/a9191880/attachment.html>