&gt; data <b>(Bits b) =&gt;</b> BitList b<br>Is deprecated and soon to be removed from the language.<br><br>I fail to understand. Why not just:<br>&gt; data BitList b = Nil | BitList Int b (BitList b)<br>??<br><br><div class="gmail_quote">

2011/10/9 Roman Beslik <span dir="ltr">&lt;<a href="mailto:beroal@ukr.net">beroal@ukr.net</a>&gt;</span><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>