<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
I am not aware of such a library, but IMHO this code will be very
simple.<br>
> data Bits b => 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>
> data ListStep e rc = Nil | Cons e rc<br>
<br>
On 07.10.11 17:52, Ryan Newton wrote:
<blockquote
cite="mid:CACYs5AZ9=Ct_HVKvgRQ2Kg8Lons6=vfZk6SD2Amv=i+1ge_06A@mail.gmail.com"
type="cite">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'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'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'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.<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 moz-do-not-send="true"
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'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...)<br>
<br>
Advice appreciated!<br>
<br>
Thanks,<br>
-Ryan<br>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
Haskell-Cafe mailing list
<a class="moz-txt-link-abbreviated" href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a>
<a class="moz-txt-link-freetext" href="http://www.haskell.org/mailman/listinfo/haskell-cafe">http://www.haskell.org/mailman/listinfo/haskell-cafe</a>
</pre>
</blockquote>
</body>
</html>