What data structure for an array of bit flags?

Question

I'm porting some imperative code to Haskell. My goal is to analyze an executable, therefore each byte of the text section gets assigned a number of flags, which would all fit in a byte (6 bits to be precise).

In a language like C, I would just allocate an array of bytes, zero them and update them as I go. How would I do this efficiently in Haskell?

In other words: I'm looking for a ByteString with bit-wise access and constant time updates as I disassemble more of the text section.

Edit: Of course, any kind of other data structure would do if it was similarly efficient.

Undermanned

Answer 1

You can use a vector with any data type that's an instance of the Bits typeclass, for example Word64 for 64 bits per element in the vector. Use an unboxed vector if you want the array to be contiguous in memory.

Birdie

Answer 2

The implementation for unboxed arrays of Bool-s in array is a packed bitarray. You can do mutable updates on such arrays in the ST Monad (this is essentially the same runtime behaviour as in C).

Quadrivium

These are both excellent answers, but I think I go with gspr's because it seems more idiomatic to me. – Undermanned

@Sebastian: vector doesn't pack Bool-s into bits, therefore you have to write your own wrapper if you want to read/write specific bits. Most of the time vector is a better choice because of the richer API, but here array is probably simpler. – Brendonbrenk

I think I will allocate one byte for each element anyway, because I think that would be more performant from an element access perspective. Also it feels like implementing my flags on top of Bits is somehow more convenient than 6 consecutive Bools, however that may be subjective. – Undermanned

@Sebastian valid points, I retract my opinion about array being preferable here. – Brendonbrenk

Although the votes beg to differ. Maybe I'm missing something? I will be able to tell in a few days. – Undermanned