Collections

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

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.

collection -> delaunay

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

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 type and predicate.

Transform its argument into a achain. 'achainify(c) returns the achain of the elements of the collection c.

Set type and predicate.
See : 'set
See : 'seq
See : 'monoidal

Seq type and predicate.
See : 'set
See : 'bag
See : 'monoidal

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 ith character ofs

'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 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 type and predicate.

Set type and predicate.
See : 'set
See : 'seq
See : 'monoidal

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

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

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.

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

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

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

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

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.

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

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

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

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

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

Return the last element in a sequence. For other collection, an element is returned.
See : hd

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

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.

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.

Counts the number of occurences of an element in a collection.
Example :'count(1, (2, 3, 1, 1, 5, 7, 1, 8)) returns 3.

Membership predicate.

'member(e, c) returns true if the element e appears in the collection c and false elsewhere.

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

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

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

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

Module Collections