TrieSet

Functional set

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

LIMITATIONS: This data structure allows at most MAX_LEAF_SIZE=8 hash collisions: attempts to insert more than MAX_LEAF_SIZE elements (whether directly via put or indirectly via other operations) with the same hash value 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

@deprecated: use TrieSet.contains()

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>

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