[Haskell-cafe] Best bit LIST data structure

[Daniel Fischer]

On Sunday 09 October 2011, 15:54:14, Joachim Breitner 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.h
> > tml#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

says info gmp:

  `_mp_size' and `_mp_alloc' are `int', although `mp_size_t' is
usually a `long'.  This is done to make the fields just 32 bits on some
64 bits systems, thereby saving a few bytes of data space but still
providing plenty of range.

So it seems to be GMP itself.