Re: list algebra

"mAsterdam" <mAsterdam_at_vrijdag.org> wrote in message news:40e28f19$0$6968$e4fe514c_at_news.xs4all.nl...
> Marshall Spight wrote:
> >
> > To my mind, this is simply a typing question. If I have a simple
> > variable of type <any>, then I can put any value of any type in
> > there, but I can't do any operations on it because <any> has
> > no operations.
> >
> > In this way of thinking, every list is homogeneous; it is simply
> > homogeneous as some upper bound of the union of the types
> > of all the elements.
>
> I like it. A list by definition homogeneous.
> The somewhat explosive differentiation is pushed to 'type'.
>
> It won't suit widely spread ideas on the
> meaning of the term list, so it must be stated.
>
> http://www.swif.uniba.it/lei/foldop/foldoc.cgi?list
> <quote>
> A data structure holding many values, possibly of different types,
> which is usually accessed sequentially, working from the head to
> to the end of the tail - an "ordered list".
> This contrasts with a (one-dimensional) array, any element
> of which can be accessed equally quickly.
> </quote>

I've long thought those widely spread ideas are crap.

The above definition describes two different implementations of list, and ignores the interface question entirely. "List" or "sequence" is a mathematical concept and it can be implemented in many different ways. (In java, this is essentially the difference between java.util.List, an interfact, and java.util.LinkedList, and java.util.ArrayList. The first is interface; the other two are different implementations of that interface.)

Clearly the order of element-access time is implementation dependent, and does not belong in any definition of a logical data structure. Are we to be forever limited to discussing implementations? If D&D have done one good thing, it's to elevate some part of the discussion to the logical level.

Futhermore, linked list is the Britney Spears of data structures. Sure, it gets a lot of attention, but it doesn't hardly deserve any of it.

Marshall Received on Wed Jun 30 2004 - 16:41:07 CEST