Add a bitset newtype wrapper

[Jashweii]

These would function the same as other set instances or n-tupled bool instances but efficiently via Bits and FiniteBits.

newtype BitSet a = BitSet a
    deriving (Eq, Bits, FiniteBits)
--  Should probably show/read as binary or a set of set bits (latter doesn't have read . show = id since it can re-order)
instance Bits a => PartialOrd (BitSet a) where
--  Avoiding complement on purpose (see finitebits note), there may be a more concise solution
    a `leq` b = (zeroBits == (a .&. (a `xor` b)))
instance Bits a => Lattice (BitSet a) where
    (\/) = (.|.)
    (/\) = (.&.)
instance Bits a => BoundedJoinSemiLattice (BitSet a) where
    bottom = zeroBits
-- see oneBits note in base 4.16 on ghc's gitlab
-- https://gitlab.haskell.org/ghc/ghc/-/blob/master/libraries/base/Data/Bits.hs#L79
instance FiniteBits a => BoundedMeetSemiLattice (BitSet a) where
--  top = oneBits -- 4.16
    top = complement zeroBits
instance FiniteBits a => Bounded (BitSet a) where
    maxBound = top
    minBound = bottom

(Natural is an example of a Bits that is not a FiniteBits, and is undefined for complement)

[phadej]

Makes sense. PR welcome.

EDIT: I'm not sure about name though. We have Ord -> Ordered. So here I'd expect some adjective as well, but my English isn't good enough.

EDIT: instance FiniteBits a => Bounded (BitSet a) where I'm not sure why you propose it. I don't think we need it. (Bounded is tricky class, I'd rather avoid it).

[phadej]

FWIW, I wanted to clean up Bits and FiniteBits such that complement wouldn't be in Bits, so Natural can be an instance without miss-behaving methods: https://mail.haskell.org/pipermail/libraries/2019-December/030132.html

[Jashweii]

How about Bitwise? I'm not sure if there might be some other useful Bits-based lattice other than wrappers applied to this however (like something acting as a nested Lexicographic on bits), and it doesn't really indicate the idea of a set.

I just added Bounded as they're bounds for the partial order, the docs on Bounded themselves say "Ord is not a superclass of Bounded since types that are not totally ordered may also have upper and lower bounds" I suppose one of the issues with Bounded is where Ord and PartialOrd don't match up, I wasn't thinking of an Ord instance but ofc then if someone wanted to put one of these in a Map directly they would be out of luck.

I have not had much luck with a show instance only requiring Bits. What I really need is a bit size that's argument dependent rather than a constant (and for read a function to check an argument can get another bit). Basically a partial isomorphism with [Bool]. The instance is possibly more hassle than it's worth over using stock show/read (either way a show instance is required by the tests).