Skip to main content

module Set

rascal-0.34.0

Library functions for sets.

Usage

import Set;

Dependencies

import Exception;
import List;
import util::Math;

Description

The following library functions are defined for sets:

function classify

Classify elements in a set.

map[&K,set[&V]] classify(set[&V] input, &K (&V) getClass)

Examples

We classify animals by their number of legs.

rascal>import Set;
ok

Create a map from animals to number of legs.

rascal>legs = ("bird": 2, "dog": 4, "human": 2, "snake": 0, "spider": 8, "millepede": 1000, "crab": 8, "cat": 4);
map[str, int]: ("snake":0,"spider":8,"human":2,"crab":8,"cat":4,"bird":2,"dog":4,"millepede":1000)

Define function nLegs that returns the number of legs for each animal (or 0 when the animal is unknown):

rascal>int nLegs(str animal){
>>>>>>> return legs[animal] ? 0;
>>>>>>>}
int (str): function(|prompt:///|(0,53,<1,0>,<3,1>))

Now classify a set of animals:

rascal>classify({"bird", "dog", "human", "spider", "millepede", "zebra", "crab", "cat"}, nLegs);
map[int, set[str]]: (
8:{"spider","crab"},
2:{"human","bird"},
4:{"cat","dog"},
1000:{"millepede"},
0:{"zebra"}
)

function group

Group elements in a set given an equivalence function.

set[set[&T]] group(set[&T] input, bool (&T a, &T b) similar)

Examples

We classify animals by their number of legs.

rascal>import Set;
ok

Create a map from animals to number of legs.

rascal>legs = ("bird": 2, "dog": 4, "human": 2, "snake": 0, "spider": 8, "millepede": 1000, "crab": 8, "cat": 4);
map[str, int]: ("snake":0,"spider":8,"human":2,"crab":8,"cat":4,"bird":2,"dog":4,"millepede":1000)

Define function nLegs that returns the number of legs fro each animal (or 0 when the animal is unknown):

rascal>int nLegs(str animal){
>>>>>>> return legs[animal] ? 0;
>>>>>>>}
int (str): function(|prompt:///|(0,53,<1,0>,<3,1>))
rascal>bool similar(str a, str b) = nLegs(a) == nLegs(b);
bool (str, str): function(|prompt:///|(0,50,<1,0>,<1,50>))

Now group a set of animals:

rascal>group({"bird", "dog", "human", "spider", "millepede", "zebra", "crab", "cat"}, similar);
set[set[str]]: {
{"spider"},
{"zebra"},
{"human"},
{"crab"},
{"cat"},
{"bird"},
{"dog"},
{"millepede"}
}

WARNING: check compiler.

function index

Map set elements to a fixed index.

map[&T,int] index(set[&T] s)

Examples

rascal>import Set;
ok
rascal>index({"elephant", "zebra", "snake"});
map[str, int]: ("snake":0,"zebra":1,"elephant":2)

function isEmpty

Test whether a set is empty.

bool isEmpty(set[&T] st)

Yields true if s is empty, and false otherwise.

Examples

rascal>import Set;
ok
rascal>isEmpty({1, 2, 3});
bool: false
rascal>isEmpty({});
bool: true

function mapper

Apply a function to all set elements and return set of results.

set[&U] mapper(set[&T] st, &U (&T) fn)

Return a set obtained by applying function fn to all elements of set s.

Examples

rascal>import Set;
ok
rascal>int incr(int x) { return x + 1; }
int (int): function(|prompt:///|(0,33,<1,0>,<1,33>))
rascal>mapper({1, 2, 3, 4}, incr);
set[int]: {5,3,2,4}

function max

Determine the largest element of a set.

&T max(set[&T] st)

Examples

rascal>import Set;
ok
rascal>max({1, 3, 5, 2, 4});
int: 5
rascal>max({"elephant", "zebra", "snake"});
str: "zebra"
---
zebra
---

function min

Smallest element of a set.

Determine the smallest element of a set.

&T min(set[&T] st)

Examples

rascal>import Set;
ok
rascal>min({1, 3, 5, 4, 2});
int: 1

Examples

rascal>import Set;
ok
rascal>min({1, 3, 5, 2, 4});
int: 1
rascal>min({"elephant", "zebra", "snake"});
str: "elephant"
---
elephant
---

function power

Determine the powerset of a set.

set[set[&T]] power(set[&T] st)

Returns a set with all subsets of s.

Examples

rascal>import Set;
ok
rascal>power({1,2,3,4});
set[set[int]]: {
{},
{1,2,4},
{1},
{3,2,4},
{3},
{1,3,2,4},
{1,3},
{2},
{4},
{1,2},
{1,4},
{3,2},
{3,4},
{1,3,2},
{1,3,4},
{2,4}
}

function power1

The powerset (excluding the empty set) of a set value.

set[set[&T]] power1(set[&T] st)

Returns all subsets (excluding the empty set) of s.

Examples

rascal>import Set;
ok
rascal>power1({1,2,3,4});
set[set[int]]: {
{1,2,4},
{1},
{3,2,4},
{3},
{1,3,2,4},
{1,3},
{2},
{4},
{1,2},
{1,4},
{3,2},
{3,4},
{1,3,2},
{1,3,4},
{2,4}
}

function reducer

Apply a function to successive elements of a set and combine the results (deprecated).

&T reducer(set[&T] st, &T (&T,&T) fn, &T unit)

&T reducer(set[&T] _:{})

Apply the function fn to successive elements of set s starting with unit.

Examples

rascal>import Set;
ok
rascal>int add(int x, int y) { return x + y; }
int (int, int): function(|prompt:///|(0,39,<1,0>,<1,39>))
rascal>reducer({10, 20, 30, 40}, add, 0);
int: 100

Pitfalls

danger

This function is deprecated, use a reducer expression instead, such as (init | fn(it,e) | e <- st).

function size

Determine the number of elements in a set.

int size(set[&T] st)

Examples

rascal>import Set;
ok
rascal>size({1,2,3,4});
int: 4
rascal>size({"elephant", "zebra", "snake"});
int: 3
rascal>size({});
int: 0

function sum

(&T <:num) sum(set[(&T <:num)] _:{})

function sum

Sum the elements of a set.

default (&T <:num) sum({(&T <: num) e, *(&T <: num) r})

Examples

rascal>import Set;
ok
rascal>sum({3, 1, 4, 5});
int: 13
rascal>sum({3, 1.5, 4, 5});
num: 13.5

function getOneFrom

Pick an arbitrary element from a set.

&T getOneFrom(set[&T] st)

Examples

rascal>import Set;
ok
rascal>getOneFrom({"elephant", "zebra", "snake"});
str: "zebra"
---
zebra
---
rascal>getOneFrom({"elephant", "zebra", "snake"});
str: "zebra"
---
zebra
---
rascal>getOneFrom({"elephant", "zebra", "snake"});
str: "snake"
---
snake
---
rascal>getOneFrom({"elephant", "zebra", "snake"});
str: "zebra"
---
zebra
---

function getFirstFrom

Get "first" element from a set.

&T getFirstFrom(set[&T] st)

Get "first" element of a set. Of course, sets are unordered and do not have a first element. However, we may assume that sets are internally ordered in some way and this ordering is reproducible. Applying getFirstFrom on the same set will always returns the same element.

Benefits

This function helps to make set-based code more deterministic, for instance, for testing purposes.

function takeOneFrom

Remove an arbitrary element from a set, returns the element and a set without that element.

tuple[&T, set[&T]] takeOneFrom(set[&T] st)

Remove an arbitrary element from set s and return a tuple consisting of the element and a set without that element. Also see GetOneFrom.

Examples

rascal>import Set;
ok
rascal>takeOneFrom({1, 2, 3, 4});
tuple[int,set[int]]: <3,{1,2,4}>
rascal>takeOneFrom({1, 2, 3, 4});
tuple[int,set[int]]: <4,{1,3,2}>
rascal>takeOneFrom({1, 2, 3, 4});
tuple[int,set[int]]: <2,{1,3,4}>

function takeFirstFrom

Remove "first" element from a set, returns the element and a set without that element.

tuple[&T, set[&T]] takeFirstFrom({&T f, *&T r})

tuple[&T, set[&T]] takeFirstFrom(set[&T] _:{})

element of a set.

function toList

Convert a set to a list.

list[&T] toList(set[&T] st)

Examples

rascal>import Set;
ok
rascal>toList({1, 2, 3, 4});
list[int]: [1,3,2,4]
rascal>toList({"elephant", "zebra", "snake"});
list[str]: ["snake","zebra","elephant"]

Note that the same result can be obtained using splicing:

rascal>s = {1,2,3,4};
set[int]: {1,3,2,4}
rascal>l = [*s];
list[int]: [1,3,2,4]

Pitfalls

Recall that the elements of a set are unordered and that there is no guarantee in which order the set elements will be placed in the resulting list.

function toMap

Convert a set of tuples to a map; each key is associated with a set of values.

map[&A,set[&B]] toMap(rel[&A, &B] st)

Convert a set of tuples to a map in which the first element of each tuple is associated with the set of second elements of all tuples with the same first element.

Examples

rascal>import Set;
ok
rascal>toMap({<"a", 1>, <"b", 2>, <"a", 10>});
map[str, set[int]]: (
"a":{10,1},
"b":{2}
)

function toMapUnique

Convert a set of tuples to a map (provided that there are no multiple keys).

map[&A,&B] toMapUnique(rel[&A, &B] st) throws MultipleKey

Convert a set of tuples to a map. The result should be a legal map (i.e., without multiple keys).

Examples

rascal>import Set;
ok
rascal>toMapUnique({<"a", 1>, <"b", 2>, <"c", 10>});
map[str, int]: ("a":1,"b":2,"c":10)

Now explore an erroneous example:

rascal>toMapUnique({<"a", 1>, <"b", 2>, <"a", 10>});
|lib://rascal/org/rascalmpl/library/Set.rsc|(9101,520,<370,0>,<385,70>): MultipleKey("a",10,1)
at *** somewhere ***(|lib://rascal/org/rascalmpl/library/Set.rsc|(9101,520,<370,0>,<385,70>))
at toMapUnique(|prompt:///|(39,2,<1,39>,<1,41>))
ok

function toString

Convert a set to a string.

str toString(set[&T] st)

Examples

rascal>import Set;
ok
rascal>toString({1, 2, 3});
str: "{1,3,2}"
---
{1,3,2}
---
rascal>toString({"elephant", "zebra", "snake"});
str: "{\"snake\",\"zebra\",\"elephant\"}"
---
{"snake","zebra","elephant"}
---

Pitfalls

Recall that the elements of a set are unordered and that there is no guarantee in which order the set elements will be placed in the resulting string.

function itoString

Convert a set to an indented string.

str itoString(set[&T] st)

Examples

rascal>import Set;
ok
rascal>toString({1, 2, 3});
str: "{1,3,2}"
---
{1,3,2}
---
rascal>toString({"elephant", "zebra", "snake"});
str: "{\"snake\",\"zebra\",\"elephant\"}"
---
{"snake","zebra","elephant"}
---

Pitfalls

Recall that the elements of a set are unordered and that there is no guarantee in which order the set elements will be placed in the resulting string.

function sort

Sort the elements of a set.

Sort the elements of a set:

  • Use the built-in ordering on values to compare list elements.
  • Give an additional lessThan function that will be used to compare elements.

This function lessThan (<) function should implement a strict partial order, meaning:

  • that it is not reflexive, i.e. never a < a
  • is anti-symmetric, i.e. never a < b && b < a.
  • is transitive, i.e. if a < b and b < c then a < c.
list[&T] sort(set[&T] s)

list[&T] sort(set[&T] l, bool (&T a, &T b) less)

Examples

rascal>import Set;
ok
rascal>import String;
ok
rascal>sort({10, 4, -2, 11, 100, 5});
list[int]: [-2,4,5,10,11,100]
rascal>fruits = {"mango", "strawberry", "pear", "pineapple", "banana", "grape", "kiwi"};
set[str]: {"mango","banana","pear","pineapple","grape","strawberry","kiwi"}
rascal>sort(fruits);
list[str]: ["banana","grape","kiwi","mango","pear","pineapple","strawberry"]
rascal>sort(fruits, bool(str a, str b){ return size(a) > size(b); });
list[str]: ["strawberry","pineapple","banana","mango","grape","kiwi","pear"]

function top

Produce the smallest k elements of a set as sorted by the less function

list[&T] top(int k, set[&T] l, bool (&T a, &T b) less)

list[&T] top(int k, set[&T] l)

This function is fast if k is relatively small, say 10 out of a 1000 elements. It operates in O(n*k) time where n is the size of the set.

If k is a larger value, say k > 10, then it's perhaps better to just sort the entire set using the asympotically faster (n*log^2(n)) sort function and take the first k elements of the resulting list.

If k is a negative number, top will return the largest abs(k) elements of the set instead of the smallest.

function union

Flatten a set of sets into a single set.

set[&T] union(set[set[&T]] sets)

function jaccard

Compute the Jaccard similarity between two sets.

real jaccard(set[value] x, set[value] y)