Re: More on lists and sets

From: Brian Selzer <brian_at_selzer-software.com>
Date: Thu, 23 Mar 2006 09:37:19 GMT
Message-ID: <j%tUf.49721$F_3.48160_at_newssvr29.news.prodigy.net>


"David Cressey" <dcressey_at_verizon.net> wrote in message news:uLYTf.2912$yo1.2560_at_trndny09...
>
> "Brian Selzer" <brian_at_selzer-software.com> wrote in message
> news: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.
>>
>
> You are correct. However, as I said in my original post, I'm interested
> in
> the case where something that is really a set gets stored in a list for
> the
> sake of convenience, and then used once again as if it were a set.
>
> Pizza toppings are a good example. They are really a set, but they are
> often presented in the form of a list.
> If you look on the menu, you'll see what looks like a list of toppings,
> even though in reality it's a set.
>
> So, in this case, the information that gets lost when you convert from a
> list back to a set is information that was irrelevant in the problem
> domain
> to begin with. When the set was stored as a list of elements, an
> arbitrary
> order was imposed on it. Losing that information is trivial.
>
> Marshall proposes a language that would offer both sets and lists. That
> may
> turn out to be the right way to go. But I'm interested in the case where
> the programming language offers lists (because they are easy to implement
> and support), while the database language offers sets (because it's more
> generally useful to do so).
>
> In this case, the easier it is to go back and forth, the more productive
> programmers will be, and the more productive data managers will be.
>
> As Jan Hidders has already pointed out, there is nothing theoretically
> innovative about this case. I'm interested anyway.
>
>
>

If order is unimportant, then transformation back and forth between a list and a bag is trivial. (1, 2, 1, 3) would be equivalent to (3, 1, 1, 2) and [1, 1, 2, 3]: it wouldn't matter how the list is stored as long as the multiplicity of each element is maintained. If neither order nor multiplicity is important, then transformation back and forth between a list or bag and a set is trivial. (1, 2, 1, 3) would not only be equivalent to (3, 1, 1, 2) and [1, 1, 2, 3], but also (3, 2, 1), [1, 1, 2, 3, 3], and {1, 2, 3}: it wouldn't matter how the list is stored as long as each distinct element is represented at least once. Received on Thu Mar 23 2006 - 10:37:19 CET

Original text of this message