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