Names for properties of operators

[Neil Brown-7]

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@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Thomas Danecker-2]

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@...>:

> 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@...
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Thomas Danecker-2]

No, they aren't rings, because rings are distributive...

2009/11/8 Thomas Danecker <tdanecker@...>:

> 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@...>:
>> 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@...
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>
>

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Matthew Brecknell-3]

Hi Neil,

You wrote:
> [...] 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)

I don't know any snappy names for this, but the following might help to
reveal some structure.

Pick some specific (but arbitrary) types:

(%) :: A -> B -> B

And some values:

x, y :: A
z :: B

f, g :: B -> B
f = (x%)
g = (y%)

Then:

x % (y % z) == f (g z) == (f . g) z
y % (x % z) == g (f z) == (g . f) z

So (%) has property 1 iff the sub-monoid of Endo [1], which is generated
by Endo (x%) forall x :: A, is commutative.

Property 3 is the same, but with a larger generator set.

Note that in your examples, the sub-monoid generated by insert+union is
just the same as that generated by insert alone (assuming no infinite
sets). This particular sub-monoid also happens to be a bounded
join-semilattice (isomorphic to the finite subsets of A), which also
makes it idempotent.

Regards,
Matthew

[1]http://haskell.org/ghc/docs/latest/html/libraries/base/src/Data-Monoid.html#Endo



_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Neil Brown-7]

Hi,

Thanks for the replies so far.  If it helps, after I sent my post, I
spotted a couple of arithmetic examples:

Neil Brown wrote:
> 2: (a % b) % c = (a % c) % b
Division (on rationals) obeys this property (a / b) / c = (a / c) / b --
which is actually equal to a / (b * c), but that doesn't matter for my
property.
> 4: (a % b) ~ c = (a ~ c) % b
Division and multiplication on rationals obey this property: (a / b) * c
= (a * c) / b.

Thanks,

Neil.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Sjoerd Visscher-2]

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@...
> http://www.haskell.org/mailman/listinfo/haskell-cafe

--
Sjoerd Visscher
sjoerd@...



_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe