`module Monoidal: ``sig end`

The *monoidal* collection: set, bag and sequence.

` 'left : ``seq -> int -> any`

Returns the value at the left of an element in a sequence.

`'left(l, p)`

returns the element at the left of position `p`

in the
sequence `l`

. Position in a sequence are integers.

This function is also a special form in a transformation.

**See** : 'right

**See** : 'collection

**See** : chapter functional

` 'right : ``seq -> int -> any`

Returns the value at the right of an element in a sequence.

`'right(l, p)`

returns the element at the right of position `p`

in the
sequence `l`

. Position in a sequence are integers.

This function is also a special form in a transformation.

**See** : 'left

**See** : 'collection

**See** : chapter functional

` 'reverse : ``seq -> seq`

Sequence reversal.

` 'rotate_left : ``seq -> seq`

` 'rotate_right : ``seq -> seq`

` 'pad_right : ``seq -> int -> any -> seq`

`pad_right(s, n, v0)`

makes a sequence of length `n`

by truncating
or padding `s`

with `v0`

on the right.` 'pad_left : ``seq -> int -> any -> seq`

`pad_left(s, n, v0)`

makes a sequence of length `n`

by truncating
or padding `s`

with `v0`

on the left.` 'matrix_dim : ``seq -> int`

` 'rank : ``seq -> seq`

`matrix_rank(s)`

returns the rank of the argument. The rank is a sequence of integers
where element `i`

represents the maximal number of elements in dimension `i`

when `s`

is viewed as a matrix. The size of the rank (i.e. the length of the returned sequence)
is the dimension of the matrix as computed by `'matrix_dim`

.
Note that if one will interpret the first element in the rank as
the number of rows in the matrix, and the second number as the number of columns, then a
nested sequence like `(1, 2)::(3, 4)::(5,6)::(7,8)::seq:()`

must be visualized as:

` 1 2`

` 3 4`

` 5 6`

` 7 8`

`rank((1, 2)::(3, 4)::(5,6)::(7,8)::seq:());;`

returns `(4, 2):'seq`

.` 'matrixify : ``seq -> seq`

`matrixify(s)`

returns a proper matrix build on `s`

. The rank of the returned sequence `m`

is
the rank of `s`

and `m`

is a proper matrix. In the process of building the proper matrix, if a
non-sequence element is provided where a sequence is required, then this element is replicated
to form a sequence as many times as necessary. If a provided sequence is shorter than a required
sequence, then the shorter sequence is padded with `<undef>`

values.`matrixify(1::2::(3::4::5::():seq)::6::():seq);;`

returns a `4x3`

matrix:
`((1, 1, 1):'seq, `

` (2, 2, 2):'seq, `

` (3, 4, 5):'seq, `

` (6, 6, 6):'seq):'seq `

and
`matrixify((1,2)::(3,4,5)::():seq);;`

build the `2x3`

matrix:
`((1, 2, <undef: matrixify>):'seq,`

` (3, 4, 5):'seq):'seq`

` 'matrix_check : ``any -> any`

`matrix_check(s)`

checks if `s`

is a matrix of dimension 2.
A matrix is a sequence of sequences of equal length. `matrix_check(s)`

returns `false`

if `s`

cannot be considered as a 2 dimensionnal matrix, else it returns a sequence of two integers
`(n, m)`

where `n`

is the number of elements at the top level sequence and `m`

the length of the
nested sequences. The elements of a 2 dimensionnal matrix are arbitrary and can be themselves sequences.
So a 3 dimensional matrix is also 2 dimensional matrix valued by sequences. In consequence, the value
`(n, m)`

returned by `matrix_check(s)`

does not coincide with `rank(s)`

.` 'transpose : ``seq -> seq`

` 'outerproduct : ``funct -> funct -> seq -> seq -> seq`

`outerproduct(f1, f2, s1, s2)`

computes the outer product of matrix or vector `s1`

and `s2`

.` 'scalarproduct : ``seq -> seq -> seq`

`scalarproduct(s1, s2)`

computes the scalar product of two vectors `s1`

and `s2`

.
`scalarproduct(s1, s2)`

is equivalent to
`outerproduct((\x, y.x+y), (\x, y.x*y), s1, s2)`

` 'matrix_vector_product : ``seq -> seq -> seq`

`matrix_vector_product(m, v)`

computes the product of matrix `m`

with vector `v`

.
`matrix_vector_product(m, v)`

is equivalent to
`outerproduct((\x, y.x+y), (\x, y.x*y), m, v)`

`'matrix_vector_product((1, 2)::(3, 4)::(5,6)::(7,8)::seq:(), (10, 11));;`

returns
`(32, 74, 116, 158):'seq`

` 'matrix_matrix_product : ``seq -> seq -> seq`

`matrix_matrix_product(m1, m2)`

computes the product of two matrices.
`matrix_matrix_product(m1, m2)`

is equivalent to
`outerproduct((\x, y.x+y), (\x, y.x*y), m1, m2)`

`matrix_matrix_product((1, 2)::(3, 4)::(5,6)::seq:(), (10, 11, 12)::(20, 21, 22)::seq:());;`

returns
`((50, 53, 56):'seq, (110, 117, 124):'seq, (170, 181, 192):'seq):'seq`

.
In tabular form, we have computed:

` | 1 2 | | 10 11 12 | | 50 53 56 | `

` | 3 4 | . | 20 21 22 | = | 110 117 124 | `

` | 5 6 | | 170 181 192 | `

` 'iota : ``int -> monoidal -> monoidal`

Enumerate the

**Example** :

`n`

first integers.
Given an integer `n`

and a monoidal collection `m`

, the expression
`iota(n+1, m)`

returns the value `0, 1, 2, ..., n, m`

.`iota(3, (2, 3, 4))`

returns the sequence
`0, 1, 2, 2, 3, 4`

and `iota(3, (2, 3, 4, set:()))`

returns the set
`0, 1, 2, 3, 4, set:()`

.` 'filter : ``funct -> monoidal -> monoidal`

`'filter(p, c)`

returns all the elements of the monoidal collection `c`

that satisfy the predicate `p`

. If `c`

is a sequence, the order of the elements
in the input sequence is preserved.` 'flatten : ``monoidal -> monoidal`

`flatten(col)`

flattens a sequence of sequences, or a set of sets, or a bag of bags.
The flattening occurs only at the first level. The flattening of the `n`

first nested levels
of a monoid can be achieved by iteration: `flatten['iter=n](col)`

By definition, `flatten(x) == x`

if `x`

is not a monoidal
collection.`flatten(1::(2::22::222::(5, 55, 555, 5555)::():seq)::3::4::():seq)`

`== (1, 2, 22, 222, (5, 55, 555, 5555):'seq, 3, 4):'seq`

and
`flatten['iter=2](1::(2::22::222::(5, 55, 555, 5555)::():seq)::3::4::():seq)`

`(== 1, 2, 22, 222, 5, 55, 555, 5555, 3, 4):'seq`

` 'partition : ``int -> monoidal -> monoidal`

`funct -> monoidal -> monoidal `

`partition(n, s)`

, with `n`

an integer, partitions a monoid `s`

(i.e. a seq, a set or a bag)
into nonoverlapping submonoids of length `n`

(except for one).

`partition(fct, s)`

, with `fct`

a predicate, partitions a monoid `s`

(i.e. a seq, a set or a bag)
into two nonoverlapping submonoids `s1`

and `s2`

, where
`s1`

is the monoid of all the elements of `s`

that satisfy the
predicate `fct`

, and `s2`

is the set of all the elements of
`s`

that do not satisfy `fct`

.

**Example** :

`partition(3, (1, 2, 3, 4, 5, 6, 7)) == ((1, 2, 3):'seq, (4, 5, 6):'seq, (7):'seq):'seq`

`partition((\x.x<3), (1, 2, 3, 4, 5, 6, 7, ():set)) == (((1, 2):'set, (3, 4, 5, 6, 7):'set):'set`

` 'partition_eq : ``funct -> monoidal -> monoidal`

`partition_eq(f, s)`

partitions a sequence `s`

into subsequences of elements of
the same equivalence class. Two elements `x`

and `y`

are of the same equivalence
class if `f(x, y)`

is true.`partition_eq((\x,y.true), (1, 2, 3, 4, 5)) == (5, 4, 3, 2, 1):'seq):'seq`

`partition_eq((\x,y.false), (1, 2, 3, 4, 5, bag:())) == ((1):'bag, (2):'bag, (3):'bag, (4):'bag, (5):'bag):'bag`

`partition_eq((\x,y.x%2==y%2), (1, 2, 3, 4, 5, set:())) == (((2, 4):'set, (1, 3, 5):'set):'set`

` 'cons : ``any -> seq -> seq`

`any -> bag -> bag `

`any -> set -> set `

Add an element to a monoidal collection.

` ':: : ``any -> seq -> seq`

`any -> bag -> bag `

`any -> set -> set `

Add an element to a monoidal collection.

` 'append : ``seq -> seq -> seq`

`bag -> bag -> bag `

`set -> set -> set `

Concatenates two monoidal collections.

` 'join : ``any -> seq -> seq`

`any -> bag -> bag `

`any -> set -> set `

`seq -> seq -> seq `

`bag -> bag -> bag `

`set -> set -> set `

`any -> any -> seq `

Join two values. If the argument are of the same monoidal collection
types, the the result has the same collection type and corresponds
to an `append`

operation.

If one of the argument is a monoidal collection type `t`

and the
other argument is not a monoidal collection, the result is the same
as a `cons`

operation and has the type `t`

.

For the other cases, the result is the sequence of the two arguments.

` 'inter : ``bag -> bag -> bag`

`set -> set -> set `

Set or bag intersection.

` 'diff : ``bag -> bag -> bag`

`set -> set -> set `

Set or bag difference.
This is not the symetric difference: `diff(A, B)`

contains the
elements of `A`

that does not appear in `B`

. For bag difference, the
multiplicities in `B`

are not taken into account.

**Example** :`diff((1, 2, 3, set:()), (2, 3, 4, 5, set:()))`

returns `(1):set`

and
`diff((1, 1, 2, 2, 3, bag:()), (2, 3, 4, 5, bag:()))`

returns
`(1, 1):bag`

.

` 'subset : ``set -> set -> bool`

`subset(A, B)`

returns true if `A`

is included in `B`