[Haskell-cafe] Names for properties of operators
Thomas Danecker
tdanecker at gmail.com
Sat Nov 7 20:09:33 EST 2009
No, they aren't rings, because rings are distributive...
2009/11/8 Thomas Danecker <tdanecker at gmail.com>:
> 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