popCount is a method of Bits, not a FiniteBits

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|

popCount is a method of Bits, not a FiniteBits

Oleg Grenrus
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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

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

Oleg Grenrus
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
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

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

Zemyla
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 <[hidden email]> 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
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

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

Brent Yorgey
In reply to this post by Oleg Grenrus
Yeah, I would be really sad if I can't do popCount on Integer.

I suppose the issue really is whether you are allowed to have instances of Bits that have values with an infinite number of 1 bits, e.g. the 2-adic numbers.


On Sat, Nov 30, 2019, 9:21 AM Oleg Grenrus <[hidden email]> 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
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

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

Vanessa McHale-2
In reply to this post by Oleg Grenrus
I like this idea.

Cheers,
Vanessa McHale

On 11/30/19 3:17 PM, 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
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

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

Vanessa McHale-2
In reply to this post by Brent Yorgey

Would a Bits instance for 2-adic numbers be useful?

Cheers,
Vanessa

On 11/30/19 4:23 PM, Brent Yorgey wrote:
Yeah, I would be really sad if I can't do popCount on Integer.

I suppose the issue really is whether you are allowed to have instances of Bits that have values with an infinite number of 1 bits, e.g. the 2-adic numbers.


On Sat, Nov 30, 2019, 9:21 AM Oleg Grenrus <[hidden email]> 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
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

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

Brent Yorgey
In reply to this post by Zemyla
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 <[hidden email]> 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 <[hidden email]> 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
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

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

Oleg Grenrus

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 <[hidden email]> 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 <[hidden email]> 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
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

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

Edward Kmett-2
In reply to this post by Oleg Grenrus
I'm pretty strongly -1 on moving popCount. Both the Natural and the slightly more... interesting... Integer implementations of that method have turned out to be quite useful in practice.

-Edward

On Sat, Nov 30, 2019 at 7:17 AM Oleg Grenrus <[hidden email]> 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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

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

Edward Kmett-2
In reply to this post by Oleg Grenrus
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 <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> 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
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: 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 <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> 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
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

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

Oleg Grenrus
In reply to this post by Edward Kmett-2

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 <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> 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
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries