`module Collections: ``sig end`

Generic functions acting on collections.
*different color*. As for any
other type,

A collection is an aggregate of values with a *neighborhood
relationship* between its elements. This determine a **topology**
and induces a notion of position, connected elements,
path, boundaries, etc. This topology is then used in the
definition of *transformations*.

Each collection type `t`

as a companion type `p`

used to denote the
positions of the topology of `t`

. A collection can be thought as an
association of values to the positions of a topology. The expression
`take(c, p)`

can be used to get the value associated to a position `p`

in the collection `c`

. Positions can be dependent to a given
collection (i.e. to a given value) or they can be dependent only to
the collection type. See the function *leibniz* and *newton*.
The following types are used to represent the positions of a
collection:

- the positions of a
`record`

are`string`

. These strings are the name of the fields of the record. - the positions of a
`monoidal`

collection are integers (`seq`

sequence,`set`

set and`bag`

multiset are monoidal collections). - the positions of a
`GBF`

are`posgbf`

. These values represent the elements of the group underlying the GBF. - the position of a
`grf`

(a graph) are integers that label arbitrarily the vertices of the graph. - the positions of a
`del`

(Delaunay graph) are integers that label arbitrarily the vertices of the graph.

`c`

, the function `'pospredicate_from_coll`

returns a
predicate that checks if its argument has the type of a position for the
collection `c`

. The function `'predicate_from_coll`

returns a predicate
that checks if its argument has the same type as `c`

.
Any collection type `t`

can be *subtyped* into a collection type
`t'`

of exactly the same topology. The corresponding declaration
begins with the keyword `collection`

. This implies that the
predicate `'collection`

is denoted only by its quoted name
`'collection`

.

The declaration

`collection NAME = t;;`

where `t`

is the name of a collection type, introduces a new collection
type of name `NAME`

and with the same topology as `t`

. Sometimes
`NAME`

is refered as a `t`

with a `NAME`

is also a predicate to check if a value belongs
to this type. A value of type `NAME`

is also a value of type `t`

(the subtyping relationship between `t`

and `NAME`

); however, a
value of type `t`

is not a value of type `NAME`

. In other words
`NAME(v)`

implies `t(v)`

but not the reverse.
If `t`

is a collection type, then `():t`

or `t:()`

denotes the empty
collection of type `t`

and `'empty_from_coll(c)`

returns an empty collection
with the same type as the collection `c`

.

**See** : 'leibniz

**See** : 'newton

**See** : 'monoidal

**See** : 'record

**See** : 'set

**See** : 'bag

**See** : 'seq

**See** : 'gbf

**See** : 'graph

**See** : 'delaunay

**See** : 'chain

**See** : 'qmf

` 'delaunayfy : ``del -> any -> del`

Build a delaunay.

`delaunayfy(d, c)`

build a delaunay from an existing delaunay `d`

and the elements of the collection `c`

(`c`

is not a record). The
result has the same type as `d`

and its elements is the union of the
element of `d`

and `c`

.

If the second argument is a scalar value or a record `s`

, the
elements in the result are the elements of `d`

plus the element `s`

.

**See** : chapter Delaunay.

` 'graphify : ``collection -> grf`

`collection -> delaunay `

Transform a delaunay-type graph into a graph.
It is the identity function on regular graphs.

` 'isomorphism : ``del -> del -> bool`

`grf -> grf -> bool `

Test the isomorphism of two graphs.
Computes if two graph collections are isomorphic (the carrier graphs
must be isomorphic and two identified vertices must be labeled with
the same values).

` 'achain : ``any -> bool`

Achain type and predicate.

` 'achainify : ``collection -> achain`

Transform its argument into a achain.

`'achainify(c)`

returns the achain of the elements of the collection
`c`

.` 'set : ``any -> bool`

` 'seq : ``any -> bool`

` 'sequify : ``scalar -> seq`

`posgbf -> seq `

`collection -> seq `

Transform its argument into a sequence.

`'sequify(c)`

returns the sequence of the elements of the collection
`c`

. If `c`

is already a sequence, `sequify`

is the identity.

`'sequify(s)`

where `s`

is a string returns a sequence where the element `i`

in the
sequence is a string with only one character, the `i`

th character of`s`

`'sequify(p)`

where `p`

is a `posgbf`

returns the sequence of the
coefficient of the smith normal form of `p`

.

`'sequify(s)`

where `s`

is a scalar that is not a `posgbf`

or a `string`

returns the singleton sequence with `s`

as the unique element.

**Example** :`string_to_seq("abc")`

returns `"a", "b", "c", seq:()`

` 'record : ``any -> bool`

Record type and predicate.

A record is a collection of elements munished with a void topology (an element has no neighbors). The elements of a record are the values associated to the fields of the records.

Record's are constructed types. The corresponding declaration
begins with the keyword `record`

. This implies that the
corresponding predicate is denoted only by its quoted name
`'record`

.

**See** : the chapter record in the documentation.

` 'qmf : ``any -> bool`

Qmf type and predicate.

` 'gbf : ``any -> bool`

` 'bag : ``any -> bool`

Bag (multiset) type and predicate. A multiset is a set where
the same element can occur several times.

**See** : 'set

**See** : 'seq

**See** : 'monoidal

` 'monoidal : ``any -> bool`

Monoidal type and predicate.
*abstract type*: it does not exist
a value that have precisely this type.

`monoidal`

is the name of an `monoidal`

rather represents
the kind of the collection types that represent a space whose
topology is based on a monoid: `set`

, `bag`

(multiset) and `seq`

(sequence or list). These three collection types are leibnizian.
Like any other type, `monoidal`

is also a predicate that can be used
to check if the type of a value is a subtype of
`monoidal`

.
Some functions are applicable to all monoidal types: `cons`

, `join`

,
`append`

, etc. Cf. the section Monoidal.

**See** : the chapter monoidal in the documentation.

**See** : 'set

**See** : 'seq

**See** : 'bag

**See** : 'leibniz

` 'leibniz : ``any -> bool`

Leibniz type and predicate.
*abstract type*: it does not exist
a value that have precisely this type.

**See** : 'newton

**See** : 'collection

`leibniz`

is the name of an `leibniz`

rather
represents the kind of the collection types that admits free
transformations. Like any other type, `leibniz`

is also a predicate
that can be used to check if a value has a leibnizian type.
The collection types are divided into `leibnizian`

and `newtonian`

kinds. These names are after the philosophical positions advocated
by Newton and Leibniz on the nature of `space`

.

In a leibnizian space, the space is formed only by the presence of the objects in it: it is the positional relationships between material objects that are present together. In this view, the concept of the places or of the position of an empty space is inconceivable.

In a newtonian space, the space preexists to the objects and play the role of a scene where the objects can be placed. Though as a box, it is always possible to speak and designate the positions of an empty space.

Examples of leibnizian collection types are: `monoidal`

collections
(set, bag and seq) and `delaunay`

. Leibnizian collections are always
`total`

data-structure, that is, each element in the collection has
a well-defined value. Examples of newtonian types include `record`

and `gbf`

. Newtonian collection can be `partial`

data-structure
(e.g. arrays with hole).

Practically this two opposed views of the concept of space raise two different kind of spaces that exhibits different behaviors:

: A leibnizian collection cannot have`<undef>`

values in the collection`<undef>`

elements. For instance, the expression

build the sequence`1, <undef>, 2, <undef>, 3`

`1, 2, 3`

. In other word, leibnizian collections are total data-structure.On the other hand, a newtonian collection can be partial. For example, an infinite GBF of a type like

`G = <a, b>`

holds an infinite number of undefined values.The characterization

*leibniz = total*and*newton = partial*is a rough approximation : it is possible to build in special circumstance a leibnizian collection including`<undef>`

elements. Refer to the MGS tutorial for a full development.*Positions*: Each collection type`t`

as a companion type`p`

used to denote the positions of the topology of`t`

. For example, a value of type`p`

is used as an argument of the`take`

function. For a leibnizian type, a position has a value relevant for a given collection and cannot be used accross collections. For newtonian type, the positions preexist to any collection of this type and can be used across collections.For example, integers are used to access the elements in a set (a leibnizian collection). However, accessing the 100th element of a set of 3 elements has no meaning. Even if there is enough elements, a position is related to a unique collection. For example, let

`s1`

and`s2`

two sets that are equal:`s1 == s2`

, but built differently (they are the result of different computations). Then, we can have`take(s1, 1) <> take(s2, 1)`

even if there is more than one element in these equal sets.In the other hand, let

`G`

be a GBF defined by`G = < a, b >`

(GBF are newtonian collection). The positions of the GBF`G`

are a new scalar type and`p == 2*|a> + 3*|b>`

is a position related to the collection type`G`

. Any collection of type`G`

can be queryed for the element at position`p`

. Eventually this value is`<undef>`

. But for any GBF`g1`

and`g2`

such that`g1 == g2`

, we have`take(g1, p) == take(g2, p)`

for any position`p`

.*Deletion and erasure rules*: A rule of form

in a transformation is interpreted as:`... => <undef>`

- a
`deletion`

rule if it is applied to a leibnizian collection: the elements matched by the left hand side of the rule are deleted in the result. - an
`erasure`

rule if it is applied to a newtonian collection: the values associated to the positions matched by the left hand side of the rule are replaced by`<undef>`

.

`3 => <undef>`

applied to the sequence`1, 2, 3, 4, 3, 5`

returns the shorter sequence`1, 2, 4, 5`

. Applied to a GBF, this rule replaces each value`3`

by`<undef>`

.- a

` 'newton : ``any -> bool`

Newton type and predicate.
*abstract type*: it does not exist
a value that have precisely this type.

**See** : 'leibniz

**See** : 'collection

`newton`

is the name of an `newton`

rather
represents the kind of the collection types that represent a
space independent of the values it holds. Examples of newtonian types
include `record`

and `gbf`

. Newtonian collection can be `partial`

data-structure (e.g. arrays with hole). See `leibniz`

for a more
detailed explanation.` 'collection : ``any -> bool`

Collection type and predicate.
*abstract type*: it does not exist
a value that have precisely this type.

**See** : 'leibniz

**See** : 'newton

**See** : 'monoidal

**See** : 'record

**See** : 'set

**See** : 'bag

**See** : 'seq

**See** : 'gbf

**See** : 'graph

**See** : 'delaunay

**See** : 'chain

**See** : 'qmf

`collection`

is the name of an `collection`

rather
represents the type of any collection type. Like any other type,
`collection`

is also a predicate. This predicate can be used to
distinguish between atomic (or scalar) values (like integers, floats,
booleans, strings...) and collection values (like records,
sequences, sets, gbfs, graphs, etc.)` 'collection_name : ``any -> bool`

On n'ajoute pas ce predicat à la main :
** il sera ajoute automatiquement via la table des descripteurs de types
*

` 'pospredicate_from_coll : ``collection -> funct`

Return the type predicate of the positions of a collection.
The argument is a collection and this function return the
predicate that answer true if its argument represent a position in
the collection type. For example, for

`'seq`

the predicate returned
is `'int`

.` 'empty_from_coll : ``collection -> collection`

Return an empty collection of the same type has its argument. The argument must be
a collection.

` 'predicate_from_coll : ``collection -> funct`

Return the type predicate of the type of its argument. The argument must be
a collection.

` 'set_color : ``collection -> collection -> collection`

Return its first argument with its color changed for the second one or raise
an error if it is not possible.

` 'size : ``any -> int`

Returns the number of elements in a collection (i.e. a positive or
null integer). If the argument is not a collection, then it is a
scalar value and the integer returned is strictly negative with
the following convention:

`-1`

for an`undef`

`-2`

for an`int`

`-3`

for a`bool`

`-4`

for a`float`

`-5`

for a`string`

`-6`

for a`funct`

`-7`

for a`gbfpos`

`-8`

for a`splx`

`-9`

for a`gmap`

`-10`

for an`ncell`

`-11`

for an`bint`

` 'empty : ``collection -> bool`

Returns

`true`

if the argument is an empty collection and `false`

if the argument is a non-empty collection. In other words,
`empty(c) == (size(c) > 0)`

if `c`

is a collection but it is sometimes
more efficient to call `empty`

rather than `size`

.
If the argument is not a collection, then an `undef`

value
is returned.` 'extension : ``string -> seq -> collection`

Build a collection of a specified type from the listing of its
elements and positions.

`'extension("type", (P1,V1)::(P2,V2):: ... ::(Pn,Vn)::():seq)`

build a collection of type `type`

with element `Vj`

at position
`Pj`

.
The first argument is a string that represents the name of the type
of the collection to be build. The second argument is a sequence of
couples (a couple is just a sequence of two elements). Such a
couple `(p,v)`

specifies that the value `v`

is at position `p`

in
the collection to be build.

This function has a more convenient infix notation :

` type:{| P1 = V1, ..., Pn = Vn |}`

or
` {| P1 = V1, ..., Pn = Vn |}:type `

is equivalent to
`'extension("type", (P1,V1)::(P2,V2):: ... ::(Pn,Vn)::():seq)`

` 'hd : ``collection -> any`

Pick one element in a collection.
The result is

**See** : tl

**See** : take

`<undef>`

if the collection is empty.
For a sequence `l`

, the expression `hd(l)`

returns the head of
the sequence. For a monoidal collection `c`

, it is ensured that ```
c
== hd(c),tl(c)
```

. For non-monoidal collection types, an element is
returned without assuming any special property except a relationship
with the `tl`

function: `hd(c)`

is element element removed
from `c`

in `tl(c)`

. Note that it cannot be assumed that
the element returned is randomly chosen in the collection.` 'tl : ``collection -> collection`

Return the collection minus one element.
The result is

**See** : tl

**See** : take

`<undef>`

if the collection is empty.
For a sequence `l`

, the expression `tl(l)`

returns the tail of
the sequence. For a monoidal collection `c`

, it is ensured that ```
c
== hd(c),tl(c)
```

. For non-monoidal collection types, an element is
returned without assuming any special property except a relationship
with the `hd`

function: `hd(c)`

is the element removed from `c`

in
`tl(c)`

. Note that it cannot be assumed that the supressed element is
randomly chosen in the collection.` 'last : ``collection -> any`

` 'take : ``collection -> any -> any`

`collection -> int -> any `

`seq -> collection -> any `

`take(c, p)`

returns the element at position `p`

in `c`

.
See the entry `collections`

for the representation of a position
for a given collection type. If there is no element at
the given position, the value `<undef>`

is returned.

In any case, `p`

can be an integer. In this case,

`take(c, n) == hd(tl['iter=n](c))`

For sequences, a position is an integer but there is no ambiguity
since the previous relation holds.
If `p`

is a collection, then it is assumed that each element in this collection
is an integer. Then `take(s, p)`

returns a collection of the same kind as `p`

where an element `n`

has been replaced by `take(s, n)`

. Note that a position is a scalar
value, and not a collection; so there is no ambiguity with the previous meaning.

`e.(p)`

is an infix syntax for `take(e, p)`

**Example** :`(4, 5, 6, 7).(1, 2, 3, set:())`

returns `(5, 6, 7):'set`

**See** : tl

**See** : hd

` 'sort : ``funct -> collection -> seq`

Sort a collection in increasing order according to a comparison
function. The comparison function must return 0 if it arguments
compare as equal, a positive integer if the first is greater,
and a negative integer if the first is smaller.

**Example** :

`'sort((\x,y.if x> y then -1 else if x == y then 0 else 1 fi fi), (1, 2, 3, 4))`

returns
`(4, 3, 2, 1):'seq`

` 'map : ``funct -> collection -> collection`

Map a function over the elements of a collection.

**See** : iter

**See** : fold

**See** : map_indexed

`map`

is a generic operator that acts over any collection type.
The results is a collection of the same type has the argument.

**Example** :

`map((\x.x+1), (0, 1, 2))`

returns the sequence `1, 2, 3`

.` 'fold : ``funct -> any -> collection`

Fold a function over the elements of a collection.

**See** : iter

**See** : map

**See** : fold_indexed

`fold`

is a generic operator that acts over any collection type.
If `c1, c2, ..., cn`

are the elements of a collection `c`

, then ```
fold(f,
zero, c)
```

computes `f(c1, f(c2, ... f(cn, zero)))`

. If the
collection has no element, then `zero`

is returned. The computation order of
the elements in the fold is not specified and may vary even within the
same collection type and size. The accumulating function `f`

takes 2
arguments: the first is the current element and the second is the
current result.

`fold`

also accept an integer instead of a collection:
`fold(f, zero, n)`

computes `f(n, f(n-1, ... f(1, zero)))`

.

**Example** :

`fold((\x,y.1+y), 0, c)`

returns the number of elements in the collection `c`

.
`fold((\x,y.x+y), 0, 133)`

computes the sum of the integers up to `133`

.` 'iter : ``funct -> collection -> undef`

Iter a function over the elements of a collection.

**See** : map

**See** : fold

**See** : iter_indexed

`iter`

is a generic operator that acts over any collection type.
The results is undef. It is used for the side-effect of the function
applied to the collection's elements.

**Example** :

`a :=0; iter((\x.a:=a+x), (1, 2, 3))`

returns the value `<undef>`

but the value of the imperative variable
`a`

is now `6`

.` 'iter_indexed : ``funct -> collection -> undef`

Iter a function over the elements of a collection with their position.

`iter_indexed(f, c)`

is an expression that iterates the function
`f`

over the elements of the collection `c`

. The function `f`

takes
2 arguments: the first one is a position `p`

and the second is the value
at position `p`

in the collection `c`

.

`iter_indexed`

is a generic operator that acts over any collection type.
The results is undef. It is used for the side-effect of the function
applied to the collection's elements. For the representation of a
position of a collection, see the function *collection* and also
the function *leibniz* and *newton*.

**See** : iter

**See** : map_indexed

**See** : fold_indexed

` 'map_indexed : ``funct -> collection -> collection`

Map a function over the elements of a collection with their position.

`map_indexed(f, c)`

is an expression that maps the function
`f`

over the elements of the collection `c`

. The function `f`

takes
2 arguments: the first one is a position `p`

and the second is the value
at position `p`

in the collection `c`

.

`map_indexed`

is a generic operator that acts over any collection type.
The results is the collection of the results returned by the
application of `f`

. For the representation of a
position of a collection, see the function *collection* and also
the function *leibniz* and *newton*.

**Example** :`map_indexed((\pos, value.pos), (4, 5, 6, 7))`

returns the sequence
of the positions of the elements of the list `4, 5, 6, 7`

. Thus, the
returned value is the sequence `0, 1, 2, 3`

.

**See** : iter_indexed

**See** : fold_indexed

**See** : map

` 'fold_indexed : ``funct -> any -> collection -> any`

Fold a function over the elements of a collection with their position.

`fold_indexed(f, zero, coll)`

is an expression that fold the function
`f`

over the elements of the collection `coll`

. The function `f`

takes
3 arguments: the first one is a position `p`

, the second is the value
at position `p`

in the collection `coll`

and the third is the
accumulator representing the result of the previous applications of
`f`

. The argument `zero`

is the initial value of the
accumulator. It is also the value returned if the collection `coll`

is empty.

`fold_indexed`

is a generic operator that acts over any collection type.
For the representation of a position of a collection, see the
function *collection* and also the function *leibniz* and *newton*.

**See** : fold

**See** : iter_indexed

**See** : map_indexed

` 'forall : ``funct -> collection -> bool`

Universal predicate.
_{n} are the elements of

`'forall(p, c)`

checks if all elements of the collection `c`

satisfy the predicate `p`

. That is, it returns
`p(c1) && p(c2) && ... && p(cn)`

where `c`

`c`

.
If the collection is empty, `true`

is returned.` 'exists : ``funct -> collection -> bool`

Existential predicate.
_{n} are the elements of

`'exists(p, c)`

checks if at least one element of
the collection satisfies the predicate `p`

. That is, it returns
`p(c1) || p(c2) || ... || p(cn)`

where `c`

`c`

.
If the collection is empty, `false`

is returned.` 'count : ``any -> collection -> int`

Counts the number of occurences of an element in a collection.

**Example** :

`'count(1, (2, 3, 1, 1, 5, 7, 1, 8))`

returns `3`

.` 'member : ``any -> collection -> bool`

Membership predicate.

`'member(e, c)`

returns `true`

if the element `e`

appears in the
collection `c`

and `false`

elsewhere.

` 'shape : ``collection -> funct`

Rebuild a collection from a sequence.

**Example** :First we build a GBF:

`'shape(c)`

(where `c`

is a collection) returns a function `f`

that
expect just one argument. This function can be used to reconstruct a
collection with the same *shape* as the collection `c`

but
with other elements. The argument of the function `f`

is a sequence
of elements that replaces the sequence of elements of `c`

. It is
ensured that

`'shape(c)(sequify(c)) == c`

`gbf GG = <X, Y>;;`

`array := iota(4, seq:()) following |X>+|Y>;;`

This GBF is an array made of a diagonal. The printing of this array
gives:
` 0 --- --- ---`

` --- 1 --- ---`

` --- --- 2 ---`

` --- --- --- 3`

The elements in this array are enumerated in some order by the
`sequify`

function: `sequify(array)`

returns
`1, 2, 3, 0`

Now, we can use the `shape`

primitive to replace all the elements by
some others. The following expression permutes the elements using
the `sort`

function:
`array2 := 'shape(array)(sort(compare, sequify(array)))`

The printing of `array2`

gives:
` 3 --- --- ---`

`--- 0 --- ---`

`--- --- 1 ---`

`--- --- --- 2`

and the sequification of `array2`

corresponds to the sequence
`0, 1, 2, 3`

` 'neighbors : ``collection -> any -> seq`

The neighbors of an element in a collection.

`'neighbors(c, p)`

returns, in a sequence, the neighbors of the
element at position `p`

in the collection `c`

.
Cf. the entry `'collection`

for the representation of the positions
associated to a collection type.

**See** : 'collection

**See** : 'leibniz

**See** : 'monoidal

` 'neighborspos : ``collection -> any -> seq`

The neighbors position of an element in a collection.

`'neighborspos(c, p)`

returns, in a sequence, the neighbors position of the
element at position `p`

in the collection `c`

.
Cf. the entry `'collection`

for the representation of the positions
associated to a collection type.

**See** : 'collection

**See** : 'leibniz

**See** : 'monoidal

` 'neighbor : ``gbf -> seq -> seq`

`gbf -> posgbf -> any `

`chain -> splx -> bool `

`chain -> splx -> int `

Specific neighbors in a GBF or a chain.

*If* the first argument is a GBF, then `'neighbor(c, p, d)`

returns
the value of the neighbor following direction `d`

of the element at
position `p`

in the GBF `c`

. Both `p`

and `d`

are `posgbf`

.

`'neighbor(c, p, l)`

where `l`

is a sequence of directions, returns
the neighbors following the directions in the list `l`

of the
element at position `p`

in the GBF `c`

.

*If* the first argument is a chain, then `'neighbor(c, s, b)`

returns the value of the simplices that are the faces (if the
boolean `b`

is false) or the cofaces (if `b`

is true) of
`s`

in the chain `c`

. Similarly, `'neighbor(c, s, n)`

where `n`

is
an integer, computes `'neighbor(c, s, (n > 0))`

.

**See** : chapter GBF

**See** : chapter Chain