[Haskell-cafe] Names for properties of operators

Neil Brown nccb2 at kent.ac.uk
Sat Nov 7 13:57:34 EST 2009


We have names for properties of operators/functions.  For example, if 
this holds:

a % b = b % a

for some operator %, we say that % is commutative.  Similarly, if this 

(a % b) % c = a % (b % c)

we say that % is associative.  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)

For example, `Set.insert` obeys 1 for any values of a, b and c.  (Any 
operator that is both associative and commutative automatically 
satisfies this property, but this property can be satisfied without the 
operator being either of those.)  Given this property, we could prove 
useful follow-on results, such as:

foldr (%) x ys = foldr (%) x (reverse ys)
foldr (%) x ys = foldl (flip (%)) x ys

The property 1 effectively states that the far-right hand element in a 
chain of such operators is special, but the ordering of everything to 
the left of it doesn't matter.

One could conceive of a mirror property (where (%) :: a -> b -> a):

2: (a % b) % c = (a % c) % b

If (%) obeys 1, flip (%) obeys 2 (and vice versa).  I think these 
properties are useful -- I'd like to know if they have names already to 
describe them by.  A similar property of two relations (where ((%), (~)) 
:: (a -> b -> b, c -> b -> b) ) would be:

3: a % (b ~ c) = b ~ (a % c)

with mirror version (and adjusted types):

4: (a % b) ~ c = (a ~ c) % b

Do these have a name?  As an example, `Set.insert` and `Set.union` obey 
property 3 for all values of a, b and c.

There are also symmetrically-typed examples of these operators, but the 
Set operations are easy and familiar.



More information about the Haskell-Cafe mailing list