missing exports in Finite DirectProduct and Product

"Bill Page" <[email protected]> Wed, 17 Oct 2007 23:19:27 -0400
Newsgroups gmane.comp.mathematics.axiom.general
Message-ID <[email protected]>
Axiom Developers;

If the components of the cartesian product Product or DirectProduct
are domains in the category Finite then the product domain has Finite.
Unfortunately the current Axiom library code does not define all of
the required exports of Finite. For example:

(1) -> index(1)$DirectProduct(2,IntegerMod(3))
   Internal Error
   The function index with signature hashcode is missing from domain
      DirectProduct2(IntegerMod 3)

(1) -> index(1)$Product(OVAR [a,b],IntegerMod(3))
   Internal Error
   The function index with signature hashcode is missing from domain
      Product(OrderedVariableList (a b))(IntegerMod 3)

(1) -> DirectProduct(2,IntegerMod(3)) has Finite

   (1)  true
                                                                Type: Boolean

The attached file contains a patch against FriCAS Revision: 112 that
adds the missing operations 'index', 'lookup', and 'hash'.  The
operation 'size' is already available as a default.

Having 'index' available for products allows one to iterate over the
elements of a cross product like this:

  X:=Product(OVAR [a,b],IntegerMod(3))
  [index(i::PI)$X for i in 1..size()$X]

Note: Coercion to PositiveInteger (PI) is required because 'size'
returns an NonNegativeInteger (NNI) so i is of type NNI but index
expects an argument >= 1. Since the products export operations allow
acces to the components it is easy to write functions that map over
such lists.

Writing this made me think that it was also desirable the domains in
Finite also enumerate there members in a more functional manner so
because FriCAS now allows us to easily make fairly deep changes in the
algebra code, as an exercise I decided to define the following new
export of Finite

  expand: () -> List %

  expand() == [index(i::PositiveInteger) for i in 1..size()]

So with this patch one can write for example:

(1) -> map(x+->(selectsecond(x)::Symbol)^(selectfirst(x)::Integer), _
         expand()$Product(ZMOD(3),OVAR [a,b]))

              2  2
   (1)  [a,b,a ,b ,1,1]
                                                Type: List Expression Integer

------

I would be interested in your opinions about this approach to
providing Cartesian products for the Axiom library.

I think it is interesting to see how domains in the category Finite
able to participate like "sets" in the language. Of course it is also
possible to represent countably infinite sets in Axiom via the Stream
domain. This suggests the that the category constructor StepThrough
could also usefully be provided with an export that expands to such
Stream. Perhaps the underlying Spad language should support this sort
of expansion of Finite and countably infinite domains as a standard
form of iterator in the [ ... for i in ... ] construction?

Of course Aldor already has implemented some basic abstractions of
this kind but it is not entirely obvious to me how best to extend
Axiom's library and still stay within the limitations of the current
Spad language.

Regards,
Bill Page.

_______________________________________________
Axiom-math mailing list
[email protected]
http://lists.nongnu.org/mailman/listinfo/axiom-math
missing-finite-exports.patch (application/octet-stream, 6.8 KB)
Index: src/algebra/catdef.spad.pamphlet
===================================================================
--- src/algebra/catdef.spad.pamphlet	(revision 112)
+++ src/algebra/catdef.spad.pamphlet	(working copy)
@@ -795,7 +795,10 @@
         ++ lookup(x) returns a positive integer such that
         ++ \spad{x = index lookup x}.
       random: () -> %
-        ++ random() returns a random element from the set.
+        ++ random() returns a random element from the set
+      expand: () -> List %
+  add
+      expand() == [index(i::PositiveInteger) for i in 1..size()]
 
 @
 \section{category FLINEXP FullyLinearlyExplicitRingOver}
Index: src/algebra/product.spad.pamphlet
===================================================================
--- src/algebra/product.spad.pamphlet	(revision 112)
+++ src/algebra/product.spad.pamphlet	(working copy)
@@ -5,6 +5,10 @@
 \author{The Axiom Team}
 \maketitle
 \begin{abstract}
+This domain implements cartesian product for a pair of (possibly different) domains.
+If the underlying domains are both Finite then the resulting Product is also Finite
+and can be enumerated via size(), index(), location(), etc. The index of the second
+component (B) varies most quickly.
 \end{abstract}
 \eject
 \tableofcontents
@@ -64,9 +68,15 @@
           1 == [1$A,1$B]
           x * y == [x.acomp * y.acomp,x.bcomp * y.bcomp]
           x ** p == [x.acomp ** p ,x.bcomp ** p]
- 
+
        if A has Finite and B has Finite then
-          size == size$A () * size$B ()
+          size == size$A * size$B
+          index(n) == [index((((n::Integer-1) quo size$B )+1)::PositiveInteger)$A,
+                       index((((n::Integer-1) rem size$B )+1)::PositiveInteger)$B]
+          random() == [random()$A,random()$B]
+          lookup(x) == ((lookup(x.acomp)$A::Integer-1) * size$B::Integer +
+                        lookup(x.bcomp)$B::Integer)::PositiveInteger
+          hash(x) == hash(x.acomp)$A * size$B::SingleInteger + hash(x.bcomp)$B
  
        if A has Group and B has Group then
           inv(x) == [inv(x.acomp),inv(x.bcomp)]
Index: src/algebra/Makefile.pamphlet
===================================================================
--- src/algebra/Makefile.pamphlet	(revision 112)
+++ src/algebra/Makefile.pamphlet	(working copy)
@@ -384,7 +384,7 @@
         ATRIG BASTYPE BGAGG BRAGG BTAGG BTCAT CLAGG COMPCAT DIAGG \
         DIFEXT DIFRING DIOPS DIRPCAT DIVRING DPOLCAT DVARCAT ELAGG \
         ELEMFUN ELTAGG ES EUCDOM EVALAB FAMR FAXF FDIVCAT FEVALAB \
-        FFCAT FFIELDC FIELD FINAALG FINRALG FLAGG FLINEXP FPC FPS \
+        FFCAT FFIELDC FIELD FINAALG FINITE FINRALG FLAGG FLINEXP FPC FPS \
         FRAMALG FRETRCT FRNAALG FSAGG FS GCDDOM GRALG GRMOD GROUP \
         HOAGG HYPCAT IEVALAB INS INTDOM IXAGG KDAGG LALG LIECAT LNAGG \
         LODOCAT LOGIC LSAGG LZSTAGG MATCAT MODULE MONAD MONADWU \
Index: src/algebra/Makefile.in
===================================================================
--- src/algebra/Makefile.in	(revision 112)
+++ src/algebra/Makefile.in	(working copy)
@@ -293,7 +293,7 @@
         ATRIG BASTYPE BGAGG BRAGG BTAGG BTCAT CLAGG COMPCAT DIAGG \
         DIFEXT DIFRING DIOPS DIRPCAT DIVRING DPOLCAT DVARCAT ELAGG \
         ELEMFUN ELTAGG ES EUCDOM EVALAB FAMR FAXF FDIVCAT FEVALAB \
-        FFCAT FFIELDC FIELD FINAALG FINRALG FLAGG FLINEXP FPC FPS \
+        FFCAT FFIELDC FIELD FINAALG FINITE FINRALG FLAGG FLINEXP FPC FPS \
         FRAMALG FRETRCT FRNAALG FSAGG FS GCDDOM GRALG GRMOD GROUP \
         HOAGG HYPCAT IEVALAB INS INTDOM IXAGG KDAGG LALG LIECAT LNAGG \
         LODOCAT LOGIC LSAGG LZSTAGG MATCAT MODULE MONAD MONADWU \
Index: src/algebra/vector.spad.pamphlet
===================================================================
--- src/algebra/vector.spad.pamphlet	(revision 112)
+++ src/algebra/vector.spad.pamphlet	(working copy)
@@ -5,6 +5,37 @@
 \author{The Axiom Team}
 \maketitle
 \begin{abstract}
+VectorCategory, DirectProductCategory, Vector, IndexedVector, DirectProduct
+
+\spadtype{VectorCategory} represents the type of vector like objects,
+i.e. finite sequences indexed by some finite segment of the
+integers. The operations available on vectors depend on the structure
+of the underlying components. Many operations from the component domain
+are defined for vectors componentwise. It can by assumed that extraction or
+updating components can be done in constant time.
+
+\spadtype{IndexedVector} represents vector like objects with varying lengths
+and a user-specified initial index.
+
+\spadtype{Vector} represents vector like objects with varying lengths
+and indexed by a finite segment of integers starting at 1.
+
+\spadtype{DirectProductCategory} represents a finite cartesian product of
+a given type. Many categorical properties are preserved under this construction.
+
+\spadtype{DirectProduct} represents the finite direct or cartesian product
+of an underlying component type. This contrasts with simple vectors in that
+the members can be viewed as having constant length. Thus many
+categorical properties can by lifted from the underlying component type.
+Component extraction operations are provided but no updating operations.
+Thus new direct product elements can either be created by converting
+vector elements using the \spadfun{directProduct} function
+or by taking appropriate linear combinations of basis vectors provided
+by the \spad{unitVector} operation.
+
+If the underlying component type is Finite then the DirectProduct
+itself is Finite and may be enumerated via size() and index(). In this
+enumeration the index of the leftmost (nth)component varies most quickly.
 \end{abstract}
 \eject
 \tableofcontents
@@ -295,8 +326,6 @@
               column(rh, minColIndex rh)
             [reducedSystem(m)@Matrix(R), vh]
  
-      if R has Finite then size == size$R ** dim
- 
       if R has Field then
         x / b       == x * inv b
         dimension() == dim::CardinalNumber
@@ -357,8 +386,31 @@
         retractIfCan(z:%):Union(R, "failed") ==
           same? z => z(minIndex z)
           "failed"
+
+      if R has Finite then
+          size == size$R ** dim
+          index(n:PositiveInteger):% ==
+            N:Integer := size$R
+            p:Integer := n-1
+            L:List R := [index(((p rem N) + 1)::PositiveInteger)$R]
+            for i in 2..dim repeat
+              p := p quo N
+              L:=cons(index(((p rem N) + 1)::PositiveInteger)$R, L)
+            vector(L)
+          random() == [random()$R for i in 1..dim]
+          lookup(x) ==
+            N:Integer := size$R
+            L:Integer := lookup(x.1)-1
+            for i in 2..dim repeat
+              L:=L*N+lookup(x.i)-1
+            (L+1)::PositiveInteger
+          hash(x) ==
+            N := size$R::SingleInteger
+            L := hash(x.1)
+            for i in 2..dim repeat
+              L:=L*N+hash(x.i)
+            L 
  
- 
       if R has AbelianSemiGroup then
         u:% + v:% == map(_+ , u, v)$Rep