[Haskell-cafe] Best bit LIST data structure

[Roman Beslik]

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
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20111009/44e791d8/attachment.htm>