std.set

Sets, by an order of their elements: a map whose values are nothing. The order is the elements’ Order, found as an instance argument is, always the same one for a set. Import it by a name, import std.set as Set. The set comes first, as a map does: Set.insert s x.

Set

type Set a = OrdMap.OrdMap a Unit

A set: a map of its elements to nothing.

empty

empty : {a : Type} -> Set a

The set of nothing.

insert

insert : {a : Type} -> {{ord : Order a}} -> Set a -> a -> Set a

The set with x in it.

member

member : {a : Type} -> {{ord : Order a}} -> Set a -> a -> Bool

Whether x is in the set.

delete

delete : {a : Type} -> {{ord : Order a}} -> Set a -> a -> Set a

The set without x (as it was, if x was not in it).

toList

toList : {a : Type} -> Set a -> List a

The elements, in order.

fromList

fromList : {a : Type} -> {{ord : Order a}} -> List a -> Set a

The set of a list’s elements.

>>> toList (fromList [3, 1, 3])
Cons 1 (Cons 3 Nil)

keepIf

keepIf : {a : Type} -> {{ord : Order a}} -> Set a -> (a -> Bool) -> Set a

The elements p holds of.

>>> toList (keepIf (fromList [1, 2, 3]) (\x -> x % 2 == 1))
Cons 1 (Cons 3 Nil)

size

size : {a : Type} -> Set a -> Int

How many elements it has.

union

union : {a : Type} -> {{ord : Order a}} -> Set a -> Set a -> Set a

The elements of both.

intersection

intersection : {a : Type} -> {{ord : Order a}} -> Set a -> Set a -> Set a

The elements of a that are in b too.

>>> toList (intersection (fromList [1, 2, 3]) (fromList [2, 3, 4]))
Cons 2 (Cons 3 Nil)

difference

difference : {a : Type} -> {{ord : Order a}} -> Set a -> Set a -> Set a

The elements of a that are not in b.

>>> toList (difference (fromList [1, 2, 3]) (fromList [2, 4]))
Cons 1 (Cons 3 Nil)

isSubset

isSubset : {a : Type} -> {{ord : Order a}} -> Set a -> Set a -> Bool

Whether every element of a is in b.

>>> List.map (\s -> isSubset s (fromList [1, 2, 3])) [fromList [1, 3], empty, fromList [0, 1]]
Cons True (Cons True (Cons False Nil))

null

null : {a : Type} -> Set a -> Bool

Whether it has no elements.

>>> List.map null [empty, fromList [1]]
Cons True (Cons False Nil)

findMin

findMin : {a : Type} -> Set a -> Maybe a

The least element, if there is one.

>>> findMin (fromList [3, 1, 2])
Just 1

findMax

findMax : {a : Type} -> Set a -> Maybe a

The greatest element, if there is one.

>>> findMax (fromList [3, 1, 2])
Just 3

foldl

foldl : {a b : Type} -> (b -> a -> b) -> b -> Set a -> b

The elements, in order, into z.

>>> foldl (\acc x -> acc * 10 + x) 0 (fromList [3, 1, 2])
123