[Haskell-cafe] Names for properties of operators
Sjoerd Visscher
sjoerd at w3future.com
Sun Nov 8 06:45:11 EST 2009
This seems related:
http://en.wikipedia.org/wiki/Semigroup_action
But I'm not entirely sure.
Sjoerd
On Nov 7, 2009, at 7:57 PM, Neil Brown wrote:
> 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
--
Sjoerd Visscher
sjoerd at w3future.com
More information about the Haskell-Cafe
mailing list