Module

Data.Set

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 

newtype Set a

Set a represents a set of values of type a

Instances

#fromFoldable 

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

Create a set from a foldable structure.

#toUnfoldable 

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

Convert a set to an unfoldable structure.

#empty 

empty :: forall a. Set a

An empty set

#isEmpty 

isEmpty :: forall a. Set a -> Boolean

Test if a set is empty

#singleton 

singleton :: forall a. a -> Set a

Create a set with one element

#map 

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 

checkValid :: forall a. Set a -> Boolean

Check whether the underlying tree satisfies the 2-3 invariant

This function is provided for internal use.

#insert 

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

Insert a value into a set

#member 

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

Test if a value is a member of a set

#delete 

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

Delete a value from a set

#size 

size :: forall a. Set a -> Int

Find the size of a set

#findMin 

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

#findMax 

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

#union 

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

Form the union of two sets

Running time: O(n * log(m))

#unions 

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

Form the union of a collection of sets

#difference 

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

Form the set difference

#subset 

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 

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 

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 

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 

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 

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

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

#toMap 

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

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

#fromMap 

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