[Haskell-cafe] Bit string

[Thomas Conway]

Hi all,

I'm doing some work with ASN.1, and I'm thinking about how to
represent the type "BIT STRING".

The obvious, and inefficient representation would be
> type BitString = [Bool]

A reasonable sparse representation might be
> type BitString = [Integer]
where the integers represent the positions of the non-zero bits, but
other implementations (e.g. C & C++ based ones) mostly seem to use
dense representations, and there are certain predictability advantages
to be had by following existing implementations in this regard.

But given that a value of type BIT STRING is allowed to have leading 0
bits, which have no semantic effect, another representation would be
> type BitString = [Word64]
(I'm a modern type, and believe in 64bit computing ;-), but you could
use Word32 if you liked).

However, after a few moments' consideration, I realized, that if I was
going to use a representation like that, I could probably use
> type BitString = Integer
which already has [I assume] a carefully optimized implementation.
Also, it ends up being significantly more strict than a list
representation, which is probably a good thing in most situations.

My question for all present is: Have I missed either a problem with
using Integer, or have I overlooked a better representation?

T.