[Haskell-cafe] Bit string

[Thomas Conway]

On 9/15/06, Lennart Augustsson <lennart at augustsson.net> wrote:
> It's hard to tell what the best representation is if you don't know
> what the operations that you are going to perform are.  If all you
> are going to do is I/O of bitstrings, then [Bool] could be great.  If
> you need to do bitwise boolean ops then Integer is a wise choice.

And is I/O of bitstring represented as Integer going to be
significantly worse [Bool]? It is certainly a much denser
representation. Actually the main operations are probably tests (is a
certain bit set), and encoding and decoding (to and from BER, PER,
etc).

The operations that need to be efficient are:

-- test to see if the Nth bit is set
testBit :: BitString -> Integer -> Bool

-- set the Nth bit
setBit :: BitString -> Integer -> BitString

-- clear the Nth bit
clearBit :: BitString -> Integer -> BitString

I can see the potential for creating large intermediate Integers (i.e.
1 `shift` n), if the number of bits is large.

T.