[Haskell-cafe] Names for properties of operators

Matthew Brecknell matthew at brecknell.net
Sat Nov 7 20:47:08 EST 2009

Hi Neil,

You wrote:
> [...] Is there a name for this property, which 
> I'm numbering 1, (where (%) :: a -> b -> b; i.e. the operator is 
> potentially, but not necessarily, asymmetrically typed):
> 1: a % (b % c) = b % (a % c)

I don't know any snappy names for this, but the following might help to
reveal some structure.

Pick some specific (but arbitrary) types:

(%) :: A -> B -> B

And some values:

x, y :: A
z :: B

f, g :: B -> B
f = (x%)
g = (y%)


x % (y % z) == f (g z) == (f . g) z
y % (x % z) == g (f z) == (g . f) z

So (%) has property 1 iff the sub-monoid of Endo [1], which is generated
by Endo (x%) forall x :: A, is commutative.

Property 3 is the same, but with a larger generator set.

Note that in your examples, the sub-monoid generated by insert+union is
just the same as that generated by insert alone (assuming no infinite
sets). This particular sub-monoid also happens to be a bounded
join-semilattice (isomorphic to the finite subsets of A), which also
makes it idempotent.



More information about the Haskell-Cafe mailing list