* algebra/free.spad.pamphlet (FreeMonoidCategory): New.

	(FreeModule): Use it.
	* algebra/xpoly.spad.pamphlet (OrderedFreeMonoid): Likewise.

4 files changed, 75 insertions, 88 deletions

diff --git a/src/algebra/Makefile.in b/src/algebra/Makefile.in
index 4d3f88c8..6166e4f8 100644
--- a/src/algebra/Makefile.in
+++ b/src/algebra/Makefile.in
@@ -537,7 +537,7 @@ axiom_algebra_layer_9 = \
   PTFUNC2  RADCAT   RADCAT-  RATRET   RADUTIL  UPXS2    \
   XFALG    ZLINDEP  BBTREE                              \
                     ODEIFTBL NIPROB   ODEPROB  OPTPROB  \
-  PDEPROB  COLOR    SIG
+  PDEPROB  COLOR    SIG      FMONCAT
 
 
 axiom_algebra_layer_9_nrlibs = \
diff --git a/src/algebra/Makefile.pamphlet b/src/algebra/Makefile.pamphlet
index 1d75410b..ee5db924 100644
--- a/src/algebra/Makefile.pamphlet
+++ b/src/algebra/Makefile.pamphlet
@@ -539,7 +539,7 @@ axiom_algebra_layer_9 = \
   PTFUNC2  RADCAT   RADCAT-  RATRET   RADUTIL  UPXS2    \
   XFALG    ZLINDEP  BBTREE                              \
                     ODEIFTBL NIPROB   ODEPROB  OPTPROB  \
-  PDEPROB  COLOR    SIG
+  PDEPROB  COLOR    SIG      FMONCAT
 
 
 axiom_algebra_layer_9_nrlibs = \
diff --git a/src/algebra/free.spad.pamphlet b/src/algebra/free.spad.pamphlet
index 90588505..abfb0e65 100644
--- a/src/algebra/free.spad.pamphlet
+++ b/src/algebra/free.spad.pamphlet
@@ -164,6 +164,72 @@ ListMonoidOps(S, E, un): Exports == Implementation where
       g
 
 @
+
+\section{A Category for Free Monoids}
+
+<<category FMONCAT FreeMonoidCategory>>=
+)abbrev category FMONCAT FreeMonoidCategory
+++ Free monoid on any set of generators
+++ Author: Stephen M. Watt, Gabriel Dos Reis
+++ Date Created: September 26, 2009
+++ Date Last Updated: September 26, 2009
+++ Description:
+++   A free monoid on a set S is the monoid of finite products of
+++   the form \spad{reduce(*,[si ** ni])} where the si's are in S, and the ni's
+++   are nonnegative integers. The multiplication is not commutative.
+FreeMonoidCategory(S: SetCategory): Category == Exports where
+  macro NNI == NonNegativeInteger
+  macro REC == Record(gen: S, exp: NonNegativeInteger)
+  macro Ex  == OutputForm
+
+  Exports == Join(Monoid, RetractableTo S) with
+    *:    (S, %) -> %
+      ++ \spad{s * x} returns the product of \spad{x} by \spad{s} on the left.
+    *:    (%, S) -> %
+      ++ \spad{x * s} returns the product of \spad{x} by \spad{s} on the right.
+    **:   (S, NonNegativeInteger) -> %
+      ++ \spad{s ** n} returns the product of \spad{s} by itself \spad{n} times.
+    hclf:   (%, %) -> %
+      ++ \spad{hclf(x, y)} returns the highest common left factor of
+      ++ \spad{x} and \spad{y},
+      ++ i.e. the largest d such that \spad{x = d a} and \spad{y = d b}.
+    hcrf:   (%, %) -> %
+      ++ hcrf(x, y) returns the highest common right factor of x and y,
+      ++ i.e. the largest d such that \spad{x = a d} and \spad{y = b d}.
+    lquo:   (%, %) -> Union(%, "failed")
+      ++ lquo(x, y) returns the exact left quotient of x by y i.e.
+      ++ q such that \spad{x = y * q},
+      ++ "failed" if x is not of the form \spad{y * q}.
+    rquo:   (%, %) -> Union(%, "failed")
+      ++ rquo(x, y) returns the exact right quotient of x by y i.e.
+      ++ q such that \spad{x = q * y},
+      ++ "failed" if x is not of the form \spad{q * y}.
+    divide:   (%, %) -> Union(Record(lm: %, rm: %), "failed")
+      ++ divide(x, y) returns the left and right exact quotients of
+      ++ x by y, i.e. \spad{[l, r]} such that \spad{x = l * y * r},
+      ++ "failed" if x is not of the form \spad{l * y * r}.
+    overlap: (%, %) -> Record(lm: %, mm: %, rm: %)
+      ++ overlap(x, y) returns \spad{[l, m, r]} such that
+      ++ \spad{x = l * m}, \spad{y = m * r} and l and r have no overlap,
+      ++ i.e. \spad{overlap(l, r) = [l, 1, r]}.
+    size         :   % -> NNI
+      ++ size(x) returns the number of monomials in x.
+    factors      : % -> List Record(gen: S, exp: NonNegativeInteger)
+      ++ factors(a1\^e1,...,an\^en) returns \spad{[[a1, e1],...,[an, en]]}.
+    nthExpon     : (%, Integer) -> NonNegativeInteger
+      ++ nthExpon(x, n) returns the exponent of the n^th monomial of x.
+    nthFactor    : (%, Integer) -> S
+      ++ nthFactor(x, n) returns the factor of the n^th monomial of x.
+    mapExpon     : (NNI -> NNI, %) -> %
+      ++ mapExpon(f, a1\^e1 ... an\^en) returns \spad{a1\^f(e1) ... an\^f(en)}.
+    mapGen       : (S -> S, %) -> %
+      ++ mapGen(f, a1\^e1 ... an\^en) returns \spad{f(a1)\^e1 ... f(an)\^en}.
+    if S has OrderedSet then OrderedSet
+
+@
+
+
+
 \section{domain FMONOID FreeMonoid}
 <<domain FMONOID FreeMonoid>>=
 )abbrev domain FMONOID FreeMonoid
@@ -175,55 +241,11 @@ ListMonoidOps(S, E, un): Exports == Implementation where
 ++ The free monoid on a set S is the monoid of finite products of
 ++ the form \spad{reduce(*,[si ** ni])} where the si's are in S, and the ni's
 ++ are nonnegative integers. The multiplication is not commutative.
-FreeMonoid(S: SetCategory): FMcategory == FMdefinition where
-    NNI ==> NonNegativeInteger
-    REC ==> Record(gen: S, exp: NonNegativeInteger)
-    Ex  ==> OutputForm
-
-    FMcategory ==> Join(Monoid, RetractableTo S) with
-        *:    (S, $) -> $
-          ++ s * x returns the product of x by s on the left.
-        *:    ($, S) -> $
-          ++ x * s returns the product of x by s on the right.
-        **:   (S, NonNegativeInteger) -> $
-          ++ s ** n returns the product of s by itself n times.
-        hclf:   ($, $) -> $
-          ++ hclf(x, y) returns the highest common left factor of x and y,
-          ++ i.e. the largest d such that \spad{x = d a} and \spad{y = d b}.
-        hcrf:   ($, $) -> $
-          ++ hcrf(x, y) returns the highest common right factor of x and y,
-          ++ i.e. the largest d such that \spad{x = a d} and \spad{y = b d}.
-        lquo:   ($, $) -> Union($, "failed")
-          ++ lquo(x, y) returns the exact left quotient of x by y i.e.
-          ++ q such that \spad{x = y * q},
-          ++ "failed" if x is not of the form \spad{y * q}.
-        rquo:   ($, $) -> Union($, "failed")
-          ++ rquo(x, y) returns the exact right quotient of x by y i.e.
-          ++ q such that \spad{x = q * y},
-          ++ "failed" if x is not of the form \spad{q * y}.
-        divide:   ($, $) -> Union(Record(lm: $, rm: $), "failed")
-          ++ divide(x, y) returns the left and right exact quotients of
-          ++ x by y, i.e. \spad{[l, r]} such that \spad{x = l * y * r},
-          ++ "failed" if x is not of the form \spad{l * y * r}.
-        overlap: ($, $) -> Record(lm: $, mm: $, rm: $)
-          ++ overlap(x, y) returns \spad{[l, m, r]} such that
-          ++ \spad{x = l * m}, \spad{y = m * r} and l and r have no overlap,
-          ++ i.e. \spad{overlap(l, r) = [l, 1, r]}.
-        size         :   $ -> NNI
-          ++ size(x) returns the number of monomials in x.
-        factors      : $ -> List Record(gen: S, exp: NonNegativeInteger)
-          ++ factors(a1\^e1,...,an\^en) returns \spad{[[a1, e1],...,[an, en]]}.
-        nthExpon     : ($, Integer) -> NonNegativeInteger
-          ++ nthExpon(x, n) returns the exponent of the n^th monomial of x.
-        nthFactor    : ($, Integer) -> S
-          ++ nthFactor(x, n) returns the factor of the n^th monomial of x.
-        mapExpon     : (NNI -> NNI, $) -> $
-          ++ mapExpon(f, a1\^e1 ... an\^en) returns \spad{a1\^f(e1) ... an\^f(en)}.
-        mapGen       : (S -> S, $) -> $
-          ++ mapGen(f, a1\^e1 ... an\^en) returns \spad{f(a1)\^e1 ... f(an)\^en}.
-        if S has OrderedSet then OrderedSet
-
-    FMdefinition ==> ListMonoidOps(S, NonNegativeInteger, 1) add
+FreeMonoid(S: SetCategory): FreeMonoidCategory(S) == FMdefinition where
+    macro NNI == NonNegativeInteger
+    macro REC == Record(gen: S, exp: NonNegativeInteger)
+    macro Ex  == OutputForm
+    FMdefinition == ListMonoidOps(S, NonNegativeInteger, 1) add
         Rep := ListMonoidOps(S, NonNegativeInteger, 1)
 
         1               == makeUnit()
@@ -583,6 +605,7 @@ FreeAbelianGroup(S:SetCategory): Exports == Implementation where
 <<license>>
 
 <<domain LMOPS ListMonoidOps>>
+<<category FMONCAT FreeMonoidCategory>>
 <<domain FMONOID FreeMonoid>>
 <<domain FGROUP FreeGroup>>
 <<category FAMONC FreeAbelianMonoidCategory>>
diff --git a/src/algebra/xpoly.spad.pamphlet b/src/algebra/xpoly.spad.pamphlet
index e3c176c1..a862c711 100644
--- a/src/algebra/xpoly.spad.pamphlet
+++ b/src/algebra/xpoly.spad.pamphlet
@@ -42,13 +42,7 @@ OrderedFreeMonoid(S: OrderedSet): OFMcategory == OFMdefinition where
     NNI ==> NonNegativeInteger
     REC ==> Record(gen:S, exp:NNI)
  
-    OFMcategory == Join(OrderedMonoid, RetractableTo S) with
-        *:    (S, %) -> %
-          ++ \spad{s * x} returns the product of \spad{x} by \spad{s} on the left.
-        *:    (%, S) -> %
-          ++ \spad{x * s} returns the product of \spad{x} by \spad{s} on the right.
-        **:   (S, NNI) -> %
-          ++ \spad{s ** n} returns the product of \spad{s} by itself \spad{n} times.
+    OFMcategory == Join(FreeMonoidCategory S,OrderedSet) with
         first: % -> S
           ++ \spad{first(x)} returns the first letter of \spad{x}.
         rest:  % -> %
@@ -58,22 +52,6 @@ OrderedFreeMonoid(S: OrderedSet): OFMcategory == OFMdefinition where
         lexico: (%,%) -> Boolean
           ++ \spad{lexico(x,y)} returns \spad{true} iff \spad{x} is smaller than \spad{y}
           ++ w.r.t. the pure lexicographical ordering induced by \spad{S}.
-        hclf:   (%, %) -> %
-          ++ \spad{hclf(x, y)} returns the highest common left factor 
-          ++ of \spad{x} and \spad{y},
-          ++ that is the largest \spad{d} such that \spad{x = d a} and \spad{y = d b}.
-        hcrf:   (%, %) -> %
-          ++ \spad{hcrf(x, y)} returns the highest common right 
-          ++ factor of \spad{x} and \spad{y},
-          ++ that is the largest \spad{d} such that \spad{x = a d} and \spad{y = b d}.
-        lquo:   (%, %) -> Union(%, "failed")
-          ++ \spad{lquo(x, y)} returns the exact left quotient of \spad{x}
-          ++  by \spad{y} that is \spad{q} such that \spad{x = y * q},
-          ++ "failed" if \spad{x} is not of the form \spad{y * q}.
-        rquo:   (%, %) -> Union(%, "failed")
-          ++ \spad{rquo(x, y)} returns the exact right quotient of \spad{x} 
-          ++ by \spad{y} that is \spad{q} such that \spad{x = q * y},
-          ++ "failed" if \spad{x} is not of the form \spad{q * y}.
         lquo:   (%, S) -> Union(%, "failed")
           ++ \spad{lquo(x, s)} returns the exact left quotient of \spad{x} 
           ++ by \spad{s}. 
@@ -84,21 +62,7 @@ OrderedFreeMonoid(S: OrderedSet): OFMcategory == OFMdefinition where
           ++ \spad{x div y} returns the left and right exact quotients of
           ++ \spad{x} by \spad{y}, that is \spad{[l, r]} such that \spad{x = l * y * r}.
           ++ "failed" is returned iff \spad{x} is not of the form \spad{l * y * r}.
-        overlap: (%, %) -> Record(lm: %, mm: %, rm: %)
-          ++ \spad{overlap(x, y)} returns \spad{[l, m, r]} such that
-          ++ \spad{x = l * m} and \spad{y = m * r} hold and such that 
-          ++ \spad{l} and \spad{r} have no overlap,
-          ++ that is \spad{overlap(l, r) = [l, 1, r]}.
-        size:   % -> NNI
-          ++ \spad{size(x)} returns the number of monomials in \spad{x}.
-        nthExpon:  (%, Integer) -> NNI
-          ++ \spad{nthExpon(x, n)} returns the exponent of the 
-          ++ \spad{n-th} monomial of \spad{x}.
-        nthFactor: (%, Integer) -> S
-          ++ \spad{nthFactor(x, n)} returns the factor of the \spad{n-th} 
           ++ monomial of \spad{x}.
-        factors: % -> List REC
-          ++ \spad{factors(a1\^e1,...,an\^en)} returns \spad{[[a1, e1],...,[an, en]]}.
         length: % -> NNI
           ++ \spad{length(x)} returns the length of \spad{x}.
         varList: % -> List S