Set
Core
A set of unique values. The values can be any comparable type. This includes Int, Float, Char, String, and tuples or lists of comparable types.
Insert, remove, and query operations all take *O(log n)* time.
Types
Set
type Set a = SetRepresents a set of unique values. So Set Int is a set of integers and Set String is a set of strings.
Examples
numbers : Set Int
numbers =
fromList [1, 2, 3]Values
empty
empty : Set aCreate an empty set.
Examples
isEmpty empty == Truesingleton
singleton : a -> Set aCreate a set with one value.
Examples
singleton 42
|> member 42 == Trueinsert
insert : a -> Set a -> Set aInsert a value into a set.
Examples
insert 3 (fromList [1, 2])
|> toList == [1, 2, 3]remove
remove : a -> Set a -> Set aRemove a value from a set. If the value is not found, no changes are made.
Examples
remove 2 (fromList [1, 2, 3])
|> toList == [1, 3]isEmpty
isEmpty : Set a -> BoolDetermine if a set is empty.
Examples
isEmpty empty == True
isEmpty (singleton 1) == Falsemember
member : a -> Set a -> BoolDetermine if a value is in a set.
Examples
member 2 (fromList [1, 2, 3]) == True
member 4 (fromList [1, 2, 3]) == Falsesize
size : Set a -> IntDetermine the number of elements in a set.
Examples
size empty == 0
size (fromList [1, 2, 3]) == 3union
union : Set a -> Set a -> Set aGet the union of two sets. Keep all values.
Examples
union (fromList [1, 2]) (fromList [2, 3])
|> toList == [1, 2, 3]intersect
intersect : Set a -> Set a -> Set aGet the intersection of two sets. Keeps values that appear in both sets.
Examples
intersect (fromList [1, 2]) (fromList [2, 3])
|> toList == [2]diff
diff : Set a -> Set a -> Set aGet the difference between the first set and the second. Keeps values that do not appear in the second set.
Examples
diff (fromList [1, 2, 3]) (fromList [2])
|> toList == [1, 3]toList
toList : Set a -> List aConvert a set into a list, sorted from lowest to highest.
Examples
toList (fromList [3, 1, 2]) == [1, 2, 3]fromList
fromList : List a -> Set aConvert a list into a set, removing any duplicates.
Examples
fromList [1, 1, 2, 3]
|> toList == [1, 2, 3]map
map : (a -> b) -> Set a -> Set bMap a function onto a set, creating a new set with no duplicates.
Examples
map (\n -> n * 2) (fromList [1, 2, 3])
|> toList == [2, 4, 6]foldl
foldl : (a -> b -> b) -> b -> Set a -> bFold over the values in a set, in order from lowest to highest.
Examples
foldl (+) 0 (fromList [1, 2, 3]) == 6foldr
foldr : (a -> b -> b) -> b -> Set a -> bFold over the values in a set, in order from highest to lowest.
Examples
foldr (::) [] (fromList [1, 2, 3]) == [1, 2, 3]filter
filter : (a -> Bool) -> Set a -> Set aOnly keep elements that pass the given test.
Examples
numbers : Set Int
numbers =
fromList [-2, -1, 0, 1, 2]
positives : Set Int
positives =
filter (\x -> x > 0) numbers
-- positives == fromList [1, 2]partition
partition : (a -> Bool) -> Set a -> (Set a, Set a)Create two new sets. The first contains all the elements that passed the given test, and the second contains all the elements that did not.
Examples
partition (\x -> x < 0) (fromList [-1, 0, 1])
|> (\(neg, rest) -> (toList neg, toList rest))
== ([-1], [0, 1])