[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Axiom-developer] operations working in general, but not in special
From: |
Ralf Hemmecke |
Subject: |
Re: [Axiom-developer] operations working in general, but not in special cases -- help needed |
Date: |
Wed, 05 Apr 2006 12:23:36 +0200 |
User-agent: |
Thunderbird 1.5 (X11/20051201) |
Dear William,
I like most of what you have written, but I must oppose against a few
things.
Example 1, Matroids
A "matroid" is a mathematical structure with one very, very important
operation, namely "dualizing" which transforms a given matroid into
another. Thus, one is tempted to have a category "MatroidCat", which exports an
operation "dual: % -> %".
I assume you want MatroidCat to be the category of all matroids, in which case,
the dual operation is actually a domain constructor. That is, the above
signature cannot do what you are aiming for:
MatroidCat():Category == ... with
dual: % -> %
because the % refers to a particular implementation of a domain which is a
matroid, not the category itself.
Sorry, I have not yet read about Matroids, but in simple terms it is that
dual: % -> %
transforms a concrete matroid M=(E, I) to M^D=(E, I^D) but doing this by
assuming I^D = I (and thus M=M^D) which need of course not be the case).
So clearly that signiture is wrong.
> The argument to dual is an element of a
matroid. A plausible signature is:
dual:() -> MatroidCat()
which associates a matroid to the current matroid.
That sounds promising but here I must oppose. The reason is that the
resulting dual domain will probably be not very useful.
[snip]
But let's analyse this...
MatroidCat(): Category == Finite with
underlyingSet: () -> Finite
underlyingFamily: () -> Set %
span: Set % -> Set %
defining?: % -> Boolean -- true if set is in underlyingFamily()
independent?: Set % -> Boolean
circuit?: Set % -> Boolean
...
dualSet: () -> Set % -- constructs I^D
dual: () -> MatroidCat()
dual()==Matroid(underlyingSet(), dualSet())
...
Clearly, that category is very much involved and cannot be compiled
without knowing about the constructor Matroid(E, I). But it's not that
what I find problematic. It is the appearance of MatroidCat within the
"with" expression. What comes after the == depends on what comes before.
I cannot say, that I like this very much. Would you do something like
that in (mathematical) category theory? The "with" expression alone is
not a value until MatroidCat is known.
What else is bad is that the dual is always constructed by the domain
constructor Matroid. You don't allow other implementations (other
constructors).
Alternatively, instead of using functions dual(), you can have a domain
constructor:
DualSet(M:MatroidCat): Set Set underlyingSet M == ...
Dual(M:MatroidCat):MatroidCat ==
E:= underlyingSet(M)
I:=underlyingFamily(M)
J:=DualSet(M)
Matroid(E, J)
Well, that demonstrates what I mean by "the resulting dual domain will
probably be not very useful" above.
Suppose you create a very special matroid M which inherits from
MatroidCat but additionally from many other categories. If you now say
N == Dual(M)
you will get something that is constructed by the constructor Matroid
(which might actually not be that what you want -- remember there are
also several implementations of polynomials and they are all good for
something).
So the next idea would be something like
Dual(M: MatroidCat, MAT: ??? -> MatroidCat): MatroidCat ==
MAT(underlyingSet M, DualSet M);
Well, what can you do if you now say
N == Dual(M, MyMatroid)
? Actually not much, since that N is of type MatroidCat and nothing
more. No additional features are available even if MyMatroid would
return something of category MyMatroidCat that is much richer than
MatroidCat itself.
With the above Dual constructor, you explicitly restrict the exports to
MatroidCat. And I would have no other idea to add features than to use
"pretend". Brrrrrhhh.
A more practical implementation may have this outline:
MatroidCat(E:Finite, I:Set Set E): Category == Finite with
span: Set % -> Set %
independent?: Set % -> Boolean
circuit?: Set % -> Boolean
...
Matroid(E: SetCategory, I:Set Set E):MatroidCat(E,I) == ... with
DualSet(E:SetCategory, I:Set Set E):List List E ==
Dual(E:SetCategory, I:Set Set E):MatroidCat(E, DualSet(E,I)) == ...
I like that somehow much better, but the same "restriction process" as
above takes place. Things are not so easy with a dual functor.
If you do NOT want to implement dual as a domain constructor, then you may try
implementing Matroid as the DOMAIN of all matroids. However, Axiom does not
allow dependent types at the code level (only at the declaration level for
constructors).
Matroid(): SetCategory == ...
Rep:= Record(E:SetCategory, I:Set Set E)
probably won't work in Axiom, but Aldor may.
Did you really mean SetCategory? So to create a new element you would
write a function.
matroid(A: SetCategory, B: Set Set A): % == per [A, B];
and call it with
matroid(Integer, [[1,2], [3,4,5]]);
That sounds to me as follows: If E' \supset E and I \subseteq Power(E)
then the matroids (E, I) and (E', I) are the same. I cannot believe that.
Ralf
- [Axiom-developer] operations working in general, but not in special cases -- help needed, Martin Rubey, 2006/04/04
- Re: [Axiom-developer] operations working in general, but not in special cases -- help needed, Bertfried Fauser, 2006/04/04
- [Axiom-developer] Re: [Aldor-l] operations working in general, but not in special cases -- help needed, Ralf Hemmecke, 2006/04/04
- Re: [Axiom-developer] operations working in general, but not in special cases -- help needed, William Sit, 2006/04/04
- [Axiom-developer] Re: [Aldor-l] operations working in general, but not in special cases -- help needed, Christian Aistleitner, 2006/04/05