Re: A Logical Model for Lists as Relations

vc wrote:
> Jay Dee wrote:
>

>> >>I think not.  Relations are sets, lists aren't.
>> >
>> > Of course lists are sets plus the 'cons' operation.
>>
>>I suspect we're stumbling into differing conventional definitions
>>rather than fundamental differences.  In my mind, a list may
>>hold duplicates, while a set may not.  [More follows.]  Too, my
>>reading of MS's post led me to think position in the list was
>>significant.
>>
>>Maybe that's covered in your theory of lists -- plus the 'cons'
>>operation -- but not in mine.

Others might write `0, nat+1: nat'

>>See, I probably grok a successor operator, maybe a nil operator, but
>>I'm not tracking cons and am not sure why zero and nil differ.

I am aware of the difference between the number zero and an empty list. Or set. Or bag. I was not aware that you attached the name Nil to such. And my notation would use brackets, not parentheses.

 From reading the other responses to this post, I can see that we're stumbling all over each other's terminology.

All the points made about "asserting" and "counting" and "naturals" and "sequences" are valid. Unfortunately, because we don't share the same vocabulary, currency is lacking. Consequently, some responses were somewhat off-point.

 >> What's 'bunch theory' ?

As for my own: scalars are boolean, numbers, and characters. Data may be structured (Here we go down the rabbit hole!) as:   a bunch (unpackaged and unindexed),
  a set (packaged and unindexed),
  a string (unpackaged and indexed), and   a list (packaged and indexed).

More terminology? Well, bunches and sets consist of elements, which has the meaning we're familiar with from sets. Sets are sets; they are a package of elements constructed with {} operator. , (comma) is the set union operator. Unpackaging a set - interpolating the contents of a set - yields a bunch, which also has a comma union operator. So

   a, b, c is a bunch
  {a, b, c} is a set.

The empty bunch is null and the empty set is {null}.

Strings consist of items which may be any boolean, number, character, non-empty bunch, or set. Strings are catenated with ; (semicolon). So

   17; 42; A; 17
is a string of length 4. Items in a string can be referred to by their 0-origin ordinal position. Ordering is defined as lexical and the < = > &c operators are defined. Indexing? You bet! Slicing? Of course!

Lists are to strings as sets are to bunches.

   17; 42; A; 17 is a string
  [17; 42; A; 17] is a list
Catenation can be defined on lists:
  [A] + [B] = [A; B]
So can mapping, composition, &c -- all it takes is definition.

Empty strings and empty lists? Call 'em nil and [nil].

There's really nothing in any of this that's revolutionary or new; everything, to some extent or another, has been made manifest in other disciplines/languages/notations/whatever. It's simply unfortunate that our language prevents us from understanding each other.

[I was wrong when I earlier said that MS needed bunches rather than lists. He needs lists to represent lists and, as BB and VT pointed out, they are readily accommodated in RM as relations. But, you know, I wasn't sure what MS meant when he said "list."]

RM has its own scheme: everything in RM is of type boolean, other scalar, tuple, or relation. That "other scalar" is where we can put any of the things referred to here -- as well as many things that haven't been mentioned. Received on Fri May 12 2006 - 01:42:43 CEST