Set operations

[konsumlamm]

A common use case of bit vectors is to use them as sets (with a 1 at index i indicating that i is in the set and a 0 indicating that it isn't). There could be some operations for this use case, e.g. union, intersection, difference, isSubset, etc. Would these be good additions to bitvec? If so, should they operate on Vector Bit or a newtype (like F2Poly)?

[Bodigrim]

How would union differ from zipBits (||)?

[konsumlamm]

How would union differ from zipBits (||)?

The implementation wouldn't (although it could extend the smaller input, so that no elements are lost), but the documentation would state that it does set union. Other operations like isSubset would have a less trivial implementation.

[Bodigrim]

(I think extending the smaller input is reasonable, yes)

A newtype please. Depending on the number of additional functions, might be better to export it from a separate module...

[konsumlamm]

(I think extending the smaller input is reasonable, yes)

What about set complement then? Naively, this would be complement (since usually when using a bitset, you have a fixed maximum size), but if we want to allow extending the vector, perhaps something like what Integer is doing would be better, i.e. conceptually storing an infinite vector of 1s, but representing it as an "inverted" flag and storing the complement in that case. Then set complement would just flip this "inverted" flag, but all other operations would have to match on the flag to decide what to do.

[Bodigrim]

That's an interesting idea, I'd like to see how it works out.

It can still be a mere newtype over Vector Bit, just that the 0-th bit stands for the "sign"... Or is it too unwieldy?..