# Module Monoidal

`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_left` cycles the elements in the sequence argument one position to the left.
See :
` 'rotate_right : `seq -> seq``
`rotate_right` cycles the elements in the sequence argument one position to the right.
See :
` '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.
See :
` '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.
See :
` 'matrix_dim : `seq -> int``
`matrix_dim(s)` returns the maximal nesting of sequences in `s`.
See : 'rank
` '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``

Example :
``rank((1, 2)::(3, 4)::(5,6)::(7,8)::seq:());;``
returns `(4, 2):'seq`.
See : 'matrix_dim
` '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.
Example :
``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``

See : 'rank
` '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)`.
See : 'rank
` 'transpose : `seq -> seq``
`transpose(m)` returns the transposition of the 2-dimensionnal matrix `m`.
See : 'matrix_check
` '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)``

Example :
``'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)``

Example :
``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 `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`.
Example :`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.
Example :
``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 non­overlapping 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 non­overlapping 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``

See : 'filter
See : 'partition_eq
` '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.
Example :
``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`