Re: Two meanings of "data structures"

As an aside (hopefully this isn't better placed in a different thread), I'm still mulling over the difference between "atomic" and "composite" types. I'm reading Watt's book (referenced by Dawn in Marshall's
"Choice quote" thread) and he doesn't truly define the difference, if
there is one.

A String can be viewed as a container for Strings, given some convention for separating them (even if just character index). Similarly, a String[1] in Java is a String container which differs very little from a Base64EncodedString, which can be said to "hold" a String.

Get and set operations on an Array can be seen as:

get(List, index) -> element
set(List, index, element) -> List

and more specifically as something on the order of:

get(set(List,index,element), index) = element get(List,index) | index>length(List) = undefined

in other words, just functions, same as:

getMonth(Date) -> Month
getYear(Date) -> Year

and

getSubstring(String, index, length) -> String

Does the composite vs. atomic distinction have something to do with
"recoverability" - the presence of functions R and S such that R(S(C,
x))=x ?

Another distinction is between List and List<String> or whatever - specifically between some type and a "type generator", of which Relation is a particularly advanced example. There are generic relational operators, but the validity of (most) relational expressions depends on the specific relations involved - you can't restrict over an expression which contains a nonexistent attribute name, for example. In that respect relations seem different than lists and arrays and even maps.

Anyone familiary enough with type theory to clarify these differences?

• Bear of little brain

P.S. Watt has an interesting quote in 2.3: "Note that the Date type [as modeled using an Ada record] models real-world dates only approximately: some Date values, such as (feb, 31), do not correspond to real-world dates. (This is a common problem in data modeling. Some real-world data are too awkward to model exactly by programming language types, so our data models have to be approximate.)"

I disagree completely; proper type definition (using OO or some sort of constraint-based subtyping language) and relational constraints would allow very precise and enforceable type definitions. Received on Wed Nov 17 2004 - 20:04:37 CET