Re: More on lists and sets

From: paul c <toledobythesea_at_oohay.ac>
Date: Thu, 23 Mar 2006 03:44:33 GMT
Message-ID: <BQoUf.172164$sa3.69546@pd7tw1no>

Mikito Harakiri wrote:
> 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)
> -------
> 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 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.
>

Thanks for explaining it, must admit this definition had never occurred to me, perhaps partly because how to insert isn't clear when 'position' attributes are used. Also, I presume that the z*100+y ordering could have been y*100+z too.

p Received on Wed Mar 22 2006 - 21:44:33 CST