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
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#se... (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