# Module Collections

`module Collections: `sig  end``
Generic functions acting on collections.

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.
Given a collection `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 different color. As for any other type, `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``
Set type and predicate.
See : 'set
See : 'seq
See : 'monoidal
` 'seq : `any -> bool``
Seq type and predicate.
See : 'set
See : 'bag
See : 'monoidal
` '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``
Set type and predicate.
See : 'set
See : 'seq
See : 'monoidal
` '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. `monoidal` is the name of an abstract type: it does not exist a value that have precisely this type. `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. `leibniz` is the name of an abstract type: it does not exist a value that have precisely this type. `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:

• `<undef>` values in the collection: A leibnizian collection cannot have `<undef>` elements. For instance, the expression
``1, <undef>, 2, <undef>, 3``
build the sequence `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
``... => <undef>``
in a transformation is interpreted as:
• 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>`.
For example, the rule `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>`.

See : 'newton
See : 'collection
` 'newton : `any -> bool``
Newton type and predicate. `newton` is the name of an abstract type: it does not exist a value that have precisely this type. `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.
See : 'leibniz
See : 'collection
` 'collection : `any -> bool``
Collection type and predicate. `collection` is the name of an abstract type: it does not exist a value that have precisely this type. `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.)
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_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 `<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.
See : tl
See : take
` 'tl : `collection -> collection``
Return the collection minus one element. The result is `<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.
See : tl
See : take
` 'last : `collection -> any``
Return the last element in a sequence. For other collection, an element is returned.
See : hd
` '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.

`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`.
See : iter
See : fold
See : map_indexed
` 'fold : `funct -> any -> collection``
Fold a function over the elements of a collection.

`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`.
See : iter
See : map
See : fold_indexed
` 'iter : `funct -> collection -> undef``
Iter a function over the elements of a collection.

`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`.
See : map
See : fold
See : iter_indexed
` '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. `'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`n are the elements of `c`. If the collection is empty, `true` is returned.
` 'exists : `funct -> collection -> bool``
Existential predicate. `'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`n are the elements of `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.

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

Example :First we build a GBF:
``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