> data *(Bits b) =>* BitList b
Is deprecated and soon to be removed from the language.
I fail to understand. Why not just:
> data BitList b = Nil | BitList Int b (BitList b)
??
2011/10/9 Roman Beslik <ber...@ukr.net>
> 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
> listHaskell-Cafe@haskell.orghttp://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
