popCount is a method of Bits, not a FiniteBits
Oleg Grenrus
oleg.grenrus at iki.fi
Tue Dec 3 18:45:14 UTC 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 <oleg.grenrus at iki.fi
> <mailto: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
>> <mailto: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
>> <mailto: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 <mailto:Libraries at haskell.org>
>> > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>> _______________________________________________
>> Libraries mailing list
>> Libraries at haskell.org <mailto:Libraries at haskell.org>
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>
>> _______________________________________________
>> Libraries mailing list
>> Libraries at haskell.org <mailto:Libraries at haskell.org>
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org <mailto: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/20191203/6f2f9fc1/attachment.html>
More information about the Libraries
mailing list