Edit detail for FreeModule revision 6 of 8

A bi-module is a free module over a ring with generators indexed by an ordered set. Each element can be expressed as a finite linear combination of generators. Only non-zero terms are stored.

This domain implements linear combinations of elements from the domain S with coefficients in the domain R where S is an ordered set and R is a ring (which may be non-commutative).

Ref: http://en.wikipedia.org/wiki/Free_module

)sh FreeModule

 FreeModule(R: Join(SemiRng,AbelianMonoid),S: Comparable) is a domain constructor
 Abbreviation for FreeModule is FM 
 This constructor is not exposed in this frame.
------------------------------- Operations --------------------------------

 ?*? : (R, S) -> %                     ?*? : (S, R) -> %
 ?*? : (%, R) -> %                     ?*? : (R, %) -> %
 ?*? : (PositiveInteger, %) -> %       ?+? : (%, %) -> %
 -? : % -> % if R has ABELGRP          ?=? : (%, %) -> Boolean
 coefficient : (%, S) -> R             coefficients : % -> List(R)
 coerce : % -> OutputForm              hash : % -> SingleInteger
 latex : % -> String                   leadingCoefficient : % -> R
 leadingMonomial : % -> %              leadingSupport : % -> S
 map : ((R -> R), %) -> %              monomial : (R, S) -> %
 monomial? : % -> Boolean              monomials : % -> List(%)
 reductum : % -> %                     support : % -> List(S)
 ?~=? : (%, %) -> Boolean             
 ?*? : (Integer, %) -> % if R has ABELGRP
 ?*? : (NonNegativeInteger, %) -> % if R has ABELMON or R has OAMON and S has ORDSET or R has OAMONS and S has ORDSET
 ?-? : (%, %) -> % if R has ABELGRP
 ?<? : (%, %) -> Boolean if R has OAMON and S has ORDSET or R has OAMONS and S has ORDSET
 ?<=? : (%, %) -> Boolean if R has OAMON and S has ORDSET or R has OAMONS and S has ORDSET
 ?>? : (%, %) -> Boolean if R has OAMON and S has ORDSET or R has OAMONS and S has ORDSET
 ?>=? : (%, %) -> Boolean if R has OAMON and S has ORDSET or R has OAMONS and S has ORDSET
 0 : () -> % if R has ABELMON or R has OAMON and S has ORDSET or R has OAMONS and S has ORDSET
 coerce : S -> % if R has SRING
 construct : List(Record(k: S,c: R)) -> %
 constructOrdered : List(Record(k: S,c: R)) -> %
 hashUpdate! : (HashState, %) -> HashState
 leadingTerm : % -> Record(k: S,c: R)
 linearExtend : ((S -> R), %) -> R if R has COMRING
 listOfTerms : % -> List(Record(k: S,c: R))
 max : (%, %) -> % if R has OAMON and S has ORDSET or R has OAMONS and S has ORDSET
 min : (%, %) -> % if R has OAMON and S has ORDSET or R has OAMONS and S has ORDSET
 numberOfMonomials : % -> NonNegativeInteger
 opposite? : (%, %) -> Boolean if R has ABELMON or R has OAMON and S has ORDSET or R has OAMONS and S has ORDSET
 retract : % -> S if R has SRING
 retractIfCan : % -> Union(S,"failed") if R has SRING
 sample : () -> % if R has ABELMON or R has OAMON and S has ORDSET or R has OAMONS and S has ORDSET
 smaller? : (%, %) -> Boolean if R has COMPAR or R has OAMON and S has ORDSET or R has OAMONS and S has ORDSET
 subtractIfCan : (%, %) -> Union(%,"failed") if R has ABELGRP or R has CABMON or R has OAMONS and S has ORDSET
 sup : (%, %) -> % if R has OAMONS and S has ORDSET
 zero? : % -> Boolean if R has ABELMON or R has OAMON and S has ORDSET or R has OAMONS and S has ORDSET

See: [PolySpad]?

FreeModule(Fraction Integer,OrderedVariableList [e1,e1]) has VectorSpace(Fraction Integer)

(1)

Ref: http://en.wikipedia.org/wiki/Vector_space#Modules

Add:

        if R has Field then VectorSpace(R)
        ...
        if R has Field then
          if S has Finite then
            dimension():CardinalNumber == coerce size()$S
          else
             dimension():CardinalNumber == Aleph(0)

)abbrev category FMCAT FreeModuleCategory
++ Author: Michel Petitot petitot@lifl.fr
++ Date Created: 91
++ Date Last Updated: 7 Juillet 92
++ Fix History: compilation v 2.1 le 13 dec 98
++ Basic Functions:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++   A domain of this category
++   implements formal linear combinations
++   of elements from a domain \spad{Basis} with coefficients
++   in a domain \spad{R}. The domain \spad{Basis} needs only
++   to belong to the category \spadtype{SetCategory} and \spad{R}
++   to the category \spadtype{Ring}. Thus the coefficient ring
++   may be non-commutative.
++   See the \spadtype{XDistributedPolynomial} constructor
++   for examples of domains built with the \spadtype{FreeModuleCategory}
++   category constructor.
++   Author: Michel Petitot (petitot@lifl.fr)
++
++   Note (Franz Lehner, June 2009):
++   Since \spad{leadingTerm} makes no sense
++   for unordered base sets,
++   and at the time of this writing this domain was never used for such,
++   it was changed to \spad{OrderedSet}.
++   \spad{FreeModule} originally was not of FreeModuleCategory.
++   Some functions (like \spad{support}, \spad{coefficients},
++   \spad{monomials}, ...) from here could be moved to
++   \spad{IndexedDirectProductCategory}
++   but at the moment there is no need for this.
FreeModuleCategory(R, S):Category == Exports where
   R: Ring
   S: OrderedSet
   Term ==> Record(k: S, c: R)

   Exports == Join(BiModule(R,R), RetractableTo S, IndexedDirectProductCategory(R,S)) with
        "*"                : (R, S) -> %
          ++ \spad{r*b} returns the product of \spad{r} by \spad{b}.
        "*":(S,R) -> %
          ++ \spad{s*r} returns the product \spad{r*s}
          ++ used by \spadtype{XRecursivePolynomial}
        coefficients       : % -> List R
          ++ \spad{coefficients(x)} returns the list of coefficients of \spad{x}.
        support            : % -> List S
          ++ \spad{support(x)} returns the list of basis elements with nonzero coefficients.
        monomials          : % -> List %
          ++ \spad{monomials(x)} returns the list of \spad{r_i*b_i}
          ++ whose sum is \spad{x}.
        numberOfMonomials  : % -> NonNegativeInteger
          ++ \spad{numberOfMonomials(x)} returns the number of monomials of \spad{x}.
        monomial?: % -> Boolean
          ++ \spad{monomial?(x)} returns true if \spad{x} contains a single
          ++ monomial.
        leadingMonomial    : % -> S
          ++ \spad{leadingMonomial(x)} returns the first element from \spad{S}
          ++ which appears in \spad{listOfTerms(x)}.
        leadingCoefficient : % -> R
          ++ \spad{leadingCoefficient(x)} returns the first coefficient
          ++ which appears in \spad{listOfTerms(x)}.
        monom : (S, R) -> %
          ++ \spad{monom(s,r)} returns the product of the basis element \spad{s} by the coefficient \spad{r}.
        coefficient :(%,S) -> R
          ++ \spad{coefficient(x,s)} returns the coefficient of the basis element s
        -- attributes
        if R has Field then VectorSpace(R)
        if R has CommutativeRing then
             Module(R)
             linearExtend:(S->R,%)->R
          ++ \spad{linearExtend:(f,x)} returns the linear extension
          ++ of a map defined on the basis applied to a linear combination
        if R has Comparable then Comparable
      add
        if R has Field then
          if S has Finite then
            dimension():CardinalNumber == coerce size()$S
          else
             dimension():CardinalNumber == Aleph(0)
        if R has Comparable then
          smaller?(p:%,q:%):Boolean ==
            if leadingMonomial(p)=leadingMonomial(q) then
              if leadingCoefficient(p)=leadingCoefficient(q) then
                smaller?(reductum p, reductum q)
              else
                smaller?(leadingCoefficient(p),leadingCoefficient(q))
            leadingMonomial(p)<leadingMonomial(q)

   Compiling FriCAS source code from file 
      /var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/5194433629109442357-25px003.spad
      using old system compiler.
   FMCAT abbreviates category FreeModuleCategory 
------------------------------------------------------------------------
   initializing NRLIB FMCAT for FreeModuleCategory 
   compiling into NRLIB FMCAT 

;;;     ***       |FreeModuleCategory| REDEFINED
Time: 0.02 SEC.

   FMCAT- abbreviates domain FreeModuleCategory& 
------------------------------------------------------------------------
   initializing NRLIB FMCAT- for FreeModuleCategory& 
   compiling into NRLIB FMCAT- 
****** Domain: R already in scope
augmenting R: (Field)
****** Domain: S already in scope
augmenting S: (Finite)
   compiling exported dimension : () -> CardinalNumber
Time: 0.02 SEC.

   compiling exported dimension : () -> CardinalNumber
Time: 0.01 SEC.

****** Domain: R already in scope
augmenting R: (Comparable)
   compiling exported smaller? : (A,A) -> Boolean
Time: 0 SEC.

(time taken in buildFunctor:  0)

;;;     ***       |FreeModuleCategory&| REDEFINED
Time: 0 SEC.

   Cumulative Statistics for Constructor FreeModuleCategory&
      Time: 0.03 seconds

   finalizing NRLIB FMCAT- 
   Processing FreeModuleCategory& for Browser database:
--------constructor---------
--------(* (% R S))---------
--------(* (% S R))---------
--------(coefficients ((List R) %))---------
--------(support ((List S) %))---------
--------(monomials ((List %) %))---------
--------(numberOfMonomials ((NonNegativeInteger) %))---------
--------(monomial? ((Boolean) %))---------
--------(leadingMonomial (S %))---------
--------(leadingCoefficient (R %))---------
--------(monom (% S R))---------
--------(coefficient (R % S))---------
--------(linearExtend (R (Mapping R S) %))---------
; compiling file "/var/aw/var/LatexWiki/FMCAT-.NRLIB/FMCAT-.lsp" (written 25 FEB 2018 07:07:18 PM):

; /var/aw/var/LatexWiki/FMCAT-.NRLIB/FMCAT-.fasl written
; compilation finished in 0:00:00.025
------------------------------------------------------------------------
   FreeModuleCategory& is now explicitly exposed in frame initial 
   FreeModuleCategory& will be automatically loaded when needed from 
      /var/aw/var/LatexWiki/FMCAT-.NRLIB/FMCAT-
   finalizing NRLIB FMCAT 
   Processing FreeModuleCategory for Browser database:
--------constructor---------
--------(* (% R S))---------
--------(* (% S R))---------
--------(coefficients ((List R) %))---------
--------(support ((List S) %))---------
--------(monomials ((List %) %))---------
--------(numberOfMonomials ((NonNegativeInteger) %))---------
--------(monomial? ((Boolean) %))---------
--------(leadingMonomial (S %))---------
--------(leadingCoefficient (R %))---------
--------(monom (% S R))---------
--------(coefficient (R % S))---------
--------(linearExtend (R (Mapping R S) %))---------
; compiling file "/var/aw/var/LatexWiki/FMCAT.NRLIB/FMCAT.lsp" (written 25 FEB 2018 07:07:18 PM):

; /var/aw/var/LatexWiki/FMCAT.NRLIB/FMCAT.fasl written
; compilation finished in 0:00:00.004
------------------------------------------------------------------------
   FreeModuleCategory is now explicitly exposed in frame initial 
   FreeModuleCategory will be automatically loaded when needed from 
      /var/aw/var/LatexWiki/FMCAT.NRLIB/FMCAT

)abbrev domain FM FreeModule
++ Author: Dave Barton, James Davenport, Barry Trager
++ Date Created:
++ Date Last Updated:
++ Basic Functions: BiModule(R,R)
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ A bi-module is a free module
++ over a ring with generators indexed by an ordered set.
++ Each element can be expressed as a finite linear combination of
++ generators. Only non-zero terms are stored.

++ old domain FreeModule1 was merged to it in May 2009
++ The description of the latter:
++   This domain implements linear combinations
++   of elements from the domain \spad{S} with coefficients
++   in the domain \spad{R} where \spad{S} is an ordered set
++   and \spad{R} is a ring (which may be non-commutative).
++   This domain is used by domains of non-commutative algebra such as:
++       \spadtype{XDistributedPolynomial},
++       \spadtype{XRecursivePolynomial}.
++   Author: Michel Petitot (petitot@lifl.fr)

FreeModule(R:Ring,S:OrderedSet):
        Join(BiModule(R,R),FreeModuleCategory(R,S)) with
    if R has CommutativeRing then Module(R)
 == IndexedDirectProductAbelianGroup(R,S) add
    --representations
       Term ==>  Record(k:S,c:R)
       Rep :=  List Term
    --declarations
       x,y: %
       r: R
       n: Integer
       f: R -> R
       s: S
       lt: List Term
   --define
       if R has EntireRing then
         r * x  ==
             zero? r => 0
--             one? r => x
             (r = 1) => x
           --map(x+->r*x1,x)
             [[u.k,r*u.c] for u in x ]
       else
         r * x  ==
             zero? r => 0
--             one? r => x
             (r = 1) => x
           --map(x1+->r*x1,x)
             [[u.k,a] for u in x | (a:=r*u.c) ~= 0$R]
       if R has EntireRing then
         x * r  ==
             zero? r => 0
--             one? r => x
             (r = 1) => x
           --map(x1+->r*x1,x)
             [[u.k,u.c*r] for u in x ]
       else
         x * r  ==
             zero? r => 0
--             one? r => x
             (r = 1) => x
           --map(x1+->r*x1,x)
             [[u.k,a] for u in x | (a:=u.c*r) ~= 0$R]

       r * s ==
         r = 0 => 0
         [[s,r]$Term]

       s * r ==
         r = 0 => 0
         [[s,r]$Term]

       coerce(x) : OutputForm ==
         null x => (0$R) :: OutputForm
         le : List OutputForm := nil
         for rec in reverse x repeat
           rec.c = 1 => le := cons(rec.k :: OutputForm, le)
           le := cons(rec.c :: OutputForm *  rec.k :: OutputForm, le)
         reduce("+",le)

       leadingMonomial x == x.first.k

       support x == [t.k for t in x]

       coefficients x == [t.c for t in x]

       monomials x == [ monom (t.k, t.c) for t in x]

       retractIfCan x ==
         numberOfMonomials(x) ~= 1 => "failed"
         x.first.c = 1 => x.first.k
         "failed"

       retract x ==
         (rr := retractIfCan x) case "failed" => error "FM1.retract impossible"
         rr :: S

       coerce(s:S):% == [[s,1$R]]

-- the following is to be replaced by monomial(r,b) everywhere
       monom(b,r):% == [[b,r]$Term]

       coefficient(x,s) ==
         null x => 0$R
         x.first.k > s => coefficient(rest x,s)
         x.first.k = s => x.first.c
         0$R

       monomial? x ==
         numberOfMonomials x = 1

       listOfTerms(x) ==
--          (x::Rep)
--          coerce(x)@Rep
         x pretend Rep

       numberOfMonomials x == # (listOfTerms x)

       if R has CommutativeRing then
           f:S->R
           x:%
           t:Term
           linearExtend(f,x) ==
               zero? x => 0
               res:R:= 0
               for t in listOfTerms x repeat
                   res := res + (t c)*f(t k)
               res

   Compiling FriCAS source code from file 
      /var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/1868799774806656872-25px004.spad
      using old system compiler.
   FM abbreviates domain FreeModule 
------------------------------------------------------------------------
   initializing NRLIB FM for FreeModule 
   compiling into NRLIB FM 
****** comp fails at level 1 with expression: ******
((|IndexedDirectProductAbelianGroup| R S))
****** level 1  ******
$x:= (IndexedDirectProductAbelianGroup R S)
$m:= $EmptyMode
$f:=
((((~= #) (= #) (|coerce| #) (|hash| #) ...)))

   >> Apparent user error:
   cannot compile (IndexedDirectProductAbelianGroup R S)

F2:=FreeModule(Fraction Integer,OrderedVariableList [e1,e1])

(2)

F2 has VectorSpace(Fraction Integer)

(3)

dimension()$F2

   The function dimension is not implemented in FreeModule(Fraction(
      Integer),OrderedVariableList([e1,e1])) .