module ListRelation

rascal-Not specified

Library functions for list relations.

Usage

import ListRelation;

Dependencies

import List;

Description

The following library functions are defined for list relations :

• carrier
• carrierR
• carrierX
• complement
• domain
• domainR
• domainX
• groupDomainByRange
• groupRangeByDomain
• ident
• index
• invert
• range
• rangeR
• rangeX

function carrier

Return the list of all elements in any tuple in a list relation.

list[&T]  carrier (lrel[&T,&T] R)

list[&T]  carrier (lrel[&T,&T,&T] R)

list[&T]  carrier (lrel[&T,&T,&T,&T] R)

list[&T]  carrier (lrel[&T,&T,&T,&T,&T] R)

Examples

rascal>import ListRelation;
ok
rascal>carrier([<1,10>, <2,20>]);
list[int]: [1,10,2,20]
rascal>carrier([<1,10,100,1000>, <2,20,200,2000>]);
list[int]: [1,10,100,1000,2,20,200,2000]

function carrierR

A list relation restricted to certain element values in tuples.

lrel[&T,&T] carrierR (lrel[&T,&T] R, set[&T] S)

lrel[&T,&T,&T] carrierR (lrel[&T,&T,&T] R, set[&T] S)

lrel[&T,&T,&T,&T] carrierR (lrel[&T,&T,&T,&T] R, set[&T] S)

lrel[&T,&T,&T,&T,&T] carrierR (lrel[&T,&T,&T,&T,&T] R, set[&T] S)

Returns list relation R restricted to tuples with elements in set S.

Examples

rascal>import ListRelation;
ok
rascal>carrierR([<1,10>, <2,20>, <3,30>], {10, 1, 20});
lrel[int,int]: [<1,10>]

function carrierX

A list relation excluding tuples containing certain values.

lrel[&T,&T] carrierX (lrel[&T,&T] R, set[&T] S)

lrel[&T,&T,&T] carrierX (lrel[&T,&T,&T] R, set[&T] S)

lrel[&T,&T,&T,&T] carrierX (lrel[&T,&T,&T,&T] R, set[&T] S)

lrel[&T,&T,&T,&T,&T] carrierX (lrel[&T,&T,&T,&T,&T] R, set[&T] S)

Returns list relation R excluding tuples with some element in S.

Examples

rascal>import ListRelation;
ok
rascal>carrierX([<1,10>, <2,20>, <3,30>], {10, 1, 20});
lrel[int,int]: [<3,30>]

function complement

Complement of a list relation.

lrel[&T0, &T1] complement(lrel[&T0, &T1] R)

lrel[&T0, &T1, &T2] complement(lrel[&T0, &T1, &T2] R)

lrel[&T0, &T1, &T2, &T3] complement(lrel[&T0, &T1, &T2, &T3] R)

lrel[&T0, &T1, &T2, &T3, &T4] complement(lrel[&T0, &T1, &T2, &T3, &T4] R)

Given a list relation R a new relation U can be constructed that contains all possible tuples with element values that occur at corresponding tuple positions in R. The function complement returns the complement of R relative to U, in other words: U - R.

Examples

rascal>import ListRelation;
ok

Declare R and compute corresponding U:

rascal>R = [<1,10>, <2, 20>, <3, 30>];
lrel[int,int]: [
  <1,10>,
  <2,20>,
  <3,30>
]
rascal>U = domain(R) * range(R);
lrel[int,int]: [
  <1,10>,
  <1,20>,
  <1,30>,
  <2,10>,
  <2,20>,
  <2,30>,
  <3,10>,
  <3,20>,
  <3,30>
]

Here is the complement of R computed in two ways:

rascal>U - R;
lrel[int,int]: [
  <1,20>,
  <1,30>,
  <2,10>,
  <2,30>,
  <3,10>,
  <3,20>
]
rascal>complement([<1,10>, <2, 20>, <3, 30>]);
lrel[int,int]: [
  <1,20>,
  <1,30>,
  <2,10>,
  <2,30>,
  <3,10>,
  <3,20>
]

function domain

Domain of a list relation: a list consisting of the first element of each tuple, uniquely.

list[&T0] domain(lrel[&T0,&T1]             R)

list[&T0] domain(lrel[&T0,&T1,&T2]         R)

list[&T0] domain(lrel[&T0,&T1,&T2,&T3]     R)

list[&T0] domain(lrel[&T0,&T1,&T2,&T3,&T4] R)

The domain can be seen as all possible inputs of the relation image operation. The result contains elements (or tuples) in the order of appearance of the original relation, but all occurrences after the first occurrence of an element have been removed.

Examples

rascal>import ListRelation;
ok
rascal>domain([<1,10>, <2,20>]);
list[int]: [1,2]
rascal>domain([<"mon", 1>, <"tue", 2>]);
list[str]: ["mon","tue"]

function domainR

List relation restricted to certain domain elements.

lrel[&T0,&T1] domainR (lrel[&T0,&T1] R, set[&T0] S)

lrel[&T0,&T1,&T2] domainR (lrel[&T0,&T1,&T2] R, set[&T0] S)

lrel[&T0,&T1,&T2,&T3] domainR (lrel[&T0,&T1,&T2,&T3] R, set[&T0] S)

lrel[&T0,&T1,&T2,&T3,&T4] domainR (lrel[&T0,&T1,&T2,&T3,&T4] R, set[&T0] S)

lrel[&T0,&T1] domainR (lrel[&T0,&T1] R, list[&T0] L)

lrel[&T0,&T1,&T2] domainR (lrel[&T0,&T1,&T2] R, list[&T0] L)

lrel[&T0,&T1,&T2,&T3] domainR (lrel[&T0,&T1,&T2,&T3] R, list[&T0] L)

lrel[&T0,&T1,&T2,&T3,&T4] domainR (lrel[&T0,&T1,&T2,&T3,&T4] R, list[&T0] L)

Restriction of a list relation R to tuples with first element in S.

Examples

rascal>import ListRelation;
ok
rascal>domainR([<1,10>, <2,20>, <3,30>], {3, 1});
lrel[int,int]: [
  <1,10>,
  <3,30>
]

function domainX

List relation excluding certain domain values.

lrel[&T0, &T1] domainX (lrel[&T0, &T1] R, set[&T0] S)

lrel[&T0, &T1, &T2] domainX (lrel[&T0, &T1, &T2] R, set[&T0] S)

lrel[&T0, &T1, &T2, &T3] domainX (lrel[&T0, &T1, &T2, &T3] R, set[&T0] S)

lrel[&T0, &T1, &T2, &T3, &T4] domainX (lrel[&T0, &T1, &T2, &T3, &T4] R, set[&T0] S)

List relation R excluding tuples with first element in S.

Examples

rascal>import ListRelation;
ok
rascal>domainX([<1,10>, <2,20>, <3,30>], {3, 1});
lrel[int,int]: [<2,20>]

function groupDomainByRange

Make sets of elements in the domain that relate to the same element in the range.

list[list[&U]] groupDomainByRange(lrel[&U dom, &T ran] input)

Examples

rascal>import ListRelation;
ok
rascal>legs = [<"bird", 2>, <"dog", 4>, <"human", 2>, <"spider", 8>, <"millipede", 1000>, <"crab", 8>, <"cat", 4>];
lrel[str,int]: [
  <"bird",2>,
  <"dog",4>,
  <"human",2>,
  <"spider",8>,
  <"millipede",1000>,
  <"crab",8>,
  <"cat",4>
]
rascal>groupDomainByRange(legs);
list[list[str]]: [
  ["bird","human"],
  ["dog","cat"],
  ["spider","crab"],
  ["millipede"]
]

function groupRangeByDomain

Make sets of elements in the range that relate to the same element in the domain.

list[list[&T]] groupRangeByDomain(lrel[&U dom, &T ran] input)

rascal>import ListRelation;
ok
rascal>skins = [<"bird", "feather">, <"dog", "fur">, <"tortoise", "shell">, <"human", "skin">, <"fish", "scale">, <"lizard", "scale">, <"crab", "shell">, <"cat", "fur">];
lrel[str,str]: [
  <"bird","feather">,
  <"dog","fur">,
  <"tortoise","shell">,
  <"human","skin">,
  <"fish","scale">,
  <"lizard","scale">,
  <"crab","shell">,
  <"cat","fur">
]
rascal>groupRangeByDomain(skins);
list[list[str]]: [
  ["feather"],
  ["fur"],
  ["shell"],
  ["skin"],
  ["scale"]
]

function ident

The identity list relation.

lrel[&T, &T] ident (list[&T] S)

The identity list relation for set S.

Examples

rascal>import ListRelation;
ok
rascal>ident(["mon", "tue", "wed"]);
lrel[str,str]: [
  <"mon","mon">,
  <"tue","tue">,
  <"wed","wed">
]

function invert

Invert the tuples in a list relation.

lrel[            &T1,&T0] invert (lrel[&T0,&T1            ] R)

lrel[        &T2,&T1,&T0] invert (lrel[&T0,&T1,&T2        ] R)

lrel[    &T3,&T2,&T1,&T0] invert (lrel[&T0,&T1,&T2,&T3    ] R)

lrel[&T4,&T3,&T2,&T1,&T0] invert (lrel[&T0,&T1,&T2,&T3,&T4] R)

Examples

rascal>import ListRelation;
ok
rascal>invert([<1,10>, <2,20>]);
lrel[int,int]: [
  <10,1>,
  <20,2>
]

function range

The range is composed of all but the first element of each tuple of a list relation, uniquely.

list[&T1]             range (lrel[&T0,&T1]             R)

lrel[&T1,&T2]         range (lrel[&T0,&T1, &T2]        R)

lrel[&T1,&T2,&T3]     range (lrel[&T0,&T1,&T2,&T3]     R)

lrel[&T1,&T2,&T3,&T4] range (lrel[&T0,&T1,&T2,&T3,&T4] R)

The range can be seen as all the elements of in all possible images of the relation. The result contains elements (or tuples) in the order of appearance of the original relation, but all occurrences after the first occurrence of an element have been removed.

Examples

rascal>import ListRelation;
ok
rascal>range([<1,10>, <2,20>]);
list[int]: [10,20]
rascal>range([<"mon", 1>, <"tue", 2>]);
list[int]: [1,2]

function rangeR

List relation restricted to certain range values.

lrel[&T0,&T1] rangeR (lrel[&T0,&T1] R, set[&T1] S)

lrel[&T0,&T1] rangeR (lrel[&T0,&T1] R, list[&T1] L)

Restriction of binary list relation R to tuples with second element in set S.

Examples

rascal>import ListRelation;
ok
rascal>rangeR([<1,10>, <2,20>, <3,30>], {30, 10});
lrel[int,int]: [
  <1,10>,
  <3,30>
]

function rangeX

List relation excluding certain range values.

lrel[&T0,&T1] rangeX (lrel[&T0,&T1] R, set[&T1] S)

lrel[&T0,&T1] rangeX (lrel[&T0,&T1] R, list[&T1] S)

Restriction of binary list relation R to tuples with second element not in set S.

Examples

rascal>import ListRelation;
ok
rascal>rangeX([<1,10>, <2,20>, <3,30>], {30, 10});
lrel[int,int]: [<2,20>]

function index

Lists a binary list relation as a map

map[&K, set[&V]] index(lrel[&K, &V] R)

Converts a binary list relation to a map of the domain to a set of the range.

Examples

rascal>import ListRelation;
ok
rascal>index([<1,10>, <2,20>, <3,30>, <30,10>]);
map[int, set[int]]: (
  1:{10},
  3:{30},
  2:{20},
  30:{10}
)