On Sun, Oct 9, 2011 at 6:18 AM, Ryan Newton
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