I am not aware of such a library, but IMHO this code will be very simple.
> data Bits b => BitList b = BitList Int {- number of used bits in the
next component -} b [b]
Write an isomorphism between @BitList b@ and @ListStep (BitList b)@
where
> data ListStep e rc = Nil | Cons e rc
On 07.10.11 17:52, Ryan Newton wrote:
Hi Cafe,
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 (cons,head,tail).
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:
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...)
Advice appreciated!
Thanks,
-Ryan
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
