[Haskell-cafe] Bit string

Lennart Augustsson lennart at augustsson.net
Thu Sep 14 21:48:49 EDT 2006

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

More information about the Haskell-Cafe mailing list