# Re: More on lists and sets

From: Brian Selzer <brian_at_selzer-software.com>
Date: Tue, 21 Mar 2006 12:54:22 GMT
Message-ID: <2ISTf.3660\$tN3.3129_at_newssvr27.news.prodigy.net>

"David Cressey" <dcressey_at_verizon.net> wrote in message news:9OCTf.2923\$1U1.813_at_trndny05...
>I think we've recently discussed lists and sets at length in the context of
> the problem domain. IMO, we can give that a rest, at least for a while.
>
> We've discussed how a set (or pizza toppings) might be stored in a list,
> for the sake of convenience, but the retrieve dand used as if it were a
> set.
> We've also discussed how a set of tuples, with one attribute thrown in for
> sequencing purposes, can, for all intents and purposes, be treated as if
> if
> were a list.
>
> I want to turn my attention to the discussion of lists and sets from the
> logical and or physical design perspective. Marshall Spight recently said
> that nearly all programming languages offer support, in one way or
> another,
> for lists. Support for sets in much more spotty. Marshall figures that a
> good language will have to allow for both. Without disputing that
> conjecture, I want to turn my attention to facilities that can convert
> easily beck and forth between sets and lists.
>

A list of widgits cannot be converted to a set of widgits without losing information. A list can be represented as a single path through a directed graph where the set of verticies is the underlying domain for the list, for example, widgits. The set of verticies is only one part of the graph, since a graph not only includes the verticies, but also the edges, which are lost in the process. A list can also be represented as a relation with a widgit attribute and a sequence attribute, so the set of widgits can be thought of as a projection on that relation. Any way you look at it, the operation is definitely not lossless, and therefore, not reversible.

The value of the elements in a list or bag are augmented by their presence within the list or bag, and in a list, the value is augmented further by the position of the element. This augmentation gives each element identity. "It's the third element in the list." "It's one of the five apples in the bag." That identity is lost when converting a list to a bag or a set or when converting a bag to a set.

> In particular, if you look at SQL as a prototype for some future
> interface
> language, it's useful to look at views and cursors. A view is basically
> a
> named query declared in the context of the database, that can be invoked
> to
> play the role of a table. A cursor is a named query, declared in the
> context of a user process (program), that can be invoked to play the
> role
> of a list. I haven't seen cursors discussed as if they were lists, but
> it
> seems to make an eminent amount of sense to me.
>
> If you'll allow me to stretch the concept just a bit, it seems to me
> that
> you can look at both a Pascal file type, and a unix pipe as a list (of
> file
> elements). And a cursor seems to do the same thing. I don't know how I
> would express going the other way. That is, how to declare a list, load
> it
> with data as if it were a list, and then turn around and deliver it to
> the
> database as if it were a table. What I'd like is some kind of compromise
> between unix pipes and the concpets behind Oracle's SQL*loader. Something
> that would look like an output file, but really be a pipeline into the