[Haskell-cafe] Bit string

[Lennart Augustsson]

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.

	-- Lennart


On Sep 14, 2006, at 21:35 , Thomas Conway wrote:

> 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.
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe