Yep, it is simple. But I prefer to only use well-tested data structure libraries where I can! Here's an example simple implementation (partial -- missing some common functions):
module Data.BitList ( BitList , cons, head, tail, empty , pack, unpack, length, drop ) where import Data.Int import Data.Bits import Prelude as P hiding (head,tail,drop,length) import qualified Data.List as L import Test.HUnit data BitList = One {-# UNPACK #-} !Int {-# UNPACK #-} !Int64 | More {-# UNPACK #-} !Int {-# UNPACK #-} !Int64 BitList instance Show BitList where show bl = "BitList " ++ show (map (\b -> case b of True -> '1'; False -> '0') (unpack bl)) -- show bl = "pack " ++ show (unpack bl) empty :: BitList empty = One 0 0 cons :: Bool -> BitList -> BitList cons True x@(One 64 _ ) = More 1 1 x cons False x@(One 64 _ ) = More 1 0 x cons True x@(More 64 bv _) = More 1 1 x cons False x@(More 64 bv _) = More 1 0 x cons True (One i bv) = One (i+1) (bv `setBit` i) cons False (One i bv) = One (i+1) (bv ) cons True (More i bv r) = More (i+1) (bv `setBit` i) r cons False (More i bv r) = More (i+1) (bv ) r -- TODO: May consider (More 0 _ _) representation to reduce extra -- allocation when size of the BitList is fluctuating back and forth. head :: BitList -> Bool head (One 0 _ ) = error "tried to take head of an empty BitList" head (More 0 _ r) = error "BitList: data structure invariant failure!" head (One i bv ) = bv `testBit` (i-1) head (More i bv r) = bv `testBit` (i-1) tail :: BitList -> BitList tail (One 0 _ ) = error "tried to take the tail of an empty BitList" tail (One i bv ) = One (i-1) bv tail (More 1 bv r) = r tail (More i bv r) = More (i-1) bv r pack :: [Bool] -> BitList pack [] = One 0 0 pack (h:t) = cons h (pack t) unpack :: BitList -> [Bool] unpack (One 0 _) = [] unpack (One i bv) = (bv `testBit` (i-1)) : unpack (One (i-1) bv) unpack (More 0 _ r) = unpack r unpack (More i bv r) = (bv `testBit` (i-1)) : unpack (More (i-1) bv r) drop :: Int -> BitList -> BitList drop 0 bl = bl drop n bl | n >= 64 = case bl of One _ _ -> error "drop: not enough elements in BitList" More i _ r -> drop (n-i) r drop n bl = case bl of One i bv -> One (i-n) bv More i bv r -> More (i-n) bv r length :: BitList -> Int length (One i _) = i length (More i _ r) = i + length r -- TODO: index, take, etc -- TODO: functor instance, etc. -------------------------------------------------------------------------------- -- Testing: t1 = pack (L.concat$ L.replicate 10 [True,False,True]) t2 = L.length $ unpack $ pack $ replicate 1000 True t3 = pack $ replicate 1000 True t4 = drop 500 t3 p3 = L.and (unpack t3) p4 = L.and (unpack t4) t5 = iterate tail t4 !! 250 t5a = length t5 t5b = L.length (unpack t5) tests :: Test tests = TestList [ show t1 ~=? "BitList \"101101101101101101101101101101\"" , t2 ~=? 1000 , t5a ~=? 250 , t5b ~=? 250 , p3 ~=? True , p4 ~=? True ] -- TODO: QuickCheck On Sun, Oct 9, 2011 at 7:50 AM, Roman Beslik <ber...@ukr.net> wrote: > 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