
From:  Ralf Hemmecke 
Subject:  data structure vs. mathematical structure (was: [Axiomdeveloper] Graph theory) 
Date:  Sat, 11 Nov 2006 17:10:52 +0100 
Useragent:  Thunderbird 1.5.0.8 (X11/20061025) 
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
[Prev in Thread]  Current Thread  [Next in Thread] 