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
type Hash = Hash.Hash
Type Set
type Set<T> = Trie.Trie<T, ()>
Function empty
func empty<T>() : Set<T>
Empty set.
Function put
func put<T>(s : Set<T>, x : T, xh : Hash, eq : (T, T) -> Bool) : Set<T>
Put an element into the set.
Function delete
func delete<T>(s : Set<T>, x : T, xh : Hash, eq : (T, T) -> Bool) : Set<T>
Delete an element from the set.
Function equal
func equal<T>(s1 : Set<T>, s2 : Set<T>, eq : (T, T) -> Bool) : Bool
Test if two sets are equal.
Function size
func size<T>(s : Set<T>) : Nat
The number of set elements, set's cardinality.
Function isEmpty
func isEmpty<T>(s : Set<T>) : Bool
Test if s is the empty set.
Function isSubset
func isSubset<T>(s1 : Set<T>, s2 : Set<T>, eq : (T, T) -> Bool) : Bool
Test if s1 is a subset of s2.
Function mem
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.
Function contains
func contains<T>(s : Set<T>, x : T, xh : Hash, eq : (T, T) -> Bool) : Bool
Test if a set contains a given element.
Function union
func union<T>(s1 : Set<T>, s2 : Set<T>, eq : (T, T) -> Bool) : Set<T>
Function diff
func diff<T>(s1 : Set<T>, s2 : Set<T>, eq : (T, T) -> Bool) : Set<T>
Function intersect
func intersect<T>(s1 : Set<T>, s2 : Set<T>, eq : (T, T) -> Bool) : Set<T>
Function fromArray
func fromArray<T>(arr : [T], elemHash : T -> Hash, eq : (T, T) -> Bool) : Set<T>
Function toArray
func toArray<T>(s : Set<T>) : [T]