SQL for Smarties | SQL Programming Style | Trees and Hierarchies in SQL | SQL Puzzles and Answers | Data and Databases


Monday, May 22, 2006

Sets and Lists, again

SQL Apprentice Question
Recently, in a thread on implementing both threads and lists in a
programming language, the example of lists or sets of Presidents arose. I
mentioned that in a list of presidents, Grover Cleveland would appear once,
but in a list of presidencies, he would appear twice.

Bob Badour asked what purppose would be served by a list of presidents, or
words to that effect. I'm interested.


If one could have a set of presidents, why would one ever want a list? In
general, if a language implements sets, why would the same language need
to also implement lists? What does it buy you?


I'm thinking of Lisp, which implemented lists, but not sets. MDL (aka
Muddle) implemented arrays, and that's one step closer to implementing sets,
but not all the way.


SQL implemented sets, but not lists. Although local extensions of SQL do
implement lists, e.g. "Segmented Strings" in DEC Rdb (aka Oracle/Rdb),
it's not really part of the language as such.


I'm also thinking of Pascal, which implemented sets, (as bitmaps), and also
lists, albeit implicitly. What I mean is that you can combine the concepts
of "record" and "pointer" in Pascal to construct dynamic linked lists of
whatevers. But Pascal was primarily for teaching and learning programming,
and may have implemented both for precisely that purpose.


So, if you have sets, why do you need lists?


Celko Answers
>> I mentioned that in a list of presidents, Grover Cleveland would appear once, but in a list of presidencies, he would appear twice. <<


We should not model presidents, but "The Presidency" by perople and
terms, so the n-th president of US has the value of Mr. X. And the
order is important -- so you can blame the previous guy for a disaster
that happened in your term.


>> So, if you have sets, why do you need lists? <<


Ever try to write a parser in SQL instead of LISP? The LISP/list model
is the best way to lingustics, semantic networks, etc. Those tools do
STRUCTURE and not DATA.

One of my Pascal programming exervcises was based ont he combinartory
operators given in Raymond Smulliyan's book "To Mock a Mocking Bird"
and part of the problem was to pick a method. Pascal list processing
was 1000 times better than try to process the expression as strings !

No comments: