[Haskell-cafe] Names for properties of operators
tdanecker at gmail.com
Sat Nov 7 20:01:07 EST 2009
1. and 2. are called left- and right-commutative.
And I think that 3. and 4. are left- and right-commutative rings
(please correct me if I'm wrong here).
2009/11/7 Neil Brown <nccb2 at kent.ac.uk>:
> We have names for properties of operators/functions. For example, if this
> 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.
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
More information about the Haskell-Cafe