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:

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


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:
 '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 cn 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 cn 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