Monoid Parity instance?

[hdgarrood]

I would like to suggest that we define the following instances:

instance semigroupParity :: Semigroup Parity where
  append Even Even = Even
  append Even Odd = Odd
  append Odd Even = Odd
  append Odd Odd = Even

instance monoidParity :: Monoid Parity where
  mempty = Even

-- I guess this would need to go in a separate library, since groups aren't defined in core afaik
instance groupParity :: Group Parity where
  ginverse = id

(as a group, Parity would be isomorphic to the group ℤ/2ℤ).

A nice consequence of doing this would be that parity :: Int -> Parity becomes a group homomorphism, where the group over Int we are considering is the additive one. That is,

parity x <> parity y = parity (x + y)

holds for all x, y :: Int. Additionally, the function parity :: Sym -> Parity in my symmetric-groups library, where Sym is the type of permutations on the set {1,2,...n} for some (finite) n, would also become a group homomorphism.

[paf31]

It's a Semiring too, right?

I'm still up for adding groups and modules to core, by the way.

[hdgarrood]

Yes: if we define add as the above append and mul as follows:

mul Odd Odd = Odd
mul _ _ = Even

We get a Field, even. We also get the following property:

parity x * parity y = parity (x * y)

Maybe that makes more sense than the above definition; this would actually make parity into a ring homomorphism (which is of course a little stronger). At this point we'd pretty much be identifying Parity with the field of two elements, but on reflection I think this makes a lot of sense. Maybe we should not give Parity a Semigroup instance if we were to do this though, for the same reason we don't give Int one.

[garyb]

Maybe we should not give Parity a Semigroup instance if we were to do this though, for the same reason we don't give Int one.

:+1: the Additive / Multiplicative newtypes will still work there, since they're constraint based rather than type based.

[hdgarrood]

We did briefly discuss this before and came to the opposite conclusion: https://github.com/purescript/purescript-integers/pull/27. I do now have a motivating use case which I previously wasn't able to provide, though: I would quite like to be able to test a parity function in my symmetric groups library by writing quickCheck \f g -> Sym.parity f + Sym.parity g == Sym.parity (f <> g) for Sym.parity :: Sym -> Parity.