Re: How is this collection called?

Mikito Harakiri wrote:

> Let '*' be binary aggregation operator.
>
> Then, sets obey the following laws:
>
> a*a=a
> a*b=b*a
> a*(b*c)=(a*b)*c
>
> Bags:
>
> a*a!=a
> a*b=b*a
> a*(b*c)=(a*b)*c
>
> Lists:
>
> a*a!=a
> a*b!=b*a
> a*(b*c)=(a*b)*c
>
> What collection type meets
>
> a*a!=a
> a*b!=b*a
> a*(b*c)!=(a*b)*c
>
You've already seen some examples. The problem is a

bit under-specified, since one has to pick a structure and an aggregation operator, but I'd suggest the merge of two (binary? ordered?) trees, i.e., a * b is the tree formed by making a new node with a as the left child and b as the right child. Obviously none of the laws will be satisfied in general.

We could even invent more laws, like the existence of an identity:

    There exists a (unique?) object 1 such that a * 1 = a     and/or 1 * a = a

(True for sets under union, true for bags under their "union",

true for lists, true (in one direction) for Michael's stacks, and false for my tree example.)

Inverses are a bit trickier:

    For (all|all "nonzero") objects a, there is an object b     such that a * b = 1 and/or b * a = 1 (for suitable "1").

(No "natural" collection type + aggregation jumps to mind.)

Of course one could include another operator and ask for distributivity....

Just noodling around when I should be working,

Rick

p.s. One could modify Michael's example and have the collection type be binary search trees and let a * b be delete (somehow) the elements of a and insert them into b.

p.p.s. Is it obvious that I'm teaching data structures this term?

p^3.s. Binomial heaps?

p^4.s. I gotta stop this and start grading. Received on Wed Mar 31 2004 - 03:59:46 CEST