Skip to main content

TrieSet

Functional set

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

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

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>

Set union.

Function diff

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

Set difference.

Function intersect

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

Set intersection.

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]