# FreeMonoid S¶

free.spad line 110 [edit on github]

S: SetCategory

The free monoid on a set `S`

is the monoid of finite products of the form `reduce(*, [si ^ ni])`

where the `si`

`'s`

are in `S`

, and the `ni`

`'s`

are nonnegative integers. The multiplication is not commutative. When `S`

is an OrderedSet, then FreeMonoid(`S`

) has order: for two elements `x`

and `y`

the relation `x < y`

holds if either `length(x) < length(y)`

holds or if these lengths are equal and if `x`

is smaller than `y`

`w`

.`r`

.`t`

. the lexicographical ordering induced by `S`

.

- 1: %
from MagmaWithUnit

- *: (%, S) -> %
`x * s`

returns the product of`x`

by`s`

on the right.

- *: (S, %) -> %
`s * x`

returns the product of`x`

by`s`

on the left.

- <=: (%, %) -> Boolean if S has OrderedSet
from PartialOrder

- <: (%, %) -> Boolean if S has OrderedSet
from PartialOrder

- >=: (%, %) -> Boolean if S has OrderedSet
from PartialOrder

- >: (%, %) -> Boolean if S has OrderedSet
from PartialOrder

- ^: (%, NonNegativeInteger) -> %
from MagmaWithUnit

- ^: (%, PositiveInteger) -> %
from Magma

- ^: (S, NonNegativeInteger) -> %
`s ^ n`

returns the product of`s`

by itself`n`

times.

- coerce: % -> OutputForm
from CoercibleTo OutputForm

- coerce: S -> %
from CoercibleFrom S

- divide: (%, %) -> Union(Record(lm: %, rm: %), failed)
`divide(x, y)`

returns the left and right exact quotients of`x`

by`y`

, i.e.`[l, r]`

such that`x = l * y * r`

, “failed” if`x`

is not of the form`l * y * r`

.

- factors: % -> List Record(gen: S, exp: NonNegativeInteger)
`factors(a1\^e1, ..., an\^en)`

returns`[[a1, e1], ..., [an, en]]`

.

- first: % -> S
`first(x)`

returns the first letter of`x`

.

- hclf: (%, %) -> %
`hclf(x, y)`

returns the highest common left factor of`x`

and`y`

, i.e. the largest`d`

such that`x = d a`

and`y = d b`

.

- hcrf: (%, %) -> %
`hcrf(x, y)`

returns the highest common right factor of`x`

and`y`

, i.e. the largest`d`

such that`x = a d`

and`y = b d`

.

- latex: % -> String
from SetCategory

- leftPower: (%, NonNegativeInteger) -> %
from MagmaWithUnit

- leftPower: (%, PositiveInteger) -> %
from Magma

- leftRecip: % -> Union(%, failed)
from MagmaWithUnit

- length: % -> NonNegativeInteger
`length(x)`

returns the length of`x`

.

- lexico: (%, %) -> Boolean if S has OrderedSet
`lexico(x, y)`

returns`true`

iff`x`

is smaller than`y`

`w`

.`r`

.`t`

. the pure lexicographical ordering induced by`S`

.

- lquo: (%, %) -> Union(%, failed)
`lquo(x, y)`

returns the exact left quotient of`x`

by`y`

i.e.`q`

such that`x = y * q`

, “failed” if`x`

is not of the form`y * q`

.

- lquo: (%, S) -> Union(%, failed)
`lquo(x, s)`

returns the exact left quotient of`x`

by`s`

.

- mapExpon: (NonNegativeInteger -> NonNegativeInteger, %) -> %
`mapExpon(f, a1\^e1 ... an\^en)`

returns`a1\^f(e1) ... an\^f(en)`

.

- mapGen: (S -> S, %) -> %
`mapGen(f, a1\^e1 ... an\^en)`

returns`f(a1)\^e1 ... f(an)\^en`

.

- max: (%, %) -> % if S has OrderedSet
from OrderedSet

- min: (%, %) -> % if S has OrderedSet
from OrderedSet

- mirror: % -> %
`mirror(x)`

returns the reversed word of`x`

.

- 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`

.

- one?: % -> Boolean
from MagmaWithUnit

- overlap: (%, %) -> Record(lm: %, mm: %, rm: %)
`overlap(x, y)`

returns`[l, m, r]`

such that`x = l * m`

,`y = m * r`

and`l`

and`r`

have no overlap, i.e.`overlap(l, r) = [l, 1, r]`

.

- recip: % -> Union(%, failed)
from MagmaWithUnit

- rest: % -> %
`rest(x)`

returns`x`

except the first letter.

- retract: % -> S
from RetractableTo S

- retractIfCan: % -> Union(S, failed)
from RetractableTo S

- rightPower: (%, NonNegativeInteger) -> %
from MagmaWithUnit

- rightPower: (%, PositiveInteger) -> %
from Magma

- rightRecip: % -> Union(%, failed)
from MagmaWithUnit

- rquo: (%, %) -> Union(%, failed)
`rquo(x, y)`

returns the exact right quotient of`x`

by`y`

i.e.`q`

such that`x = q * y`

, “failed” if`x`

is not of the form`q * y`

.

- rquo: (%, S) -> Union(%, failed)
`rquo(x, s)`

returns the exact right quotient of`x`

by`s`

.

- sample: %
from MagmaWithUnit

- size: % -> NonNegativeInteger
`size(x)`

returns the number of monomials in`x`

.

- smaller?: (%, %) -> Boolean if S has Comparable
from Comparable

- varList: % -> List S
`varList(x)`

returns the list of variables of`x`

.

Comparable if S has Comparable

OrderedMonoid if S has OrderedSet

OrderedSemiGroup if S has OrderedSet

OrderedSet if S has OrderedSet

PartialOrder if S has OrderedSet