TrieSet

Sets are partial maps from element type to unit type, i.e., the partial map represents the set with its domain.

:::warning Limitations

This data structure allows at most MAX_LEAF_SIZE = 8 hash collisions. Attempts to insert more than 8 elements with the same hash value—either directly via put or indirectly via other operations—will trap. This limitation is inherited from the underlying Trie data structure. :::

type Hash = Hash.Hash

type Set<T> = Trie.Trie<T, ()>

public func empty<T>() : Set<T>

Empty set.

public func put<T>(
  s : Set<T>,
  x : T,
  xh : Hash,
  eq : (T, T) -> Bool
) : Set<T>

Put an element into the set.

public func delete<T>(
  s : Set<T>,
  x : T,
  xh : Hash,
  eq : (T, T) -> Bool
) : Set<T>

Delete an element from the set.

public func equal<T>(
  s1 : Set<T>,
  s2 : Set<T>,
  eq : (T, T) -> Bool
) : Bool

Test if two sets are equal.

public func size<T>(s : Set<T>) : Nat

The number of set elements, set's cardinality.

public func isEmpty<T>(s : Set<T>) : Bool

Test if s is the empty set.

public func isSubset<T>(
  s1 : Set<T>,
  s2 : Set<T>,
  eq : (T, T) -> Bool
) : Bool

Test if s1 is a subset of s2.

public func mem<T>(
  s : Set<T>,
  x : T,
  xh : Hash,
  eq : (T, T) -> Bool
) : Bool

:::warning Deprecated function Use TrieSet.contains() instead. :::

Test if a set contains a given element.

public func contains<T>(
  s : Set<T>,
  x : T,
  xh : Hash,
  eq : (T, T) -> Bool
) : Bool

Test if a set contains a given element.

public func union<T>(
  s1 : Set<T>,
  s2 : Set<T>,
  eq : (T, T) -> Bool
) : Set<T>

Set union.

public func diff<T>(
  s1 : Set<T>,
  s2 : Set<T>,
  eq : (T, T) -> Bool
) : Set<T>

Set difference.

public func intersect<T>(
  s1 : Set<T>,
  s2 : Set<T>,
  eq : (T, T) -> Bool
) : Set<T>

Set intersection.

public func fromArray<T>(
  arr : [T],
  elemHash : T -> Hash,
  eq : (T, T) -> Bool
) : Set<T>

Construct a set from an array.

public func toArray<T>(s : Set<T>) : [T]

Returns the set as an array.