[Haskell-cafe] Names for properties of operators
Thomas Danecker
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).
Cheers, Thomas
2009/11/7 Neil Brown <nccb2 at kent.ac.uk>:
> Hi,
>
> 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
> holds:
>
> (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.
>
> Thanks,
>
> Neil.
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
More information about the Haskell-Cafe
mailing list