<br>Yep, it is simple.  But I prefer to only use well-tested data structure libraries where I can!  Here&#39;s an example simple implementation (partial -- missing some common functions):<br><br><br>module Data.BitList <br>

  ( BitList<br>  , cons, head, tail, empty <br>  , pack, unpack, length, drop<br>  )<br>where<br><br>import Data.Int<br>import Data.Bits<br>import Prelude as P hiding (head,tail,drop,length)<br>import qualified Data.List as L<br>

import Test.HUnit<br><br>data BitList = One  {-# UNPACK #-} !Int {-# UNPACK #-} !Int64<br>             | More {-# UNPACK #-} !Int {-# UNPACK #-} !Int64 BitList<br> <br>instance Show BitList where <br> show bl = &quot;BitList &quot; ++ show (map (\b -&gt; case b of True -&gt; &#39;1&#39;; False -&gt; &#39;0&#39;) (unpack bl))<br>

-- show bl = &quot;pack &quot; ++ show (unpack bl)<br><br>empty :: BitList<br>empty = One 0 0<br><br>cons :: Bool -&gt; BitList -&gt; BitList<br>cons True  x@(One  64 _ )   = More 1 1 x<br>cons False x@(One  64 _ )   = More 1 0 x<br>

cons True  x@(More 64 bv _) = More 1 1 x<br>cons False x@(More 64 bv _) = More 1 0 x<br>cons True    (One   i bv)   = One  (i+1) (bv `setBit` i)<br>cons False   (One   i bv)   = One  (i+1) (bv           )<br>cons True    (More  i bv r) = More (i+1) (bv `setBit` i) r<br>

cons False   (More  i bv r) = More (i+1) (bv           ) r<br><br>-- TODO: May consider (More 0 _ _) representation to reduce extra<br>-- allocation when size of the BitList is fluctuating back and forth.<br><br>head :: BitList -&gt; Bool<br>

head (One  0 _   ) = error &quot;tried to take head of an empty BitList&quot;<br>head (More 0 _  r) = error &quot;BitList: data structure invariant failure!&quot;<br>head (One  i bv  ) = bv `testBit` (i-1)<br>head (More i bv r) = bv `testBit` (i-1)<br>

<br>tail :: BitList -&gt; BitList<br>tail (One  0 _   ) = error &quot;tried to take the tail of an empty BitList&quot;<br>tail (One  i bv  ) = One  (i-1) bv<br>tail (More 1 bv r) = r<br>tail (More i bv r) = More (i-1) bv r<br>

<br>pack :: [Bool] -&gt; BitList<br>pack  []   = One 0 0<br>pack (h:t) = cons h (pack t)<br><br>unpack :: BitList -&gt; [Bool] <br>unpack (One 0 _)     = []<br>unpack (One i bv)    = (bv `testBit` (i-1)) : unpack (One (i-1) bv)<br>

unpack (More 0 _ r)  =  unpack r<br>unpack (More i bv r) = (bv `testBit` (i-1)) : unpack (More (i-1) bv r)<br><br>drop :: Int -&gt; BitList -&gt; BitList<br>drop 0 bl           = bl<br>drop n bl | n &gt;= 64 = case bl of <br>

                One _ _    -&gt; error &quot;drop: not enough elements in BitList&quot;<br>            More i _ r -&gt; drop (n-i) r<br>drop n bl = case bl of <br>          One i  bv   -&gt; One  (i-n) bv<br>          More i bv r -&gt; More (i-n) bv r<br>

<br>length :: BitList -&gt; Int<br>length (One  i _)   = i<br>length (More i _ r) = i + length r<br><br><br>-- TODO: index, take, etc<br><br>-- TODO: functor instance, etc.<br><br><br>--------------------------------------------------------------------------------<br>

-- Testing:<br><br>t1 = pack (L.concat$ L.replicate 10 [True,False,True])<br><br>t2 = L.length $ unpack $ pack $ replicate 1000 True<br><br>t3 = pack $ replicate 1000 True<br>t4 = drop 500 t3<br>p3 = L.and (unpack t3)<br>

p4 = L.and (unpack t4)<br><br>t5 = iterate tail t4 !! 250<br>t5a = length t5<br>t5b = L.length (unpack t5)<br><br>tests :: Test<br>tests = <br>  TestList <br>    [ <br>      show t1 ~=? &quot;BitList \&quot;101101101101101101101101101101\&quot;&quot;<br>

    , t2  ~=? 1000<br>    , t5a ~=? 250<br>    , t5b ~=? 250<br>    , p3  ~=? True<br>    , p4  ~=? True<br>    ]<br><br>-- TODO: QuickCheck<br><br><br><br><div class="gmail_quote">On Sun, Oct 9, 2011 at 7:50 AM, Roman Beslik <span dir="ltr">&lt;<a href="mailto:beroal@ukr.net">beroal@ukr.net</a>&gt;</span> wrote:<br>

<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
  
    
  
  <div bgcolor="#FFFFFF" text="#000000">
    I am not aware of such a library, but IMHO this code will be very
    simple.<br>
    &gt; data Bits b =&gt; BitList b = BitList Int {- number of used
    bits in the next component -} b [b]<br>
    Write an isomorphism between @BitList b@ and @ListStep (BitList b)@<br>
    where<br>
    &gt; data ListStep e rc = Nil | Cons e rc<div><div></div><div class="h5"><br>
    <br>
    On 07.10.11 17:52, Ryan Newton wrote:
    </div></div><blockquote type="cite"><div><div></div><div class="h5">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" target="_blank">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>
      <br>
      <fieldset></fieldset>
      <br>
      </div></div><pre>_______________________________________________
Haskell-Cafe mailing list
<a href="mailto:Haskell-Cafe@haskell.org" target="_blank">Haskell-Cafe@haskell.org</a>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a>
</pre>
    </blockquote>
  </div>

<br>_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
<br></blockquote></div><br>