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

[Bill Page]

Gaby,

On November 13, 2006 10:17 PM you wrote:
> ... 
> [ Is it normal that I don't see Ralf's messages? ]
>

I believe that all messages that I received recently from Ralf are
here in the axiom-developer email archive:

http://lists.nongnu.org/archive/html/axiom-developer/2006-11/index.html

which means that under normal circumstances these would also have
been forwarded to you. Are you missing some?

> Bill Page writes:
> ...
> | 
> | All domains that have SetCategory are required to have a hash
> | into SmallInteger.
> 
> That is not a mathematical requirement.
>

I would tend to agree but perhaps Kurt Gödel would not have... ;-)

[Concerning the complexity of Set(T) for some type T ...]

> | I suppose that this means that the cost of adding
> | new elements is independent of Type T.
> 
> Why?
> 

hash makes testing equality O(1).

Axiom's implementation of Set is rather primitive.

See:

http://wiki.axiom-developer.org/axiom--test--1/src/algebra/SetsSpad

Set(S:SetCategory): FiniteSetAggregate S

...
++ \spad{insert(x,t)} and \spad{remove(x,t)} is \spad{O(n)}
...
      insert_!(x, s) ==
        for k in minIndex s .. maxIndex s repeat
          s.k = x => return s
        insert_!(x, s, inc maxIndex s)
...

Regards,
Bill Page.