Re: Two meanings of "data structures"

> I can in OOPLs just declare a collection as a Tree and it
> immediately has only the right methods and is also immediately
> self-documenting how it structured.

We're back to an older argument; rather than thinking of traversal per se in a Tree, you can see it as simply a set of algebraic equations that define how the various operations relate - e.g. "child(add(parent, c1)) = child" or some such. That's usually the most succinct definition I've seen of data structures, and they consist merely of operational definitions of semantics - nothing of the "internals." So it's a type, and its operations are defined over values of that type and other available types (e.g. Tree and Node, with perhaps Object in there for node contents).

So I guess what I'm saying is that in such data structures, "structure" is difficult to separate from functions - an artificial distinction?

I'd say that's different (without saying how) from a relation, which allows "type generation" both in defining your types and in defining the type of the result of a relational operation - say a join. It's a relation, but it's specifically a relation<int i, string s>, for example.

I don't have the lexicon or brainpower at this point to clearly articulate the difference, though...

> Not so with relations; we
> may embed an adjacency list in a relation, but this is not as
> obvious when looking at the code. Also, lots of possibly undesired
> operations are now supported.

It may not be obvious that it's an "adjency list", but its "adjency-listness" shouldn't be your goal, should it? A database with appropriate constraints gives you "adjancency-listness" as a byproduct, plus all the other relational operations. If those are undesired, then you probably didn't want a relation, nor did you want it to "relate" to other data structures, so it sounds like an attribute type (domain).

Otherwise you quickly get into a weird combinatorial explosion of how data structures relate to other data structures - what parts of X can "point to" parts of Y - so to what extent are those data structures encapsulated?

I think the value of relational is that it makes you choose, for each "data structure", whether it should be encapsulated with all the hiding that provides, versus unencapsulated with all the power that provides (especially when combined with other unencapsulate thingies).

> If we want a relation to represent, say, a queue, we need to enter
> a bunch of transition constraints that again will not be obvious
> in intent. In some ways the OOPL techinque of encapsulating
> *functionality* is superior to the RM approach, at least as
> I understand it.

OOPL offers type definition, though the bundling of functions with types isn't always done well (since in Java and the like, functions are second-class citizens).

> (The canonical comment at this point is
> to say "then you just don't understand it very well" and
> leave it at that. If the responder is not going to add to my
> understanding, please feel free not to respond; heard it!)

You rotten son of a...

> (These parentheticals are explicitly *not* addressed to
> Eric.)

Oops, never mind. :-)

> So it seems to me that perhaps we should discard OOPLs
> encapsulation of data in favor of the RM approach and
> declarative integrity constraints; but perhaps also we
> should examine the OOPL technique of collecting up
> appropriate operators as a style of constraint enforcement
> and see what we can't learn.

True enough, though I've found the collecting / enslavement of functions to a Primary Type to be limiting, especially in any sort of framework (e.g. you want to use Reflection for plug-in extensibility).

Again, I think the value of relational is that it makes you choose. Object classes which ride the fence, sort of like a relation (lots of getters) and sort of like a type, are often used inconsistently and much aliasing nastiness results.
Sorry for the incoherence of the above.

Immutables ahoy!

• erk