Re: More on lists and sets

From: Mikito Harakiri <mikharakiri_nospaum_at_yahoo.com>
Date: 21 Mar 2006 09:41:29 -0800
Message-ID: <1142962888.991516.261470_at_u72g2000cwu.googlegroups.com>

Mikito Harakiri wrote:
> Mikito Harakiri wrote:
> > Definition. List intersection is a cartesian product with equijoin of
> > the list nodes and lexicographic order. Example: 1->2->1 /\ 2->1->2 =
> > 2->1->1->2
> >
> > 2 2
> > ^ ^
> > | \
> > 1 1 ------> 1
> > ^ ^
> > | \
> > 2 2
> > 1 -> 2 -> 1
> >

Formal definition. Let A(x) and B(x) be lists. Convert them to relations
A(x,y) and B(x,z) where attributes y and z are orderings. In the example we have

A(x,y)

---

1 0
2 1
1 2

B(x,z)

---

2 0
1 1
2 2

Join the relations

A(x,y)&&B(y,z)

---

2 1 0
1 0 1
1 2 1
2 1 2

Make the list of values x ordered by z*100+y (where the constant 100 is the maximum y). Remove the ordering columns y and z.

List intersection associativity follows from the definition.

> This is actually amusing.

It is.

> As join/intersection is noncommutative, we have left selection and right
selection.

The right selection with the x>=0 condition is the list sort operation!

1->2->1->3->2 /\ 'x>=0'
=
1->1->2->2->3 Received on Tue Mar 21 2006 - 18:41:29 CET