[Haskell-cafe] Best bit LIST data structure
rrnewton at gmail.com
Fri Oct 7 16:52:41 CEST 2011
We are lucky to have a plethora of data structures out there. But it does
make choosing one off hackage difficult at times. In this case I'm *not*
looking for a O(1) access bit vector (Data.Vector.Unboxed seems to be the
choice there), but an efficient representation for a list of bits
Let's say that you want to represent tree indices as you walk down a binary
tree. [Bool] is a simple choice, you only add to the front of the list (0/1
= Left/Right), sharing the tails. But [Bool] is quite space inefficient.
Something like [Int] would allow packing the bits more efficiently. A Lazy
ByteString could amortize the space overhead even more... but in both cases
there's a tiny bit of work to do in wrapping those structures for per-bit
access. That's probably the right thing but I wanted to check to see if
there's something else recommended, perhaps more off-the-shelf.
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:
(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...)
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe