On Sun, Oct 9, 2011 at 6:18 AM, Ryan Newton <rrnew...@gmail.com> wrote:
> > 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 > I suggest data BitTail = Zero | More {-# UNPACK #-} !Int64 BitTail data BitList = Head {-# UNPACK #-} !Int {-# UNPACK #-} !Int64 BitTail empty = Head 0 0 Zero or else just data BitList = Head {-# UNPACK #-} !Int {-# UNPACK #-} !Int64 [Int64] empty = Head 0 0 [] length (Head n _ xs) = n + 64 * List.length xs 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) > I'd implement as view :: BitList -> Maybe (Bool, BitList) view (One 0 _) = Nothing view bl = Just (head bl, tail bl) unpack = unfoldr view > 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 > This is wrong. drop 5 (More 1 0 (One 64 0)) -> More (-4) 0 (One 64 0) Fixed version (also gives same behavior as List.drop when n > length l) drop :: Int -> BitList -> BitList drop n (One i bv) | n >= i = empty | otherwise = One (i - n) bv drop n (More i bv r) | n >= i = drop (n - i) r | otherwise = More (i - n) bv r -- ryan
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe