[Haskell-cafe] Best bit LIST data structure

[Thomas Schilling]

On 9 October 2011 14:54, Joachim Breitner <mail at joachim-breitner.de> wrote:
> Hi,
>
> Am Freitag, den 07.10.2011, 10:52 -0400 schrieb Ryan Newton:
>> What about just using the Data.Bits instance of Integer?  Well,
>> presently, the setBit instance for very large integers creates a whole
>> new integer, shifts, and xors:
>>
>> http://haskell.org/ghc/docs/latest/html/libraries/base/src/Data-Bits.html#setBit
>> (I don't know if it's possible to do better.  From quick googling GMP
>> seems to use an array of "limbs" rather than a chunked list, so maybe
>> there's no way to treat large Integers as a list and update only the
>> front...)
>
> interesting idea. Should this be considered a bug in ghc? (Not that it
> cannot represent the result, but that it crashes even out of ghci):
>
> $ ghci
> GHCi, version 7.0.4: http://www.haskell.org/ghc/  :? for help
> Loading package ghc-prim ... linking ... done.
> Loading package integer-gmp ... linking ... done.
> Loading package base ... linking ... done.
> Prelude> :m + Data.Bits
> Prelude Data.Bits> setBit 0 (2^63-1::Int)
> gmp: overflow in mpz type
> Abgebrochen

Yes, that's a bug.  GMP shouldn't call abort(), but it should be
turned into a Haskell exception.  It probably doesn't make much of a
difference in practise, but "safe" could should never crash GHC.