Re: More on lists and sets

paul c 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
> > ...
>
> I'm struggling with the definition. If 1 and 2 stand for nodes, aren't
> the two lists circular? If that's so, aren't there multiple answers?
> (or one answer comprising two lists?)

A label doesn't define list node identity. Otherwise, characters strings can't be represented as lists.

Also the informal defintion above is too sketchy. 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)

Make the list of values x ordered by z*100+y (where the magic constant 100
is the greatest y in B). Project away the ordering columns y and z.

This definition should be equipped with a proposition that proves independence from the choice of auxiliary ordering columns. Received on Wed Mar 22 2006 - 19:17:28 CET