+
+-- | /O(n)/ @'take' n bs@ returns the prefix of @bs@ of length
+-- @n@. @bs@ must have at least @n@ bits.
+take ∷ Integral n ⇒ n → BitString → BitString
+take n xs = case splitAt n xs of
+ (taken, _) → taken
+
+-- | /O(n)/ @'drop' n bs@ returns the suffix of @bs@ after the first
+-- @n@ bits. @bs@ must have at least @n@ bits.
+drop ∷ Integral n ⇒ n → BitString → BitString
+drop n xs = case splitAt n xs of
+ (_, dropped) → dropped
+
+-- | /O(n)/ @'splitAt' n bs@ is equivalent to @('take' n bs, 'drop' n
+-- bs)@.
+splitAt ∷ Integral n ⇒ n → BitString → (BitString, BitString)
+splitAt n bs
+ = case splitRemAt n $ leftRem bs of
+ (# S.Just h, lr' #)
+ -- The leftRem has enough bits.
+ → let !h' = BitString {
+ leftRem = h
+ , leftBytes = L.empty
+ , rightBytes = L.empty
+ , rightRem = remEmpty
+ }
+ in
+ (h', bs { leftRem = lr' })
+
+ (# S.Nothing, _ #)
+ → let !bytesToTake = (n - fromIntegral (remLen $ leftRem bs)) `div` 8
+ !amortised = leftBytes bs `L.append` (L.reverse $ rightBytes bs)
+ -- 0 ≤ bitsToTake < 8 - remLen (leftRem bs)
+ -- ∴ remLen (leftRem bs) + bitsToTake < 8
+ !bitsToTake = n - bytesToTake ⋅ 8 - fromIntegral (remLen $ leftRem bs)
+ in
+ case (# bytesToTake, L.uncons amortised #) of
+ (#_, Just (!w, amor') #)
+ -- There is at least one byte in the byte pool
+ -- (amortised).
+ → let !h1 = leftRem bs
+ (# h2, lr' #)
+ = case splitRemAt bitsToTake $ byteToRem w of
+ (# S.Just h2', lr'' #) → (# h2', lr'' #)
+ (# S.Nothing , _ #) → error "internal error"
+ !h = h1 `appendRem` h2
+ (bytes, lb')
+ = L.splitAt (fromIntegral bytesToTake) amor'
+ in
+ if L.length bytes ≡ fromIntegral bytesToTake then
+ -- The byte pool actuall has at least
+ -- bytesToTake bytes.
+ let !h' = BitString {
+ leftRem = h
+ , leftBytes = bytes
+ , rightBytes = L.empty
+ , rightRem = remEmpty
+ }
+ !bs' = BitString {
+ leftRem = lr'
+ , leftBytes = lb'
+ , rightBytes = L.empty
+ , rightRem = rightRem bs
+ }
+ in
+ (h', bs')
+ else
+ error "splitAt: not enough bits"
+
+ (# 0, Nothing #)
+ -- No bytes are in the byte pool but the
+ -- rightRem may have enough bits.
+ → case splitRemAt bitsToTake $ rightRem bs of
+ (# S.Just h, rr' #)
+ → let !h' = BitString {
+ leftRem = leftRem bs
+ , leftBytes = L.empty
+ , rightBytes = L.empty
+ , rightRem = h
+ }
+ !bs' = BitString {
+ leftRem = remEmpty
+ , leftBytes = L.empty
+ , rightBytes = L.empty
+ , rightRem = rr'
+ }
+ in
+ (h', bs')
+
+ (# S.Nothing, _ #)
+ → error "splitAt: not enough bits"
+
+ (# _, Nothing #)
+ -- No bytes are in the byte pool but more than 8
+ -- bits are requested. The rightRem can't have
+ -- that many bits.
+ → error "splitAt: not enough bits"