newtype And a = And { getAnd :: a }

newtype Or a = Or { getOr :: a }

newtype Even a = Even { getEven :: a }

newtype Odd a = Odd { getOdd :: a }

Once things move to arbitrary bitwise operations, Even/Odd may not be the best names, though they do perform "vertical" bitwise parity checks.

While I don't have a particularly strong preference about whether those extra instances should live in Data.Monoid or Data.Bits, due to Monoid now being in Prelude, users do import Data.Monoid unqualified in rather more code than Bits. This would give me a slight preference to placing these in Data.Bits, but if one or the other would create an import cycle in base, I think it'd be fine to let that trump such a concern and force the placement.

-Edward