Module

Data.Set

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

This module defines a type of sets as balanced 2-3 trees, based on http://www.cs.princeton.edu/~dpw/courses/cos326-12/ass/2-3-trees.pdf

Qualified import is encouraged, so as to avoid name clashes with other modules.

#Set Source

newtype Set a

Set a represents a set of values of type a

Instances

(Eq a) => Eq (Set a)
Eq1 Set
(Show a) => Show (Set a)
(Ord a) => Ord (Set a)
Ord1 Set
(Ord a) => Monoid (Set a)
(Ord a) => Semigroup (Set a)
Foldable Set

#fromFoldable Source

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

Create a set from a foldable structure.

#toUnfoldable Source

toUnfoldable :: forall a f. 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 b a. 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. Set a -> Boolean

Check whether the underlying tree satisfies the 2-3 invariant

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

#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 * log(m))

#unions Source

unions :: forall a f. 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 b a. 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.

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