Hi Cafe,<br><br>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&#39;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).<br>

<br>Let&#39;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.<br>

 <br>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&#39;s a tiny bit of work to do in wrapping those structures for per-bit access.  That&#39;s probably the right thing but I wanted to check to see if there&#39;s something else recommended, perhaps more off-the-shelf.<br>

<br>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:<br>    <a href="http://haskell.org/ghc/docs/latest/html/libraries/base/src/Data-Bits.html#setBit">http://haskell.org/ghc/docs/latest/html/libraries/base/src/Data-Bits.html#setBit</a> <br>

(I don&#39;t know if it&#39;s possible to do better.  From quick googling GMP seems to use an array of &quot;limbs&quot; rather than a chunked list, so maybe there&#39;s no way to treat large Integers as a list and update only the front...)<br>

<br>Advice appreciated!<br><br>Thanks,<br>  -Ryan<br>