Discussion: Change the specification of rotateL for non-finite Bits, or move rotations to FiniteBits

David Feuer

29 Sep 2014 29 Sep '14

11:33 a.m.

Problem: The documentation currently specifies that for non-finite Bits instances, rotate is the same as shift. This seems reasonable for Integer rotateR, but very strange for Integer rotateL. In particular: rotateL 5 (-1 :: Int) = -1 rotateL 5 (-1 :: Integer) = 16 Based on the concept that Integers represent two's complement out to infinity, rotating a negative integer left should fill with 1s, but it fills with 0s instead. Solutions: As stated in the subject, I think one reasonable solution is just to make rotateL fill with 1s for negative non-finite instances, and the other is to move rotations to FiniteBits, as was done with bitSize.

Attachments:

attachment.html (text/html — 756 bytes)

Show replies by date

Edward Kmett

29 Sep 29 Sep

11:41 a.m.

It does seem like it should rotate in 1s, but if it does so, what happens when it rotates out something that isn't all 1s into a negative number or all 0s into a positive number? We'd expect `rotateL n . rotateR n = id = rotateR n . rotateL n` for the finite cases. but you can't rotate out the digits "up at infinity". So even this is messy. =/ Ideally we *would* move rotate/rotateL/rotateR to FiniteBits, but there is a huge upgrade/migration cost associated with that. All user specified instances break in a way that requires CPP and it diverges from the standard further. On Mon, Sep 29, 2014 at 11:33 AM, David Feuer wrote:

...

Problem:

The documentation currently specifies that for non-finite Bits instances, rotate is the same as shift. This seems reasonable for Integer rotateR, but very strange for Integer rotateL. In particular:

rotateL 5 (-1 :: Int) = -1 rotateL 5 (-1 :: Integer) = 16

Based on the concept that Integers represent two's complement out to infinity, rotating a negative integer left should fill with 1s, but it fills with 0s instead.

Solutions:

As stated in the subject, I think one reasonable solution is just to make rotateL fill with 1s for negative non-finite instances, and the other is to move rotations to FiniteBits, as was done with bitSize.

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

David Feuer

11:55 a.m.

On Sep 29, 2014 11:41 AM, "Edward Kmett" wrote:

...

It does seem like it should rotate in 1s, but if it does so, what happens

when it rotates out something that isn't all 1s into a negative number or all 0s into a positive number?

...

We'd expect `rotateL n . rotateR n = id = rotateR n . rotateL n` for the

finite cases.

...

but you can't rotate out the digits "up at infinity".

So even this is messy. =/

You're absolutely right. Integer couldn't support that. You could, however, have a Bits instance newtype RotInteger = RotInteger {number::Integer, atInfinity::Integer} That would be able to support rotations into and out of the bits "at infinity".

...

Ideally we would move rotate/rotateL/rotateR to FiniteBits, but there is a huge upgrade/migration cost associated with that. All user specified instances break in a way that requires CPP and it diverges from the standard further.

Well, the approach taken for bitSize would work here too. Deprecate the three names, leaving them in place. Add three new ones to FiniteBits, using correct but somewhat slow defaults (implementing rotations using shifting and masking). The FiniteBits dictionary is already growing from one member to three, so adding another few should be okay, right?

Milan Straka

11:58 a.m.

Hi all, I agree with Edward that although rotate{,L,R} should really live in FiniteBits, it is probably too costly to move them there. When staying in Bits, I find the "rotate is shift for infinite" semantics the most appealing -- rotations do not make really sense for infinite sequences, so I would not pretend they are rotating the sequence. Cheers, Milan

...

-----Original message----- From: Edward Kmett Sent: 29 Sep 2014, 11:41

It does seem like it should rotate in 1s, but if it does so, what happens when it rotates out something that isn't all 1s into a negative number or all 0s into a positive number?

We'd expect `rotateL n . rotateR n = id = rotateR n . rotateL n` for the finite cases.

but you can't rotate out the digits "up at infinity".

So even this is messy. =/

Ideally we *would* move rotate/rotateL/rotateR to FiniteBits, but there is a huge upgrade/migration cost associated with that. All user specified instances break in a way that requires CPP and it diverges from the standard further.

On Mon, Sep 29, 2014 at 11:33 AM, David Feuer wrote:

...
Problem:

The documentation currently specifies that for non-finite Bits instances, rotate is the same as shift. This seems reasonable for Integer rotateR, but very strange for Integer rotateL. In particular:

rotateL 5 (-1 :: Int) = -1 rotateL 5 (-1 :: Integer) = 16

Based on the concept that Integers represent two's complement out to infinity, rotating a negative integer left should fill with 1s, but it fills with 0s instead.

Solutions:

As stated in the subject, I think one reasonable solution is just to make rotateL fill with 1s for negative non-finite instances, and the other is to move rotations to FiniteBits, as was done with bitSize.

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

...

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

David Feuer

2:28 p.m.

Thinking about this some more, I ran into something else to chew on. It would seem to make a certain amount of sense to have instance (Bits b) => Bits (Seq b) with .&., .|., and xor defined using a zero-prepending zipWith variant. but there are a few challenges relating to size. Specifically: 1. The specification indicates that finiteBitSize and bitSizeMaybe are supposed to return a result based only on the type of their argument. Clearly, that will not work for this. 2. There is no obviously correct size to use for zeroBits and bit. One approach, of course, is to define something wonky like newtype SeqN (n::Nat) a = SeqN (Seq a) and then use instance (Bits b) => Bits (SeqN n b) but that gives a different, more limited type than one might expect.

John Lato

3:10 p.m.

Do you have a use case for this instance? I don't think I would ever want it. Also I think the behavior is too unspecified, and trying to specify it more precisely will inevitably lead to a much less useful instance. In this instance I might prefer we focus on problems we have already rather make new ones. Also +1 for rotate acting like shift for infinite types, for the reasons Milan gave. John L. On Sep 29, 2014 11:28 AM, "David Feuer" wrote:

...

Thinking about this some more, I ran into something else to chew on. It would seem to make a certain amount of sense to have

instance (Bits b) => Bits (Seq b)

with .&., .|., and xor defined using a zero-prepending zipWith variant.

but there are a few challenges relating to size. Specifically:

1. The specification indicates that finiteBitSize and bitSizeMaybe are supposed to return a result based only on the type of their argument. Clearly, that will not work for this. 2. There is no obviously correct size to use for zeroBits and bit.

One approach, of course, is to define something wonky like

newtype SeqN (n::Nat) a = SeqN (Seq a)

and then use

instance (Bits b) => Bits (SeqN n b)

but that gives a different, more limited type than one might expect. _______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

David Feuer

3:54 p.m.

No particular use case. Just trying to look at where the boundaries lie. I think rejecting such things is an argument for putting rotations in `FiniteBits`, though. On Mon, Sep 29, 2014 at 3:10 PM, John Lato wrote:

...

Do you have a use case for this instance? I don't think I would ever want it. Also I think the behavior is too unspecified, and trying to specify it more precisely will inevitably lead to a much less useful instance. In this instance I might prefer we focus on problems we have already rather make new ones.

Also +1 for rotate acting like shift for infinite types, for the reasons Milan gave.

John L.

On Sep 29, 2014 11:28 AM, "David Feuer" wrote:

...
Thinking about this some more, I ran into something else to chew on. It would seem to make a certain amount of sense to have

instance (Bits b) => Bits (Seq b)

with .&., .|., and xor defined using a zero-prepending zipWith variant.

but there are a few challenges relating to size. Specifically:

1. The specification indicates that finiteBitSize and bitSizeMaybe are supposed to return a result based only on the type of their argument. Clearly, that will not work for this. 2. There is no obviously correct size to use for zeroBits and bit.

One approach, of course, is to define something wonky like

newtype SeqN (n::Nat) a = SeqN (Seq a)

and then use

instance (Bits b) => Bits (SeqN n b)

but that gives a different, more limited type than one might expect. _______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

Edward Kmett

4:47 p.m.

Seq Bool and [Bool] aren't really correct Bits instances, let alone Bits a => Bits (Seq a) (the latter really only even starts to make sense for FiniteBits a => Bits (Seq a), because you have to enumerate bits. I also think defining such SeqN types (which _are_ legal) should really be left up to the end user if they want them. There are lots of points in the design space (Do you trim excess 0-bit only entries from on the right? Leave them? etc.) it involves messy types, and there is little to be gained by standardizing on one of them. We don't have to include everything someone may someday want in base. -Edward On Mon, Sep 29, 2014 at 2:28 PM, David Feuer wrote:

...

Thinking about this some more, I ran into something else to chew on. It would seem to make a certain amount of sense to have

instance (Bits b) => Bits (Seq b)

with .&., .|., and xor defined using a zero-prepending zipWith variant.

but there are a few challenges relating to size. Specifically:

1. The specification indicates that finiteBitSize and bitSizeMaybe are supposed to return a result based only on the type of their argument. Clearly, that will not work for this. 2. There is no obviously correct size to use for zeroBits and bit.

One approach, of course, is to define something wonky like

newtype SeqN (n::Nat) a = SeqN (Seq a)

and then use

instance (Bits b) => Bits (SeqN n b)

but that gives a different, more limited type than one might expect. _______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

3886

Age (days ago)

3886

Last active (days ago)

List overview

Download

7 comments

4 participants

participants (4)

David Feuer
Edward Kmett
John Lato
Milan Straka