data structure vs. mathematical structure (was: [Axiom-developer] Graph theory)

[Ralf Hemmecke]

> I think one of the neat things about Axiom is that it is usually
> not necessary or even desirable to make a distinction between
> data structures and mathematical structures. Data structures are
> just another kind of "mathematical" object.

Oh, don't believe that I don't see data structures as mathematical 
structures. They are. But I rather have the feeling that for efficiency 
reasons it is desirable to have some basic data structures underlying 
the mathematics where one can say something about the complexity of the 
functions. After all that is a distincion between classic mathematics 
and constructive mathematics.

Example. You want to implement quicksort. Would someone choose lists to 
do that instead of arrays? Both basically represent the mathematical 
idea of tuples. But we care about the actual representation on a 
computer. Why does Axiom have distributed and recursive polynomials. 
Mathematically it's the same thing, so why bother?

I hope you get somehow the feeling what I meant when I said that I care 
for data structures of graphs. We all know that some representation is 
better than the other for certain algorithms.

Drawing the line between "data structures" and "mathematical structures" 
is hard if not impossible. But for data structures I somehow feel that 
their documentation should clearly say something about the complexity of 
operations.

> For example, is an Axiom set, i.e. a member of the domain Set, a
> data structure or a mathematical structure?

How expensive is it to add a new element to an existing set of type 
Set(T) where T has no ordering function?
How expensive is it to add a new element to Set(T) if T provides an 
ordering function?

I actually don't care about much about whether to call it "data 
structure" or "mathematical structure" since in a general sense the 
first is (as an abstract data type) clearly a mathematical object.
What I care about is stating complexity properties and providing a rich 
set of basic data structures for Axiom/Aldor.

Ralf