# 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;okrascal>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;okrascal>isEmpty({1, 2, 3});bool: falserascal>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;okrascal>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;okrascal>max({1, 3, 5, 2, 4});int: 5rascal>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;okrascal>min({1, 3, 5, 4, 2});int: 1``

#### Examples​

``rascal>import Set;okrascal>min({1, 3, 5, 2, 4});int: 1rascal>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;okrascal>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;okrascal>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;okrascal>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;okrascal>size({1,2,3,4});int: 4rascal>size({"elephant", "zebra", "snake"});int: 3rascal>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;okrascal>sum({3, 1, 4, 5});int: 13rascal>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;okrascal>getOneFrom({"elephant", "zebra", "snake"});str: "snake"---snake---rascal>getOneFrom({"elephant", "zebra", "snake"});str: "elephant"---elephant---rascal>getOneFrom({"elephant", "zebra", "snake"});str: "elephant"---elephant---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;okrascal>takeOneFrom({1, 2, 3, 4});tuple[int,set[int]]: <3,{1,2,4}>rascal>takeOneFrom({1, 2, 3, 4});tuple[int,set[int]]: <1,{3,2,4}>rascal>takeOneFrom({1, 2, 3, 4});tuple[int,set[int]]: <1,{3,2,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;okrascal>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;okrascal>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;okrascal>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;okrascal>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;okrascal>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;okrascal>import String;okrascal>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)``