Module

Data.Set

Package
purescript-ordered-collections
Repository
purescript/purescript-ordered-collections

This module defines a type of sets as height-balanced (AVL) binary trees. Efficient set operations are implemented in terms of https://www.cs.cmu.edu/~guyb/papers/BFS16.pdf

#Set Source

newtype Set a

Set a represents a set of values of type a

Instances

#fromFoldable Source

fromFoldable :: forall f a. Foldable f => Ord a => f a -> Set a

Create a set from a foldable structure.

#toUnfoldable Source

toUnfoldable :: forall f a. Unfoldable f => Set a -> f a

Convert a set to an unfoldable structure.

#empty Source

empty :: forall a. Set a

An empty set

#isEmpty Source

isEmpty :: forall a. Set a -> Boolean

Test if a set is empty

#singleton Source

singleton :: forall a. a -> Set a

Create a set with one element

#map Source

map :: forall a b. Ord b => (a -> b) -> Set a -> Set b

Maps over the values in a set.

This operation is not structure-preserving for sets, so is not a valid Functor. An example case: mapping const x over a set with n > 0 elements will result in a set with one element.

#checkValid Source

checkValid :: forall a. Ord a => Set a -> Boolean

Check whether the underlying tree satisfies the height, size, and ordering invariants.

This function is provided for internal use.

#insert Source

insert :: forall a. Ord a => a -> Set a -> Set a

Insert a value into a set

#member Source

member :: forall a. Ord a => a -> Set a -> Boolean

Test if a value is a member of a set

#delete Source

delete :: forall a. Ord a => a -> Set a -> Set a

Delete a value from a set

#toggle Source

toggle :: forall a. Ord a => a -> Set a -> Set a

Insert a value into a set if it is not already present, if it is present, delete it.

#size Source

size :: forall a. Set a -> Int

Find the size of a set

#findMin Source

findMin :: forall a. Set a -> Maybe a

#findMax Source

findMax :: forall a. Set a -> Maybe a

#union Source

union :: forall a. Ord a => Set a -> Set a -> Set a

Form the union of two sets

Running time: O(n + m)

#unions Source

unions :: forall f a. Foldable f => Ord a => f (Set a) -> Set a

Form the union of a collection of sets

#difference Source

difference :: forall a. Ord a => Set a -> Set a -> Set a

Form the set difference

#subset Source

subset :: forall a. Ord a => Set a -> Set a -> Boolean

True if and only if every element in the first set is an element of the second set

#properSubset Source

properSubset :: forall a. Ord a => Set a -> Set a -> Boolean

True if and only if the first set is a subset of the second set and the sets are not equal

#intersection Source

intersection :: forall a. Ord a => Set a -> Set a -> Set a

The set of elements which are in both the first and second set

#filter Source

filter :: forall a. Ord a => (a -> Boolean) -> Set a -> Set a

Filter out those values of a set for which a predicate on the value fails to hold.

#mapMaybe Source

mapMaybe :: forall a b. Ord b => (a -> Maybe b) -> Set a -> Set b

Applies a function to each value in a set, discarding entries where the function returns Nothing.

#catMaybes Source

catMaybes :: forall a. Ord a => Set (Maybe a) -> Set a

Filter a set of optional values, discarding values that contain Nothing

#toMap Source

toMap :: forall a. Set a -> Map a Unit

A set is a map with no value attached to each key.

#fromMap Source

fromMap :: forall a. Map a Unit -> Set a

A map with no value attached to each key is a set. See also Data.Map.keys.

Modules
Data.Map
Data.Map.Gen
Data.Map.Internal
Data.Set
Data.Set.NonEmpty