groups.dtx

% 
% \iffalse
%<*driver>
\documentclass{mtmtcl}
\begin{document}
\DocInput{groups.dtx}
\PrintIndex
\end{document}
%</driver>
% \fi
% 
% 
% \part{Groups and variants}
% 
% While basic courses in abstract algebra typically begin with groups 
% or fields, there is also the ``Bourbaki'' style of beginning with a 
% magma (set with one binary operation not known to satisfy any 
% axioms). Going that far is not immediately useful, but semigroups and 
% monoids have the direct applications that it is not necessary to 
% separately define associative rings and associative unital rings, 
% since these are the same things as rings which also satisfy the 
% axioms for a semigroup and monoid, respectively.
% 
% Implementation-wise, there is one package |mtmtcl::groups::util| 
% which collects utility commands that are useful for several groups, 
% and some number of sibling packages which implement particular 
% groups (or families of groups). For historical reasons, there is 
% also a docstrip module {\Module{pkg}} which pretty much includes 
% all code (sans that for package handling). The trend is to migrate 
% code from this big combination to functionality-specific packages. 
% The {\Module{common}} module is for code common to such packages 
% (namely the |mtmtcl::groups| namespace declaration).
% \begin{tcl}
%<pkg,common>namespace eval ::mtmtcl::groups {}
%<*docstrip.tcl::catalogue>
pkgProvide mtmtcl::groups::util 1.0 util
%</docstrip.tcl::catalogue>
%<util,pkg>namespace eval ::mtmtcl::groups::util {}
% \end{tcl}
% \setnamespace{mtmtcl::groups}
% 
% 
% \section{Basic versions}
% 
% The general trend for \texttt{group} and other group-related 
% interface classes is that version~1.0 provides the fundamental 
% operations, whereas higher version numbers add more and more derived 
% operations (variadic operation, powers, power products). The 
% \texttt{semigroup}, \texttt{monoid}, and \texttt{group} interfaces 
% all employ a multiplicative notation; see \tclverb*|additive group| 
% for the additive counterpart.
% 
% 
% \begin{APIspec}{semigroup}{1.0}
%   The \texttt{semigroup} interface (v\,1.0) prescribes two methods: 
%   the binary operation |*| and the equality relation |=|.
%   \begin{APIdescription}{semigroup}
%     \begin{APImethod}{=}
%       \word{element} \word{element}
%     \end{APImethod}
%       The |=| method satisfies version~1.0 of the \texttt{equality} 
%       interface.
%       
%     \begin{APImethod}{*}
%       \word{element} \word{element}
%     \end{APImethod}
%       The |*| method is an associative binary operation. This implies 
%       that every \meta{semigroup} $G$ must have the property that the 
%       two expressions
%       \begin{displaysyntax}
%         [$G$ * [$G$ * $a$ $b$] $c$]\par
%         [$G$ * $a$ [$G$ * $b$ $c$]]
%       \end{displaysyntax}
%       are |=|-equal for all elements $a$, $b$, and $c$.
%   \end{APIdescription}
%   The |*| method is congruent.
% \end{APIspec}
% 
% \begin{APIspec}{monoid}{1.0}
%   The \texttt{monoid} interface is an extension of \texttt{semigroup} 
%   which adds a multiplicative unit method.
%   \begin{APIdescription}{monoid}
%     \begin{APImethod}{=}
%       \word{element} \word{element}
%     \end{APImethod}
%       The |=| method satisfies version~1.0 of the \texttt{equality} 
%       interface.
%       
%     \begin{APImethod}{*}
%       \word{element} \word{element}
%     \end{APImethod}
%       The |*| method satisfies version~1.0 of the \texttt{semigroup} 
%       interface.
%       
%     \begin{APImethod}{1}
%     \end{APImethod}
%       The |1| method returns the identity element of the monoid. The 
%       relevant axiom says that the three expressions
%       \begin{displaysyntax}
%         [$G$ * [$G$ 1] $a$]\par
%         [$G$ * $a$ [$G$ 1]]\par
%         $a$
%       \end{displaysyntax}
%       are |=|-equal for every element $a$ of the \meta{monoid} $G$.
%   \end{APIdescription}
%   All methods are congruent.
% \end{APIspec}
% 
% \begin{proc}{string_free_monoid}
%   This procedure is implements the free \texttt{monoid} of 
%   strings (over the Unicode alphabet). The overall syntax is
%   \begin{displaysyntax}
%     |::mtmtcl::groups::string_free_monoid|
%     \word{subcommand} \word{argument}\regstar
%   \end{displaysyntax}
%   and the implemented subcommands are |API|, |=|, |*|, and |1|.
%   \begin{tcl}
%<*docstrip.tcl::catalogue>
pkgProvide mtmtcl::groups::string_free_monoid 1.0 {stringmonoid common}
%</docstrip.tcl::catalogue>
%<*pkg,stringmonoid>
proc ::mtmtcl::groups::string_free_monoid {method args} {
   switch -- $method {
%   \end{tcl}
%   \begin{procmethod}{=}
%     String equality is implemented by the \Tcl\ core.
%     \begin{tcl}
      = {string equal [lindex $args 0] [lindex $args 1]}
%     \end{tcl}
%   \end{procmethod}
%   
%   \begin{procmethod}{*}
%     The product of two lists is their concatenation. 
%     \begin{tcl}
      * {join $args ""}
%     \end{tcl}
%   \end{procmethod}
%   
%   \begin{procmethod}{1}
%     The identity element is the empty string.
%     \begin{tcl}
      1 {return ""}
%     \end{tcl}
%   \end{procmethod}
%   
%   \begin{procmethod}{canonise}
%     Every string is a value on canonical form, but an explicit 
%     |canonise| method that just returns the argument is a useful 
%     piece of glue.
%     \begin{tcl}
      canonise {return [lindex $args 0]}
%     \end{tcl}
%   \end{procmethod}
%   
%   \begin{procmethod}{API}
%     It just so happens that the definition of |*| above satifies 
%     not only v\,1.0 but also v\,1.1 of \texttt{semigroup} and 
%     \texttt{monoid}, so we might as well say so. Furthermore every 
%     string has a unique representation, so we can declare support 
%     for the \texttt{onlycanonical} and \texttt{autocanonical} 
%     interfaces as well.
%     \begin{tcl}
      API {
         ::API::static {equality 1.0  autocanonical 1.0 \
           onlycanonical 1.0  semigroup 1.1  monoid 1.1} {*}$args
      }
%     \end{tcl}
%   \end{procmethod}
%   
%   It doesn't hurt to give an informative error message.
%   \begin{tcl}
      default {
         return -code error "Unknown method \"$method\": must be\
           =, *, 1, canonise, or API"
      }
   }
}
%</pkg,stringmonoid>
%   \end{tcl}
% \end{proc}
% 
% 
% \begin{APIspec}{group}{1.0}
%   The \texttt{group} interface is an extension of \texttt{monoid} 
%   with a multplicative inverse operation.
%   
%   \begin{APIdescription}{group}
%     \begin{APImethod}{=}
%       \word{element} \word{element}
%     \end{APImethod}
%       The |=| method satisfies version~1.0 of the \texttt{equality} 
%       interface.
%       
%     \begin{APImethod}{*}
%       \word{element} \word{element}
%     \end{APImethod}
%       The |*| method satisfies version~1.0 of the \texttt{semigroup} 
%       interface.
%       
%     \begin{APImethod}{1}
%     \end{APImethod}
%       The |1| method satisfies version~1.0 of the \texttt{monoid} 
%       interface.
%       
%     \begin{APImethod}{inverse}
%       \word{element}
%     \end{APImethod}
%       The inversion operation |inverse| has the property that
%       \begin{displaysyntax}
%         [$G$ * $a$ [$G$ inverse $a$]]\par
%         [$G$ * [$G$ inverse $a$] $a$]\par
%         [$G$ 1]
%       \end{displaysyntax}
%       are |=|-equal for all elements $a$ of the \meta{group} $G$.
%   \end{APIdescription}
%   All methods are congruent.
% \end{APIspec}
% 
% Additive groups, like multiplicative groups, can be specified as 
% extensions of additive semigroups or monoids, but these aren't all 
% that common, so it is probably easier to do it all in one go.
% 
% \begin{APIspec}{additive group}{2.0}
%   In the additive notation for a group, the binary operation is $+$, 
%   the identity element is $0$, and the inversion operation is 
%   written |neg|.
%   
%   \changes{0.1}{2010/03/25}{Introduced version 2.0 and friends of 
%     \texttt{additive group}. Deprecating 1.0. (LH)}
%   
%   \begin{APIdescription}{group}
%     \begin{APImethod}{=}
%       \word{element} \word{element}
%     \end{APImethod}
%       The |=| method satisfies version~1.0 of the \texttt{equality} 
%       interface.
%       
%     \begin{APImethod}{+}
%       \word{element} \word{element}
%     \end{APImethod}
%       The |+| operation is binary group operation. By 
%       associativity, the two expressions
%       \begin{displaysyntax}
%         [$G$ + [$G$ + $a$ $b$] $c$]\par
%         [$G$ + $a$ [$G$ + $b$ $c$]]
%       \end{displaysyntax}
%       are |=|-equal for all elements $a$, $b$, and $c$ of a 
%       \meta{group} $G$.
%     
%     \begin{APImethod}{0}
%     \end{APImethod}
%       The |0| method returns the identity element of the 
%       group. The relevant axiom says that the three expressions
%       \begin{displaysyntax}
%         [$G$ + [$G$ 0] $a$]\par
%         [$G$ + $a$ [$G$ 0]]\par
%         $a$
%       \end{displaysyntax}
%       are |=|-equal for each element $a$ of a \meta{group} $G$.
%       
%     \begin{APImethod}{neg}
%       \word{element}
%     \end{APImethod}
%       The inversion operation |neg| has the property that
%       \begin{displaysyntax}
%         [$G$ + $a$ [$G$ neg $a$]]\par
%         [$G$ + [$G$ neg $a$] $a$]\par
%         [$G$ 0]
%       \end{displaysyntax}
%       are |=|-equal for each element $a$ of a \meta{group} $G$.
%   \end{APIdescription}
%   All methods are congruent. Note that |additive group| does 
%   \emph{not} require the group to be abelian.
% \end{APIspec}
% 
% Version~1.0 of |additive group| was the same as version~2.0, 
% except that the inversion operation was named |-|. It turns out 
% that it is more practical to reserve |-| as the name for 
% subtraction, as implementations would have to determine at runtime 
% which is wanted if they both have the same name.
%   
% \begin{APIspec}{additive group}{1.0}
%   \begin{APIdescription}{group}
%     \begin{APImethod}{=}
%       \word{element} \word{element}
%     \end{APImethod}
%       The |=| method satisfies version~1.0 of the 
%       \APIref{equality}{1.0} interface.
%       
%     \begin{APImethod}{+}
%       \word{element} \word{element}
%     \end{APImethod}
%       The |+| operation is binary group operation. By 
%       associativity, the two expressions
%       \begin{displaysyntax}
%         [$G$ + [$G$ + $a$ $b$] $c$]\par
%         [$G$ + $a$ [$G$ + $b$ $c$]]
%       \end{displaysyntax}
%       are |=|-equal for all elements $a$, $b$, and $c$ of a 
%       \meta{group} $G$.
%     
%     \begin{APImethod}{0}
%     \end{APImethod}
%       The |0| method returns the identity element of the 
%       group. The relevant axiom says that the three expressions
%       \begin{displaysyntax}
%         [$G$ + [$G$ 0] $a$]\par
%         [$G$ + $a$ [$G$ 0]]\par
%         $a$
%       \end{displaysyntax}
%       are |=|-equal for each element $a$ of a \meta{group} $G$.
%       
%     \begin{APImethod}{-}
%       \word{element}
%     \end{APImethod}
%       The inversion operation |-| has the property that
%       \begin{displaysyntax}
%         [$G$ + $a$ [$G$ - $a$]]\par
%         [$G$ + [$G$ - $a$] $a$]\par
%         [$G$ 0]
%       \end{displaysyntax}
%       are |=|-equal for each element $a$ of a \meta{group} $G$.
%   \end{APIdescription}
%   All methods are congruent. Note that |additive group| does 
%   \emph{not} require the group to be abelian.
% \end{APIspec}
% 
% 
% The above are pretty obvious translations of standard textbook 
% definitions, but there are also some computational subtleties in 
% them that disappear among the mathematical content. Defining the 
% minimalistic structure of a \texttt{magma} serves, if nothing else, 
% the purpose of letting these details be discussed.
% 
% \begin{APIspec}{magma}{1.0}
%   A magma is mathematically a set $M$ together with a binary 
%   operation \(*\colon M \times M \longrightarrow M\).
%   \begin{APIdescription}{magma}
%     \begin{APImethod}{*}
%       \word{element} \word{element}
%     \end{APImethod}
%       The |*| method returns an element of the magma.
%   \end{APIdescription}
% \end{APIspec}
% 
% Does that capture the conventional sense of what it means to be a 
% magma, though? A slightly stronger formalisation is the following.
% 
% \begin{APIspec}{magma}{1.1}
%   A magma is a set $M$ together with the equality relation on $M$ 
%   and a binary operation \(*\colon M \times M \longrightarrow M\).
%   \begin{APIdescription}{magma}
%     \begin{APImethod}{=}
%       \word{element} \word{element}
%     \end{APImethod}
%       The |=| method satisfies version~1.0 of the 
%       \APIref{equality}{1.0} interface.
%       
%     \begin{APImethod}{*}
%       \word{element} \word{element}
%     \end{APImethod}
%       The |*| method returns an element of the magma, and is congruent.
%   \end{APIdescription}
% \end{APIspec}
% 
% What \APIref+{magma}{1.1} claims in addition to the conjunction of 
% \APIref+{magma}{1.0} and \APIref+{equality}{1.0} is that |*| is 
% congruent, which is not a trivial claim\Dash indeed, it is often a 
% claim that is required for a construction to make sense. It is 
% however traditionally not given the status of axiom, since it is 
% trivial for the set-theoretic equality relation.
% 
% \begin{APIspec}{commutative *}{1.0}
%   This interface is simply the statement that the |*| operation, 
%   whatever it computes, is commutative.
%   \begin{APIdescription}{magma}
%     \begin{APImethod}{=}
%       \word{element} \word{element}
%     \end{APImethod}
%       The |=| method satisfies version~1.0 of the 
%       \APIref{equality}{1.0} interface.
%       
%     \begin{APImethod}{*}
%       \word{element} \word{element}
%     \end{APImethod}
%       The |*| method returns an element of the magma. 
%       The |*| method has the property that
%       \begin{displaysyntax}
%         [$M$ * $a$ $b$]\par
%         [$M$ * $b$ $a$]
%       \end{displaysyntax}
%       are |=|-equal for any two elements $a$ and $b$ of a 
%       \meta{magma} $M$.
%   \end{APIdescription}
% \end{APIspec}
% 
% Why not call \APIref{commutative *}{1.0} something like 
% \tclverb*|commutative magma|, though? While that would be more in 
% line with traditional mathematical terminology, it doesn't 
% generalise all that well\Dash commutativity is a property that one 
% might require for quite a number of different operations (besides 
% addition and the main multiplication). By including the operation 
% name in the interface name, one opens up for having multiple such 
% interfaces around. On the other hand, something like dot-product 
% commutativity would be slightly different, as in that case the 
% equality in the axiom is equality in a different (but related) 
% structure.
% 
% 
% 
% \section{User-friendly extensions}
% 
% \subsection{Variadic operation versions}
% 
% While the methods specified by interfaces in the previous section 
% suffice for any computation with elements in a magma, semigroup, 
% monoid, or group, it is often possible to provide more optimised 
% implementation of specific operations. One example is that one 
% $n$-ary product might be quicker to compute than $n-1$ binary 
% products.
% 
% \begin{APIspec}{semigroup}{1.1}
%   Version~1.1 of \texttt{semigroup} extends the |*| operation to be 
%   variadic:
%   \begin{APIdescription}{semigroup}
%     \begin{APImethod}{*}
%       \word{element}\regplus
%     \end{APImethod}
%       The unary form of this method returns the original 
%       element, or more precisely, the two expressions
%       \begin{displaysyntax}
%         [$G$ * $a$]
%         \par
%         $a$
%       \end{displaysyntax}
%       are |=|-equal for every element $a$ of the \meta{semigroup} 
%       $G$. The general identity for the variadic form is that the 
%       two expressions
%       \begin{displaysyntax}
%         [$G$ * [$G$ * \meta{$L_a$}] [$G$ * \meta{$L_b$}]]
%         \par
%         [$G$ * \meta{$L_a$} \meta{$L_b$}]
%       \end{displaysyntax}
%       are |=|-equal for any two nonempty lists $L_a$ and $L_b$ of 
%       elements of the \meta{semigroup} $G$.
%   \end{APIdescription}
%   All methods are congruent.
% \end{APIspec}
% 
% 
% \begin{APIspec}{monoid}{1.1}
%   Version~1.1 of \texttt{monoid} extends the |*| operation to be 
%   variadic. It goes one step further than its \texttt{semigroup} 
%   counterpart by allowing also a nullary multiplication.
%   \begin{APIdescription}{monoid}
%     \begin{APImethod}{*}
%       \word{element}\regstar
%     \end{APImethod}
%       This method satisfies version 1.1 of the |semigroup| interface, 
%       and in addition the two expressions
%       \begin{displaysyntax}
%         [$G$ * [$G$ * \meta{$L_a$}] [$G$ * \meta{$L_b$}]]
%         \par
%         [$G$ * \meta{$L_a$} \meta{$L_b$}]
%       \end{displaysyntax}
%       are |=|-equal for any two lists (not just nonempty lists) 
%       $L_a$ and $L_b$ of elements of the \meta{monoid} $G$.
%       
%       It follows that the nullary form of the |*| method returns 
%       the unit element, because \texttt{[$G$ *]} is by the unit axiom 
%       equal to \texttt{[$G$ * [$G$ 1] [$G$ *]]}, which by the unary 
%       |*| axiom is equal to \texttt{[$G$ * [$G$ * [$G$ 1]] [$G$ *]]}, 
%       which by the variadic axiom is equal to 
%       \texttt{[$G$ * [$G$ 1]]}, which by the unary |*| axiom is equal 
%       to \texttt{[$G$ 1]}.
%   \end{APIdescription}
%   All methods are congruent.
% \end{APIspec}
% 
% 
% \begin{APIspec}{group}{1.1}
%   Version~1.1 of \texttt{group} extends the |*| operation to be 
%   variadic:
%   \begin{APIdescription}{group}
%     \begin{APImethod}{*}
%       \word{element}\regstar
%     \end{APImethod}
%       This method satisfies version 1.1 of the |monoid| interface.
%       
%       \begin{remark}
%         When the |inverse| is available, the unary |*| axiom becomes 
%         redundant.
%       \end{remark}
%   \end{APIdescription}
%   All methods are congruent.
% \end{APIspec}
% 
% 
% \begin{proc}{list_free_monoid_1.1_do}
%   This procedure implements the free \APIref+{monoid}{1.1} over a 
%   structure with \APIref{equality}{1.0}. The overall syntax is
%   \begin{displaysyntax}
%     |::mtmtcl::groups::list_free_monoid_1.1_do| \word{base structure} 
%     \word{API-dict} \word{subcommand} \word{argument}\regstar
%   \end{displaysyntax}
%   and the return value depends on the \word{subcommand}.
%   \changes{0.2}{2010/05/02}{Rewritten as constructor with 
%     do-procedure. (LH)}
%   
%   \begin{tcl}
%<*docstrip.tcl::catalogue>
pkgProvide mtmtcl::groups::list_free_monoid 1.0 {listmonoid common}
%</docstrip.tcl::catalogue>
%<*pkg,listmonoid>
proc ::mtmtcl::groups::list_free_monoid_1.1_do {base API method args} {
   switch -- $method {
%   \end{tcl}
%   \begin{procmethod}{=}
%     Two lists are equal if they are the same length and 
%     corresponding list elements are equal.
%     \begin{tcl}
      = {
         if {[llength [lindex $args 0]] != [llength [lindex $args 1]]}\
         then {return 0}
         foreach x [lindex $args 0] y [lindex $args 1] {
            if {![{*}$base = $x $y]} then {return 0}
         }
         return 1
      }
%     \end{tcl}
%     This completes the \APIref+{equality}{1.0} interface. Doing 
%     version 1.1 would be an unnecessary complication.
%   \end{procmethod}
%   
%   \begin{procmethod}{*}
%     The product of a collection of lists is their concatenation. 
%     \begin{tcl}
      * {
         return [concat {*}$args]
      }
%     \end{tcl}
%     That this is so easy to implement is the reason why this 
%     implementation does not stop at \APIref+{monoid}{1.0}, but 
%     instead goes on to version~1.0.
%   \end{procmethod}
%   
%   \begin{procmethod}{1}
%     The identity element is the empty list.
%     \begin{tcl}
      1 {return [list]}
%     \end{tcl}
%     This completes the \APIref+{monoid}{1.1} interface. 
%   \end{procmethod}
%   
%   \begin{procmethod}{canonise}
%     Canonisation means canonise each list element and rebuild the 
%     list with canonical representation.
%     \begin{tcl}
      canonise {
         set res [list]
         foreach item [lindex $args 0] {
            lappend res [{*}$base canonise $item]
         }
         return $res
      }
%     \end{tcl}
%     This is supported if the base structure supports it.
%   \end{procmethod}
%   
%   \begin{procmethod}{named}
%     Named elements of the base structure are accepted as names 
%     for the length $1$ list containing that element.
%     \begin{tcl}
      named {return [list [{*}$base named [lindex $args 0]]]}
%     \end{tcl}
%   \end{procmethod}
%   
%   \begin{procmethod}{* decomposition}
%     There is a trivial element decomposition which puts the power 
%     $1$ on everything.
%     \begin{tcl}
      {* decomposition} {
%<*trivial>
         set res {}
         foreach item [lindex $args 0] {
            lappend res $item 1
         }
%</trivial>
%     \end{tcl}
%     But it is nicer to recognise sequences of identical elements 
%     and express those as powers; \APIref{equality}{1.0} in the 
%     base structure is sufficient for this.
%     \begin{tcl}
%<*!trivial>
         if {[llength [lindex $args 0]] > 1} then {
            set res [list [lindex $args 0 0]]
            set count 1
            foreach item [lrange [lindex $args 0] 1 end] {
               if {[{*}$base = [lindex $res end] $item]} then {
                  incr count
               } else {
                  lappend res $count $item
                  set count 1
               }
            }
            lappend res $count
         } elseif {[llength [lindex $args 0]] == 1} then {
            set res [list [lindex $args 0 0] 1]
         } else {
            set res {}
         }
%</!trivial>
         return $res
      }
%     \end{tcl}
%   \end{procmethod}
%   
%   \begin{procmethod}{generator}
%     The |generator| method returns a list of length one whose only 
%     element is the argument.
%     \begin{tcl}
      generator {return [lrange $args 0 0]}
%     \end{tcl}
%   \end{procmethod}
%   
%   \begin{procmethod}{generators}
%     The base structure is made available via the |generators| 
%     method.
%     \changes{0.2}{2010/05/02}{Renamed from \texttt{namestructure}. 
%       (LH)}
%     \begin{tcl}
      generators {uplevel 1 $base $args}
%     \end{tcl}
%   \end{procmethod}
%   
%   \begin{procmethod}{export}
%     Exporting is pretty straightforward: just form the product of 
%     the exports of each element separately. This may serve as an 
%     example of how to handle the paths.
%     \begin{tcl}
      export {
         lassign $args L attr
         set sattr [dict replace $attr  cd arith1  name times]
         dict lappend sattr mtmtcl:path *
         set childL [list [list OMS $sattr {}]]
         set battr $attr
         dict lappend battr mtmtcl:path generators
         foreach factor $L {
            lappend childL [{*}$base export $factor $battr]
         }
         return [list OMA $attr $childL]
      }
%     \end{tcl}
%     In a free monoid with power operation, it might be more 
%     appropriate to use powers as much as possible when expressing 
%     the element.
%   \end{procmethod}
%   
%   \begin{procmethod}{API}
%     Since the base structure is cached in a parameter, the 
%     implementation of this is trivial.
%     \begin{tcl}
      API {::API::static $API {*}$args}
%     \end{tcl}
%   \end{procmethod}
%   
%   It doesn't hurt to give an informative error message.
%   \begin{tcl}
      default {
         return -code error "Unknown method \"$method\""
      }
   }
}
%   \end{tcl}
% \end{proc}
% 
% \begin{proc}{list_free_monoid_1.1}
%   The constructor for the list free monoid has the call syntax
%   \begin{displaysyntax}
%     |mtmtcl::groups::list_free_monoid_1.1| \word{base structure}
%   \end{displaysyntax}
%   i.e., it takes the underlying base structure as only argument and 
%   returns the corresponding free monoid.
%   
%   \begin{tcl}
proc ::mtmtcl::groups::list_free_monoid_1.1 {base} {
   set D [dict create]
   if {[{*}$base API equality 1.0]} then {
      dict lappend D equality 1.0 
      dict lappend D semigroup 1.1 
      dict lappend D monoid 1.1
%   \end{tcl}
%   The claim to support \APIref{generated semigroup}{1.0} is 
%   commented out until the actual specification has been done.
%   \begin{tcl}
      # dict lappend D "generated semigroup" 1.0
   }
   if {[{*}$base API canonise 1.0]} then {
      if {[{*}$base API canonise 1.1]} then {
         dict set D canonise 1.1
      } else {
         dict set D canonise 1.0 
      }
   }
   if {[{*}$base API "named element" 1.0]} then {
      dict lappend D "named element" 1.0
   }
   if {[{*}$base API export 2.0]} then {
      dict set D export 2.0 
   }
   return [list [namespace which list_free_monoid_1.1_do] $base D]
}
%</pkg,listmonoid>
%     \end{tcl}
% \end{proc}
% 
% 
% \subsection{Powers}
% 
% A power operation makes sense for two reasons. First, it is 
% customary to express things using powers whenever possible. Second, 
% there might be quicker ways of computing powers than just what you 
% get from repeated multiplication (even when repeated multiplication 
% includes squaring in $O(\log_2 n)$ multiplications rather the $n-1$ 
% required by the trivial algorithm of multiplying by the base). 
% Examples include:
% \begin{enumerate}
%   \item
%     In a power product monoid, taking a power just means taking a 
%     multiple of the exponents.
%   \item
%     Large powers of a matrix can be mostly reduced to large powers 
%     of scalars, by diagonalising the matrix (or more generally, 
%     transformation to Jordan normal form). Although for practical 
%     computations, it often works out the other way around.
%   \item
%     Employing knowledge about periods to limit the powers that need 
%     to be computed. A permutation can be factorised into 
%     cycles, and the order of each cycle is equal to its length.
% \end{enumerate}
% In such cases, an implementation of a power method constitutes a 
% useful addition to a group.
% 
% \begin{APIspec}{semigroup}{1.2}
%   Version 1.2 of \texttt{semigroup} improves on v\,1.1 by adding 
%   a power method.
%   \begin{APIdescription}{semigroup}
%     \begin{APImethod}{^}
%       \word{element} \word{integer}
%     \end{APImethod}
%       The \word{integer} must be positive. 
%       The value of \texttt{[\meta{group} \^{} $a$ $n$]} is $a^n$.
%   \end{APIdescription}
%   All methods are congruent.
% \end{APIspec}
% 
% \begin{APIspec}{monoid}{1.2}
%   Version 1.2 of \texttt{monoid} improves on v\,1.1 by adding 
%   a power method.
%   \begin{APIdescription}{monoid}
%     \begin{APImethod}{^}
%       \word{element} \word{integer}
%     \end{APImethod}
%       The \word{integer} must be nonnegative. 
%       The value of \texttt{[\meta{group} \^{} $a$ $n$]} is $a^n$.
%   \end{APIdescription}
%   All methods are congruent.
% \end{APIspec}
% 
% \begin{APIspec}{group}{1.2}
%   Version 1.2 of \texttt{group} improves on v\,1.1 by adding a power 
%   method.
%   \begin{APIdescription}{group}
%     \begin{APImethod}{^}
%       \word{element} \word{integer}
%     \end{APImethod}
%       The value of \texttt{[\meta{group} \^{} $a$ $n$]} is $a^n$.
%   \end{APIdescription}
%   All methods are congruent.
% \end{APIspec}
% 
% A \APIref+{group}{1.2} satisfies \APIref+{monoid}{1.2} and 
% \APIref+{semigroup}{1.2}, but a \APIref+{group}{1.1} that satisfies 
% \APIref+{monoid}{1.2} is not necessarily a \APIref+{group}{1.2}, 
% since the latter makes claims about e.g.~\texttt{[\meta{group} \^{} $a$ 
% -1]} whereas the former does not\Dash there an exponent of $-1$ 
% could cause the power operation to error out as not implemented.
% 
% ---
% 
% \begin{APIspec}{group}{1.3}
%   Version 1.3 of \texttt{group} improves on v\,1.2 by adding a power 
%   product method |*^|, analogous to a linear combination.
%   \begin{APIdescription}{group}
%     \begin{APImethod}{*^}
%       \begin{regblock}[\regstar] \word{element} \word{integer} 
%       \end{regblock}
%     \end{APImethod}
%       The value of
%       \begin{displaysyntax}
%         [\meta{group} *\^{} $a_1$ $n_1$ $\dots$ $a_k$ $n_k$]
%       \end{displaysyntax}
%       is $a_1^{n_1} \dotsb a_k^{n_k}$, i.e., on one hand
%       \begin{displaysyntax}
%         [$G$ |*^| $a$ $n$]\par
%         [$G$ |^| $a$ $n$]
%       \end{displaysyntax}
%       are |=|-equal for every element $a$ and integer $n$, and on the 
%       other,
%       \begin{displaysyntax}
%         [$G$ |*^| \splode$L_a$ \splode$L_b$]\par
%         [$G$ * [$G$ |*^| \splode$L_a$] [$G$ |*^| \splode$L_b$]]
%       \end{displaysyntax}
%       are |=|-equal for all lists $L_a$ and $L_b$ with the structure
%       \begin{quote}
%         \begin{regblock}[\regstar] \word{element} \word{integer} 
%         \end{regblock}
%       \end{quote}
%   \end{APIdescription}
%   All methods are congruent.
% \end{APIspec}
% 
% 
% \begin{proc}{power_product_monoid_1.3}
%   The |power_product_monoid_1.3| procedure implements 
%   multiplicative free abelian monoids, denoted as power products. 
%   The \meta{monoid} command prefix is
%   \begin{displaysyntax}
%     |power_product_monoid| \word{generator set}
%   \end{displaysyntax}
%   where the \word{generator set} is the command prefix of a 
%   \APIref+{finite set}{1.1}.
%   
%   Elements are lists of exponents, where the $i$th exponent 
%   corresponds to the $i$th generator. The exponents are native 
%   non-negative integers.
%   
%   \begin{tcl}
%<*pkg>
proc ::mtmtcl::groups::power_product_monoid_1.3 {base method args} {
   switch -- $method {
%   \end{tcl}
%   \begin{procmethod}{=}
%     Since all elements are lists of the same length, two lists 
%     are equal if corresponding list elements are equal.
%     \begin{tcl}
      = {
         foreach x [lindex $args 0] y [lindex $args 1] {
            if {$x != $y]} then {return 0}
         }
         return 1
      }
%     \end{tcl}
%   \end{procmethod}
%   
%   \begin{procmethod}{1}
%     The identity element is a list of zeroes, but one must look at 
%     the set of generators to figure out how many.
%     \begin{tcl}
      1 {
         set res {}
         foreach x [{*}$base elements] {lappend res 0}
         return $res
      }
%     \end{tcl}
%   \end{procmethod}
%   
%   \begin{procmethod}{*}
%     The product of a collection of lists is their pointwise sum.
%     \begin{tcl}
      * {
         if {![llength $args]} then {
            return [power_product_monoid_1.3 $base 1]
         }
         set res [lindex $args 0]
         foreach factor [lrange $args 1 end] {
            set nres {}
            foreach x $res y $factor {lappend nres [expr {$x+$y}]}
            set res $nres
         }
         return $res
      }
%     \end{tcl}
%   \end{procmethod}
%   
%   \begin{procmethod}{^}
%     The power operation is similarly a pointwise multiplication by 
%     scalar.
%     \begin{tcl}
      ^ {
         set res {}
         foreach item [lindex $args 0] {
            lappend res [expr {$item * [lindex $args 1]}]
         }
         return $res
      }
%     \end{tcl}
%   \end{procmethod}
%   
%   \begin{procmethod}{*^}
%     The product-of-powers operation combines pointwise sum and 
%     multiplication by scalar.
%     \begin{tcl}
      * {
         if {![llength $args]} then {
            return [power_product_monoid_1.3 $base 1]
         }
         set res {}
         foreach item [lindex $args 0] {
            lappend res [expr {$item * [lindex $args 1]}]
         }
         foreach {factor exp} [lrange $args 2 end] {
            set nres {}
            foreach x $res y $factor {lappend nres [expr {$x+$y*$exp}]}
            set res $nres
         }
         return $res
      }
%     \end{tcl}
%   \end{procmethod}
%   
%   \begin{procmethod}{canonise}
%     Canonisation means canonise each list element and rebuild the 
%     list with canonical representation.
%     \begin{tcl}
      canonise {
         set res [list]
         foreach item [lindex $args 0] {
            lappend res [format %d $item]
         }
         return $res
      }
%     \end{tcl}
%   \end{procmethod}
%   
%   \begin{procmethod}{named}
%     Elements of the base structure are accepted as names for 
%     element with exponent $1$ for that generator and $0$ for all 
%     others.
%     \begin{tcl}
      named {
         set res {}
         foreach name [{*}$base elements] {
            lappend res [::tcl::mathfunc::bool [
               {*}$base = $name [lindex $args 0]
            ]]
         }
         return $res
      }
%     \end{tcl}
%     It wouldn't be correct to merely |lsearch| for the wanted 
%     argument, as the set of generators is not required to be 
%     |onlycanonical|.
%   \end{procmethod}
%   
%   \begin{procmethod}{namestructure}
%     The base structure is made available via the |namestructure| 
%     method.
%     \begin{tcl}
      namestructure {uplevel 1 $base $args}
%     \end{tcl}
%   \end{procmethod}
%   
%   \begin{procmethod}{* decomposition}
%     The element decomposition is straightforward.
%     \begin{tcl}
      {* decomposition} {
         set res {}
         foreach name [{*}$base elements] exp [lindex $args 0] {
            lappend res $name $exp
         }
         return $res
      }
%     \end{tcl}
%   \end{procmethod}
%   
%   \begin{procmethod}{export}
%     Not surprisingly, power products are exported as products of 
%     powers. The format is somewhat prolix in that it has a power 
%     for \emph{every} generator (even those with exponent $0$ or 
%     $1$), but it is easier to get rid of these than to reinsert 
%     them.
%     \begin{tcl}
      export {
         lassign $args L attr
         set pattr [dict replace $attr  cd arith1  name power]
         set mattr [dict replace $attr  cd arith1  name times]
         set battr $attr
         dict lappend pattr mtmtcl:path ^
         dict lappend mattr mtmtcl:path *
         dict lappend battr mtmtcl:path namestructure
         set pow [list OMS $pattr {}]
         set childL [list [list OMS $mattr {}]]
         foreach name [{*}$base elements] exponent $L {
            lappend childL [list OMA $attr [list $pow [
               {*}$base export $name $battr
            ] [
               list integer [dict create value $exponent] {}
            ]]]
         }
         return [list OMA $attr $childL]
      }
%     \end{tcl}
%   \end{procmethod}
%   
%   \begin{procmethod}{/}
%     The quotient of two power products exists iff each exponent in 
%     the numerator is $\geqslant$ the corresponding exponent in the 
%     denominator.
%     \begin{tcl}
      / {
         lassign $args a b
         set res {}
         foreach k $a l $b {
            lappend res [expr {$k-$l}]
            if {[lindex $res end] < 0} then {
               return -code error -errorcode {API division nosolution}\
                 "Would get negative exponent"
            }
         }
         return $res
      }
%     \end{tcl}
%   \end{procmethod}
%   
%   \begin{procmethod}{API}
%     The base structure API is only queried when the |API| method is 
%     called. The adapter denounces support for everything unless the 
%     base structure at least supports \APIref+{finite set}{1.1}.
%     \begin{tcl}
      API {
         set D [dict create]
         if {[{*}$base API "finite set" 1.1]} then {
            dict lappend D equality 1.0 
            dict lappend D semigroup 1.3 
            dict lappend D monoid 1.3
            dict lappend D division 1.0
            dict lappend D "named element" 1.0
            dict lappend D "* decomposition" 1.0
         }
         if {[{*}$base API canonise 1.0]} then {
            dict set D canonise 1.0 
         }
         if {[{*}$base API export 2.0]} then {
            dict set D export 2.0 
         }
         ::API::static $D {*}$args
      }
%     \end{tcl}
%   \end{procmethod}
%   
%   It doesn't hurt to give an informative error message.
%   \begin{tcl}
      default {
         return -code error "Unknown method \"$method\""
      }
   }
}
%</pkg>
%   \end{tcl}
% \end{proc}
% 
% 
% \setnamespace{mtmtcl::groups::util}
% 
% 
% \begin{proc}{balanced_nassoc}
%   This procedure implements a variadic $n$-associative product (for 
%   \(n \geqslant 1\)) on top of a binary product. The call syntax is
%   \begin{displaysyntax}
%     |::mtmtcl::groups::util::balanced_nassoc| \word{binary-prefix} 
%     \word{factor}\regplus
%   \end{displaysyntax}
%   where the \word{binary-prefix} is a command prefix with the syntax
%   \begin{displaysyntax}
%     \meta{binary-prefix} \word{factor} \word{factor}
%   \end{displaysyntax}
%   that returns the ``product'' of those two factors. The operation 
%   implemented by this prefix should be associative.
%   
%   The `balanced' part of the name has to do with the fact that the 
%   tree of intermediate binary products being computed is ensured to 
%   be balanced, i.e., the distances from any \word{factor} leaf in 
%   this tree to the root may differ by at most one. The way the 
%   algorithm works is that the list of factors is processed in a 
%   number of rounds, and in each round factors are paired up and 
%   multiplied using the binary operation, meaning the number of 
%   things still left to multiply is halved for each round. If at 
%   some round the number of factors is odd, then an intermediate 
%   round multiplying just two of them is performed, to make the 
%   number of factors in the main round even. The choice of two 
%   factors for the intermediate round is such that no descendant of 
%   such an intermediate round product will appear in another 
%   intermediate round product, so the tree overall ends up balanced.
%   
%   \begin{tcl}
%<*util>
proc ::mtmtcl::groups::util::balanced_nassoc {bincmd args} {
   while {[llength $args] > 1} {
      if {[llength $args] & 1} then {
         set args [lreplace $args 1 2 [
            {*}$bincmd {*}[lrange $args 1 2]
         ]]
      }
      set args [lmap {l r} $args {
         {*}$bincmd $l $r
      }]
   }
   return [lindex $args 0]
}
%</util>
%   \end{tcl}
%   
%   What is then the importance of balancing this tree? It tends to 
%   reduce the sizes of the factors passed to the \word{binary-prefix}, 
%   which is often a major factor in the overall complexity, and 
%   sometimes also in precision. The details depend on the complexity 
%   of the \meta{binary-prefix}, but the improvement seems more often 
%   to be in the constant factor of the complexity than in the hard 
%   asymptotics; still, it can be useful.
%   
%   Note also that regardless of how the products are arranged, this 
%   procedure still makes $n-1$ calls to the \word{binary-prefix}. 
%   Powers are better computed using |squaring_power|, which takes 
%   advantage of some intermediate results being equal when computing 
%   a pure power.
% \end{proc}
% 
% \begin{proc}{variadic_product}
%   The |variadic_product| procedure implements a variadic product on 
%   top of (mostly) a binary product. The call syntax is
%   \begin{displaysyntax}
%     |variadic_product| \word{binary command} \word{use unary} 
%     \word{unary command} \word{nullary command}
%     \word{factor}\regstar
%   \end{displaysyntax}
%   where the \word{binary command}, \word{unary command}, and 
%   \word{nullary command} are command prefixes taking $2$, $1$, and 
%   $0$ arguments respectively and which compute the product of that 
%   many arguments. The \word{unary command} is typically empty or a 
%   |canonise| command.
%   
%   If the \word{nullary command} is empty then the $0$ factor form 
%   is not allowed. The \word{use unary} is a boolean; if it is false 
%   then the $1$ factor form simply returns that factor. If it is 
%   true and \word{unary command} is nonempty then that is used. If 
%   \word{use unary} is true and \word{unary command} is empty but 
%   \word{nullary command} is nonempty then the result is computed 
%   using \word{binary command} and \word{nullary command}. Otherwise 
%   the $1$ factor form is not allowed either.
%   \begin{tcl}
%<*pkg,util>
proc ::mtmtcl::groups::util::variadic_product {
   bincmd use1 uncmd nullcmd args
} {
   if {[llength $args] == 2} then {
      return [eval $bincmd $args]
   } elseif {[llength $args] > 2} then {
      set res [lindex $args 0]
      foreach factor [lrange $args 1 end] {
         set res [eval $bincmd [list $res $factor]]
      }
      return $res
   } elseif {[llength $args] == 0} then {
      if {[llength $nullcmd]} then {
         return [eval $nullcmd]
      } else {
         return -code error "Nullary form not supported"
      }
   } else {
      if {!$use1} then {
         return [lindex $args 0]
      } elseif {[llength $uncmd]} then {
         return [eval $uncmd $args]
      } elseif {[llength $nullcmd]} then {
         return [eval $bincmd [list [eval $nullcmd]] $args]
      } else {
         return -code error "Unary form not supported"
      }
   }
}
%   \end{tcl}
% \end{proc}
% 
% 
% \begin{proc}{squaring_power}
%   The |squaring_power| procedure implements integer powers on top of 
%   (mostly) a binary product, by taking squares. The call syntax is
%   \begin{displaysyntax}
%     |squaring_power| \word{binary command} \word{use unary} 
%     \word{unary command} \word{identity command}
%     \word{inverse command} \word{base} \word{exponent}
%   \end{displaysyntax}
%   where \word{exponent} is an integer and \word{base} is something 
%   that can be multiplied. The \word{binary command}, \word{inverse 
%   command}, \word{unary command}, and \word{nullary command} are 
%   command prefixes taking $2$, $1$, $1$, and $0$ arguments 
%   respectively and which compute the product of two factors, the 
%   inverse of one factor, the product of one factor, or the product 
%   of no factors. If any one of these is an empty string, then that 
%   operation is considered to be unavailable; the procedure will try 
%   to work around the situation, but must in some cases fail.
%   
%   What complicates the syntax is that it is desirable to preserve 
%   automatic canonisation of elements although that will not always 
%   come automatically, so there are a couple of edge cases for low 
%   exponents and structures without unit or inverse. The 
%   implementation tries to do \emph{something} in these cases; the 
%   rationale for this is that these are probably not the hard cases 
%   anyway.
%   
%   If the \word{nullary command} is empty then the $0$ factor form 
%   is not allowed. The \word{use unary} is a boolean; if it is false 
%   then the $1$ factor form simply returns that factor. If it is 
%   true and \word{unary command} is nonempty then that is used. If 
%   \word{use unary} is true and \word{unary command} is empty but 
%   \word{nullary command} is nonempty then the result is computed 
%   using \word{binary command} and \word{nullary command}. Otherwise 
%   the $1$ factor form is not allowed either.
%   \begin{tcl}
proc ::mtmtcl::groups::util::squaring_power {
   bincmd use1 uncmd idcmd invcmd base exp
} {
   if {$exp < 0} then {
%   \end{tcl}
%   Negative exponents are straightforward: an inverse is needed. 
%   After inverting \word{base}, the exponent can be negated.
%   \begin{tcl}
      if {[llength $invcmd]} then {
         set base [{*}$invcmd $base]
         if {$exp == -1} then {return $base}
         set exp [expr {-$exp}]
      } else {
         return -code error "Inverses not supported"
      }
   } elseif {$exp == 0} then {
%   \end{tcl}
%   Zero exponents have two possible implementations: use explicit 
%   identity element (preferred), or try the expression $b b^{-1}$.
%   \begin{tcl}
      if {[llength $idcmd]} then {
         return [{*}$idcmd]
      } elseif {[llength $invcmd]} then {
         return [{*}$bincmd $base [{*}$invcmd $base]]
      } else {
         return -code error "0th power not supported"
      }
   }
%   \end{tcl}
%   In the case of \word{exponent} $1$, things get even messier. The 
%   easiest implementation is that we can just return the 
%   \word{base}, so there is a separate argument \word{use unary} to 
%   signal when this is not OK.
%   \begin{tcl}
   if {$exp == 1} then {
      if {!$use1} then {
         return $base
      } elseif {[llength $uncmd]} then {
         return [{*}$uncmd $base]
      } elseif {[llength $idcmd] || [llength $invcmd]} then {
         if {[llength $idcmd]} then {
            set id [{*}$idcmd]
         } else {
            set id [{*}$bincmd $base [{*}$invcmd $base]]
         }
         return [{*}$bincmd $base $id]
      } else {
         return -code error "1st power not supported"
      }
   }
%   \end{tcl}
%   The actual algorithm computes $b^e$ as $\prod_{k \in E} b^{2^k}$ 
%   where \(E \subset \mathbb{N}\) is such that \(e = 
%   \sum_{k \in E} 2^k\), i.e., $E$ is the set of positions of $1$s 
%   in the base $2$ representation of the integer $e$.
%   \begin{tcl}
   set power $base
   for {} {!($exp & 1)} {set exp [expr {$exp/2}]} {
      set power [{*}$bincmd $power $power]
   }
   set res $power
   while {$exp>=2} {
      set power [{*}$bincmd $power $power]
      set exp [expr {$exp/2}]
      if {$exp & 1} then {
         set res [{*}$bincmd $res $power]
      }
   }
   return $res
}
%   \end{tcl}
%   For an $n$-bit exponent (one at least $2^n$ but less than 
%   $2^{n+1}$), this algorithm does between $n$ and $2n$ calls to the 
%   \word{binary command}, and whereas $n$ is an unescapable lower 
%   bound, it would be possible to improve on the upper bound, 
%   although only to improve the constant factor: one may 
%   asymptotically attain $(1+\nobreak\varepsilon)n$ for any 
%   \(\varepsilon>0\). However, the trick to do that is to work with 
%   groups of \(k > \frac{1}{\varepsilon}\) bits, view such groups as 
%   ``base $2^k$ digits'', and first spending another $2^k-2$ 
%   multiplications on computing all single digit powers; in other 
%   words this only applies when $2^k$ is $o(n)$. This makes sense 
%   for certain number-theoretical applications, but not so much in 
%   symbolic computation, so it is not really something to worry 
%   about for the general implementation.
% \end{proc}
% 
% \begin{proc}{power_product}
%   This command has the syntax
%   \begin{displaysyntax}
%     |power_product| \word{product-command} \word{power-command} 
%     \begin{regblock}[\regstar] \word{base} \word{exponent} 
%     \end{regblock}
%   \end{displaysyntax}
%   It uses the \word{power-command}\Ldash which has the syntax
%   \begin{quote}
%     \word{power-command} \word{base} \word{exponent}
%   \end{quote}
%   \Dash to compute $a^n$ for each \word{base} $a$ and \word{exponent} 
%   $n$, and then the \word{product-command}\Ldash which has the 
%   syntax
%   \begin{quote}
%     \word{product-command} \word{factor}\regstar
%   \end{quote}
%   \Dash to multiply these powers. The return value is that product.
%   \begin{tcl}
proc ::mtmtcl::groups::util::power_product {prodcmd powcmd args} {
   set call [list $prodcmd]
   foreach {base exponent} $args {
      lappend call [eval $powcmd [list $base $exponent]]
   }
   return [eval $call]
}
%</pkg,util>
%   \end{tcl}
% \end{proc}
% 
% 
% \setnamespace{mtmtcl::groups}
% 
% \begin{proc}{group_1.3_upgrade}
%   The |group_1.3_upgrade| procedure is an adaptor which creates 
%   a \texttt{group} v\,1.3 from a \texttt{group} v\,1.0 or later. The 
%   call syntax is
%   \begin{displaysyntax}
%     |group_1.3_upgrade| \word{name} \meta{prefix}
%   \end{displaysyntax}
%   where \word{name} is the name of the new command to create and 
%   \meta{prefix} is the command prefix of the group inside.
%   
%   The interfaces the new structure may support in addition to 
%   |group|~1.3 are |equality|~1.0, |canonise|~1.0 (if \meta{prefix} 
%   does), and |autocanonical|~1.0 (if \meta{prefix} does).
%   
%   The implementation uses the |APIutil::ensemble| command.
%   \begin{tcl}
%<*pkg&deadapproach>
proc ::mtmtcl::groups::group_1.3_upgrade {name args} {
   if {![eval $args [list API group 1.0]]} then {
      error "Base structure is not a: group 1.0"
   }
   ::APIutil::adaptation $name $args uplevel 1 same {
      equality 1.0 {=}
      canonise 1.0 {canonise}
      autocanonical 1.0 {}
   } push {
      1 {# {Non-autocanonical power}
         #nswc squaring_power #{ #*0 * #} 0 {}
         #{ #*0 identity #} #{ #*0 inverse #}
      }
   } method {
      * {group 1.1} {#*0 *}
      * {autocanonical 1.0 canonise 1.0} {
         #nswc variadic_product #{ #*0 * #} 1 #{ #*0 canonise #}
         #{ #*0 identity #}
      }
      * {autocanonical 1.0} {
         #nswc variadic_product #{ #*0 * #} 1 {} #{ #*0 identity #}
      }
      * {} {
         #nswc variadic_product #{ #*0 * #} 0 {} #{ #*0 identity #}
      }
      identity {} {#*0 identity}
      inverse {} {#*0 inverse}
      ^ {group 1.2} {#*0 ^}
      ^ {autocanonical 1.0 canonise 1.0} {
         #nswc squaring_power #{ #*0 * #} 1 #{ #*0 canonise #}
         #{ #*0 identity #} #{ #*0 inverse #}
      }
      ^ {autocanonical 1.0} {
         #nswc squaring_power #{ #*0 * #} 1 {}
         #{ #*0 identity #} #{ #*0 inverse #}
      }
      ^ {} {#*1}
   } pushmethod {
      2 *
   } method {
      *^ {group 1.3} {#*0 *^}
      *^ {group 1.2} {
         #nswc power_product #{ #*0 * #} #{ #*0 ^ #}
      }
      *^ {group 1.1} {
         #nswc power_product #{ #*0 * #} #1
      }
      *^ {} {
         #nswc power_product #2 #1
      }
   } interface {
      group 1.3 {}
      monoid 1.3 {}
      semigroup 1.3 {}
   }
}
%</pkg&deadapproach>
%   \end{tcl}
% \end{proc}
% 
% 
% 
% \begin{APIspec}{additive group}{2.0.1}
%   Version 2.0.1 of \texttt{additive group} introduces |-| for 
%   subtraction.
%   \begin{APIdescription}{group}
%     \begin{APImethod}{-}
%       \word{element} \word{element}
%     \end{APImethod}
%       The defining property of |-| is that the two expressions
%       \begin{displaysyntax}
%         [$G$ - $a$ $b$]\par
%         [$G$ + $a$ [$G$ neg $b$]]
%       \end{displaysyntax}
%       are |=|-equal for all elements $a$ and $b$.
%   \end{APIdescription}
%   All methods are congruent. 
% \end{APIspec}
% 
% \begin{APIspec}{additive group}{2.1}
%   Version 2.1 of \texttt{additive group} extends the syntax of 
%   addition to be variadic and introduces |iszero| for testing 
%   whether something is $0$.
%   \begin{APIdescription}{group}
%     \begin{APImethod}{+}
%       \word{element}\regstar
%     \end{APImethod}
%       The general identity for the variadic form is that the two 
%       expressions
%       \begin{displaysyntax}
%         [$G$ + [$G$ + \meta{$L_a$}] [$G$ + \meta{$L_b$}]]
%         \par
%         [$G$ + \meta{$L_a$} \meta{$L_b$}]
%       \end{displaysyntax}
%       are |=|-equal for any two lists of elements $L_a$ and $L_b$. 
%       In particular this implies that \texttt{[$G$ +]} returns 
%       the identity element and that $a$ is |=|-equal to 
%       \texttt{[$G$ + $a$]} for every element $a$.
%       
%     \begin{APImethod}{iszero}
%       \word{element}
%     \end{APImethod}
%       This method is a shorthand for testing equality to zero, i.e., 
%       the two expressions
%       \begin{displaysyntax}
%         [$G$ iszero $a$]\par
%         [$G$ = [$G$ 0] $a$]
%       \end{displaysyntax}
%       are equal as booleans for all elements $a$ of the 
%       \meta{group}~$G$.
%   \end{APIdescription}
%   All methods are congruent. 
% \end{APIspec}
% 
% \begin{APIspec}{additive group}{2.2}
%   Version 2.2 of \texttt{additive group} parallels version 1.2 of 
%   \texttt{group} by adding an integer multiple method.
%   \begin{APIdescription}{group}
%     \begin{APImethod}{integer.}
%       \word{integer} \word{element} 
%     \end{APImethod}
%       The value of \texttt{[\meta{group} integer.\@ $n$ $a$]} is 
%       $\sum_{i=1}^n a$.
%       
%       The notation is chosen to on one hand make it easy to turn an 
%       additive group into a $\mathbb{Z}$-module, but on the other 
%       hand stay distinct so that it does not conflict with the scalar 
%       multiple of modules of other rings.
%   \end{APIdescription}
%   All methods are congruent.
% \end{APIspec}
% 
% \begin{APIspec}{additive group}{2.3}
%   Version 2.3 of \texttt{additive group} improves on v\,2.2 by adding 
%   a linear combination extension of the integer multiple method.
%   \begin{APIdescription}{group}
%     \begin{APImethod}{+integer.}
%       \begin{regblock}[\regstar] \word{integer} \word{element} 
%       \end{regblock}
%     \end{APImethod}
%       The value of
%       \begin{displaysyntax}
%         [\meta{group} +integer. $n_1$ $a_1$ $\dots$ $n_k$ $a_k$]
%       \end{displaysyntax}
%       is $\sum_{i=1}^k n_1 a_1$, i.e., on one hand
%       \begin{displaysyntax}
%         [$G$ +integer. $n$ $a$]\par
%         [$G$ integer. $n$ $a$]
%       \end{displaysyntax}
%       are |=|-equal for every element $a$ and integer $n$, and on the 
%       other,
%       \begin{displaysyntax}
%         [$G$ +integer. \meta{$L_a$} \meta{$L_b$}]\par
%         [$G$ + [$G$ +integer. \meta{$L_a$}] 
%           [$G$ +integer. \meta{$L_b$}]]
%       \end{displaysyntax}
%       for all lists $L_a$ and $L_b$ with the structure
%       \begin{quote}
%         \begin{regblock}[\regstar] \word{integer} \word{element} 
%         \end{regblock}
%       \end{quote}
%   \end{APIdescription}
%   All methods are congruent.
% \end{APIspec}
% 
% There is also a parallel list of \APIref{additive group}{1.0} 
% versions~1.x which build upon 1.0.
% 
% \begin{APIspec}{additive group}{1.1}
%   Version 1.1 of \texttt{additive group} extends the syntaxes of 
%   addition to be variadic and the syntax of |-| to provide 
%   subtraction as well as negation.
%   \begin{APIdescription}{group}
%     \begin{APImethod}{+}
%       \word{element}\regstar
%     \end{APImethod}
%       The general identity for the variadic form is that the two 
%       expressions
%       \begin{displaysyntax}
%         [$G$ + [$G$ + \meta{$L_a$}] [$G$ + \meta{$L_b$}]]
%         \par
%         [$G$ + \meta{$L_a$} \meta{$L_b$}]
%       \end{displaysyntax}
%       are |=|-equal for any two lists of elements $L_a$ and $L_b$. 
%       In particular this implies that \texttt{[$G$ +]} returns 
%       the identity element and that $a$ is |=|-equal to 
%       \texttt{[$G$ + $a$]} for every element $a$.
%       
%     \begin{APImethod}{-}
%       \word{element} \word{element}
%     \end{APImethod}
%       The binary form of |-| is has as defining property that the two 
%       expressions.
%       \begin{displaysyntax}
%         [$G$ - $a$ $b$]\par
%         [$G$ + $a$ [$G$ - $b$]]
%       \end{displaysyntax}
%       are |=|-equal for all elements $a$ and $b$.
%       
%     \begin{APImethod}{iszero}
%       \word{element}
%     \end{APImethod}
%       This method is a shorthand for testing equality to zero, i.e., 
%       the two expressions
%       \begin{displaysyntax}
%         [$G$ iszero $a$]\par
%         [$G$ = [$G$ 0] $a$]
%       \end{displaysyntax}
%       are equal as booleans for all elements $a$ of the 
%       \meta{group}~$G$.
%   \end{APIdescription}
%   All methods are congruent. 
% \end{APIspec}
% 
% \begin{APIspec}{additive group}{1.2}
%   Version 1.2 of \texttt{additive group} parallels version 1.2 of 
%   \texttt{group} by adding an integer multiple method.
%   \begin{APIdescription}{group}
%     \begin{APImethod}{integer.}
%       \word{integer} \word{element} 
%     \end{APImethod}
%       The value of \texttt{[\meta{group} integer. $n$ $a$]} is 
%       $\sum_{i=1}^n a$.
%       
%       The notation is chosen to on one hand make it easy to turn an 
%       additive group into a $\mathbb{Z}$-module, but on the other 
%       hand stay distinct so that it does not conflict with the scalar 
%       multiple of modules of other rings.
%   \end{APIdescription}
%   All methods are congruent.
% \end{APIspec}
% 
% \begin{APIspec}{additive group}{1.3}
%   Version 1.3 of \texttt{additive group} improves on v\,1.2 by adding 
%   a linear combination extension of the integer multiple method.
%   \begin{APIdescription}{group}
%     \begin{APImethod}{+integer.}
%       \begin{regblock}[\regstar] \word{integer} \word{element} 
%       \end{regblock}
%     \end{APImethod}
%       The value of
%       \begin{displaysyntax}
%         [\meta{group} *\^{} $n_1$ $a_1$ $\dots$ $n_k$ $a_k$]
%       \end{displaysyntax}
%       is $\sum_{i=1}^k n_1 a_1$, i.e., on one hand
%       \begin{displaysyntax}
%         [$G$ +integer. $a$ $n$]\par
%         [$G$ integer. $a$ $n$]
%       \end{displaysyntax}
%       are |=|-equal for every element $a$ and integer $n$, and on the 
%       other,
%       \begin{displaysyntax}
%         [$G$ +integer. \meta{$L_a$} \meta{$L_b$}]\par
%         [$G$ + [$G$ +integer. \meta{$L_a$}] 
%           [$G$ +integer. \meta{$L_b$}]]
%       \end{displaysyntax}
%       for all lists $L_a$ and $L_b$ with the structure
%       \begin{quote}
%         \begin{regblock}[\regstar] \word{integer} \word{element} 
%         \end{regblock}
%       \end{quote}
%   \end{APIdescription}
%   All methods are congruent.
% \end{APIspec}
% 
% 
% 
% 
% 
% \begin{proc}{make_group_additive}
%   
% \end{proc}
% 
% \section{Related interfaces}
% 
% 
% \begin{APIspec}{division}{1.0}
%   The |division| interface specifies the existence of a binary 
%   division operation |/| that is an inverse of |*|. The quotient 
%   need not be defined for all pairs of elements. It probably makes 
%   more sense if |*| is at least associative, but is perfectly 
%   possible to define even in other situations.
%   \begin{APIdescription}{magma}
%     \begin{APImethod}{=}
%       \word{element} \word{element}
%     \end{APImethod}
%       The |=| method must satisfy \APIref+{equality}{1.0}.
%     \begin{APImethod}{*}
%       \word{element} \word{element}
%     \end{APImethod}
%       The |*| method returns an element.
%     \begin{APImethod}{/}
%       \word{element} \word{element}
%     \end{APImethod}
%       This method may throw an error, but if
%       \begin{displaysyntax}
%         [$M$ / $a$ $b$]
%       \end{displaysyntax}
%       for elements $a$ and $b$ of a \meta{magma} $M$ returns $x$ 
%       then that $x$ must be an element such that the two expressions
%       \begin{displaysyntax}
%         [$M$ * $b$ $x$]\par
%         $a$
%       \end{displaysyntax}
%       are |=|-equal.
%       
%       \begin{remark}
%         In terms of an multiplicative inverse, this defines $a/b$ 
%         to be $b^{-1}a$, i.e., it is a \emph{left} division. This 
%         may seem unintuitive, but it makes it possible to have 
%         \(a/(bc) = (a/b)/c\). Right division would have \(a/(bc) = 
%         (a/c)/b\).
%       \end{remark}
%       
%       If this method throws an error, then it should set the 
%       |-errorcode| to one of the following lists:
%       \begin{displaysyntax}
%         API division nosolution\par
%         API division unimplemented
%       \end{displaysyntax}
%       Use of the |nosolution| form signals that there really isn't 
%       any solution $x$ to \(bx=a\). Use of the |unimplemented| form 
%       merely means that division has not been implemented for these 
%       arguments (e.g.~a ring of polynomials might have division 
%       implemented only for monomial denominators), in which case 
%       the error does not imply nonexistence of a solution.
%   \end{APIdescription}
%   
%   Note that |/| is not required to be congruent. This is 
%   because the \texttt{division} interface does not require the 
%   equation \(bx=a\) to have a unique solution, and 
%   ensuring that the choice of solution is independent of 
%   argument representation could well be unreasonably expensive. 
% \end{APIspec}
% 
% 
% 
% \begin{ensemble}{free_abelian_group}
%   The |free_abelian_group| ensemble implements a free abelian group 
%   on top of a structure with \APIref{canonise}{1.0}. Unlike 
%   |power_product_monoid_1.3|, it uses a sparse representation 
%   (dictionary mapping generator to exponent), so it is better 
%   suited in cases with many generators. It is expected that 
%   combining this with |semigroup_algebra| will be the main way of 
%   implementing polynomial-like expressions.
%   \begin{tcl}
%<*docstrip.tcl::catalogue>
pkgProvide mtmtcl::groups::free_abelian_group 1.0 freeabelian
%</docstrip.tcl::catalogue>
%   \end{tcl}
%   
%   The full call syntax of the ensemble is
%   \begin{displaysyntax}
%     |mtmtcl::groups::free_abelian_group| \word{generator-structure} 
%     \word{sorter} \word{subcommand} \meta{arguments}
%   \end{displaysyntax}
%   where \word{generator-structure} is the underlying structure of 
%   generators. The \word{sorter} is a command prefix with the 
%   structure
%   \begin{displaysyntax}
%     \meta{sorter} \word{generator-list}
%   \end{displaysyntax}
%   which, when given a list of elements from the generator 
%   structure, returns a sorted list of those elements.
%   \begin{tcl}
%<*freeabelian,pkg>
namespace eval mtmtcl::groups::free_abelian_group {
   namespace ensemble create -parameters {set sorter}
   namespace export {[!-^`-~]*}
   interp alias {} [namespace current]::_OM {}\
     [namespace parent [namespace parent]]::openmath::OM
}
%   \end{tcl}
%   In practice, the \word{sorter} can often be an |lsort| with some 
%   options. The reason to make it a separate parameter, rather than 
%   an API supported by the generator structure, is that one often 
%   wishes to customise the sorting of factors in products---needing 
%   to bundle that with a structure can be rather awkward. 
%   Conversely, it is trivial to build a \word{sorter} when given a 
%   sorting or comparing subcommand of a structure.
%   
%   As hinted above, the representation will use a dictionary mapping 
%   generators to their exponents (integers). Since this requires 
%   the generators to be canonised, there isn't much extra effort in 
%   always keeping the representations canonical: no exponent is $0$, 
%   and dictionary keys are in sorted order. In fact, it makes sense 
%   to \emph{only} acknowledge these canonical representations as 
%   correct.
%   
%   \begin{ensproc}{=}
%     Because of the decision to keep group elements canonised, 
%     equality testing can be made a simple matter of 
%     |string equal|ity.
%     \begin{tcl}
proc mtmtcl::groups::free_abelian_group::= {X sorter {first ""} args} {
   foreach second $args {
      if {![string equal $first $second]} then {return 0}
   }
   return 1
}
%     \end{tcl}
%   \end{ensproc}
%   
%   \begin{ensproc}{named}
%     The |named| subcommand is used to provide the canonical mapping 
%     (as figuring in the universal property) from the generator 
%     structure to the group. Since this explicitly |canonise|s its 
%     argument, it is not necessary for the generator structure to be 
%     |onlycanonical|.
%     \begin{tcl}
proc mtmtcl::groups::free_abelian_group::named {X sorter name} {
   dict create [{*}$X canonise $name] 1
}
%     \end{tcl}
%   \end{ensproc}
%   
%   \begin{ensproc}{canonise}
%     Because this is an \APIref{onlycanonical}{1.0} structure, the 
%     |canonise| subcommand could in principle just return its 
%     argument (not canonical for noncanonical key orderings, but 
%     by specification such things are not proper representations, so 
%     behaviour is undefined), but it it more useful to do a full 
%     canonisation; this can for example be used to recanonise 
%     elements after switching \word{sorter}.
%     \begin{tcl}
proc mtmtcl::groups::free_abelian_group::canonise {X sorter elem} {
   set D [dict create]
   dict for {k v} $elem {
      dict incr D [{*}$X canonise $k] $v
   }
   set res [dict create]
   foreach k [{*}$sorter [dict keys $D]] {
      if {[dict get $D $k]} then {
         dict set res $k [format %lld [dict get $D $k]]
      }
   }
   return $res
}
%     \end{tcl}
%   \end{ensproc}
%   
%   \begin{ensproc}{*}
%     The multiplication operation is what is needed to additionally 
%     support \APIref{semigroup}{1.1}. Implementation-wise it is 
%     similar to |canonise|, but it doesn't |format| the exponents 
%     since it is only expected to operate on canonical 
%     representations.
%     \begin{tcl}
proc mtmtcl::groups::free_abelian_group::* {X sorter args} {
   set D [dict create]
   foreach elem $args {
      dict for {k v} $elem {dict incr D $k $v}
   }
   set res [dict create]
   foreach k [{*}$sorter [dict keys $D]] {
      if {[dict get $D $k]} then {
         dict set res $k [dict get $D $k]
      }
   }
   return $res
}
%     \end{tcl}
%   \end{ensproc}
%   
%   \begin{ensproc}{1}
%     A unit operation is what is needed to additionally 
%     support \APIref{monoid}{1.1}.
%     \begin{tcl}
proc mtmtcl::groups::free_abelian_group::1 {X sorter} {
   dict create
}
%     \end{tcl}
%   \end{ensproc}
%   
%   \begin{ensproc}{inverse}
%     An inverse operation is what is needed to additionally 
%     support \APIref{group}{1.1}. It does not have to resort or 
%     check exponents for being zero, as that should already be in 
%     order.
%     \begin{tcl}
proc mtmtcl::groups::free_abelian_group::inverse {X sorter elem} {
   set res [dict create]
   dict for {k v} $elem {
      dict set res $k [expr {-$v}]
   }
   return $res
}
%     \end{tcl}
%   \end{ensproc}
%   
%   \begin{ensproc}{^}
%     The power operation is what is needed to additionally 
%     support \APIref{group}{1.2}. It is implementation-wise similar 
%     to |inverse|, except in the case that the exponent $n$ is $0$.
%     \begin{tcl}
proc mtmtcl::groups::free_abelian_group::inverse {X sorter elem n} {
   set res [dict create]
   if {$n == 0} then {return $res}
   dict for {k v} $elem {
      dict set res $k [expr {$n*$v}]
   }
   return $res
}
%     \end{tcl}
%   \end{ensproc}
%   
%   A power product method would be possible, but I don't need it at 
%   the moment, so it can be a project for another day. Similarly, 
%   one could implement \APIref{division}{1.0}, but I can do without 
%   that one too.
%   
%   \begin{ensproc}{generators}
%     The |generators| subcommand gives access to the generator 
%     structure.
%     \begin{tcl}
proc mtmtcl::groups::free_abelian_group::generators {X sorter args} {
   tailcall {*}$X {*}$args
}
%     \end{tcl}
%   \end{ensproc}
%   
%   \begin{ensproc}{export}
%     Of practical importance is the |export| subcommand required by  
%     the \APIref+{export}{2.0} interface.
%     \begin{tcl}
proc mtmtcl::groups::free_abelian_group::export {X sorter elem attr} {
   set root [list OMA $attr]
   set L [list [_OM mS arith1 times $attr *]]
   set gattr $attr
   dict lappend gattr mtmtcl:path generators
   set power [_OM mS arith1 power $attr ^] 
   dict for {k v} $elem {
      set base [{*}$X export $k $gattr]
      if {$v != 1} then {
         set base [list OMA $attr [list $power $base [_OM I $v]]]
      }
      lappend L $base
   }
   lappend root $L
}
%     \end{tcl}
%   \end{ensproc}
%   
%   \begin{ensproc}{API}
%     This doesn't test the |export| preconditions properly, but it's 
%     good enough for now.
%     \begin{tcl}
proc mtmtcl::groups::free_abelian_group::API {X sorter args} {
   ::API::static [lindex {{} {
      equality 1.1
      onlycanonical 1.0
      canonise 1.1
      "named element" 1.0
      semigroup 1.1
      monoid 1.1
      group 1.2
      export 2.0
   }} [{*}$X API canonise 1.0]] {*}$args
}
%</freeabelian,pkg>
%     \end{tcl}
%   \end{ensproc}
% \end{ensemble}
% 
% \begin{APIspec}{generated group}{1.0}
%   If a group is generated by a known subset of elements, then it 
%   can be useful to have an operation which produces an expression 
%   in terms of those generators for arbitrary elements of the group. 
%   This is what this interface specifies.
%   
%   \begin{APIdescription}{group}
%     \begin{APImethod}{=}
%       \word{element} \word{element}
%     \end{APImethod}
%     \begin{APImethod}{*}
%       \word{element} \word{element}
%     \end{APImethod}
%     \begin{APImethod}{1}
%     \end{APImethod}
%     \begin{APImethod}{inverse}
%       \word{element}
%     \end{APImethod}
%       First of all, the |group| interface version~1.0 must be 
%       satisfied. Denote by $G$ the upgrade of \meta{group} to 
%       version~1.3 of this interface.
%       
%     \begin{APImethod}{named}
%       \word{name}
%     \end{APImethod}
%       Second, the |named element| interface version~1.0 must also 
%       be satisfied.
%       
%     \begin{APImethod}{* decomposition}
%       \word{element}
%     \end{APImethod}
%       This method returns a list
%       \begin{displaysyntax}
%         \begin{regblock}[\regstar] \word{name} \word{integer} 
%         \end{regblock}
%       \end{displaysyntax}
%       such that if the returned value is $s_1$ $n_1$ $\dots$ $s_k$ 
%       $n_k$ then the return value of
%       \begin{displaysyntax}
%         [$G$ |*^| [$G$ named $s_1$] $n_1$ $\dots$ 
%         [$G$ named $s_k$] $n_k$]
%       \end{displaysyntax}
%       is |=|-equal to the \word{element}.
%   \end{APIdescription}
% \end{APIspec}
% 
% 
% \begin{APIspec}{generated additive group}{2.0}
%   If a group is generated by a known subset of elements, then it 
%   can be useful to have an operation which produces an expression 
%   in terms of those generators for arbitrary elements of the group. 
%   This is what this interface specifies.
%   
%   \begin{APIdescription}{group}
%     \begin{APImethod}{=}
%       \word{element} \word{element}
%     \end{APImethod}
%     \begin{APImethod}{+}
%       \word{element} \word{element}
%     \end{APImethod}
%     \begin{APImethod}{0}
%     \end{APImethod}
%     \begin{APImethod}{neg}
%       \word{element}
%     \end{APImethod}
%       First of all, the |additive group| interface version~2.0 must 
%       be satisfied. Denote by $G$ the upgrade of \meta{group} to 
%       version~2.3 of this interface.
%       
%     \begin{APImethod}{named}
%       \word{name}
%     \end{APImethod}
%       Second, the |named element| interface version~1.0 must also 
%       be satisfied.
%       
%     \begin{APImethod}{+ decomposition}
%       \word{element}
%     \end{APImethod}
%       This method returns a list
%       \begin{displaysyntax}
%         \begin{regblock}[\regstar] \word{name} \word{integer} 
%         \end{regblock}
%       \end{displaysyntax}
%       such that if the returned value is $s_1$ $n_1$ $\dots$ $s_k$ 
%       $n_k$ then the return value of
%       \begin{displaysyntax}
%         [$G$ +integer. $n_1$ [$G$ named $s_1$] $\dots$ $n_k$ 
%         [$G$ named $s_k$]]
%       \end{displaysyntax}
%       is |=|-equal to the \word{element}.
%   \end{APIdescription}
% \end{APIspec}
% 
% \begin{APIspec}{generated additive group}{1.0}
%   This is the same as version~2.0, except that it incorporates 
%   version 1.0 of \APIref{additive group}{1.0} rather than~2.0.
% \end{APIspec}
% 
% 
\endinput