On Fri, Jul 27, 2012 at 03:06:04PM -0400, Edward Kmett wrote:
> There is currently no way to know whether or not calling

> Data.Bits.bitSizewill crash your program.

>
> I propose extending the Bits class to include:
>
> hasBitSize :: Bits b => b -> Bool
>
> such that it returns False for Integer and True for the other instances

Can you give an example of a situation in which you would use
hasBitSize, and do something useful if it returned False?

The following can only work if bitSize is well defined.

traverseBits :: (Applicative f, Bits b) => (Bool -> f Bool) -> b -> f b

traverseBits f b = snd . Prelude.foldr step (bitSize b - 1,0) <$> traverse (f . testBit b) [0 .. bitSize b - 1] where

step True (n,r) = (n - 1, setBit r n)

step _ (n,r) = (n - 1, r)

to work around this I've had to use:

traverseBits :: (Applicative f, Bits b) => (Bool -> f Bool) -> b -> f b

traverseBits f b = Prelude.foldr step 0 <$> traverse g bits

where

g n = (,) n <$> f (testBit b n)

bits = Prelude.takeWhile hasBit [0..]

hasBit n = complementBit b n /= b -- test to make sure that complementing this bit actually changes the value

step (n,True) r = setBit r n

step _ r = r

where I'm manually probing each bit to see that changing it changes the value.

Used with the other combinators in lens the former just crashes when you use

foldMapOf :: ((c -> Const m d) -> a -> Const m b) -> (c -> m) -> a -> m

foldMapOf l f = getConst . l (Const . f)

toListOf :: ((c -> Const [c] d) -> a -> Const [c] b) -> a -> [c]

toListOf l = foldMapOf l return

Now when we use it with an explicit signature both of these can do reasonable things:

ghci> toListOf traverseBits (5 :: Int)

[True,False,True,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False,False]

But with defaulting choosing Integer

ghci> toListOf traverseBits 5

the former instance will crash, whereas the latter properly returns an infinite lazy list

It would be much nicer not to have to probe using complementBit creating ever larger temporary integers just to see if the list of valid bit positions hadn't been exhausted.

Then I could test at the start to know whether I should use [0..] or [0..bitSize-1] and get away with much less code and much less unnecessary memory allocation.

-Edward

Would it be better to move bitSize into a separate class?

I don't think so. Ultimately, you should be able to know for every numeric type if it has a fixed or variable number of bits. In a perfect world 'd rather just have bitSize return a Maybe that way we don't have to truck with partial functions in the API.

However, the case for just adding hasBitSize is that it avoids breaking existing code.

> since the vast majority of instances are finite, it may be reasonable to
> set the default definition to
>
> hasBitSize _ = False

Did you mean True?

Yes

Either way, I think I would personally prefer not to have a default, so
that people need to actually check existing instances.

Also perfectly reasonable.

-Edward