Documentation

Insert the element if it is present, or delete it otherwise.

>>> toggle 5 $ Set.fromList [1,2,3,6]
fromList [1,2,3,5,6]
>>> toggle 5 $ Set.fromList [1,2,3,5,6]
fromList [1,2,3,6]

Given a monotonic function f that maps a to b, and a value x, split the sequence s depending on the b values. I.e. the result (l,m,r) is such that * all (y -> f y < x) l * all (y -> f y == x) m * all (y -> f y > x) r

running time: \(O(\log n)\)

Given a monotonic function f that orders a, split the sequence s into three parts. I.e. the result (lt,eq,gt) is such that * all (x -> f x == LT) lt * all (x -> f x == EQ) eq * all (x -> f x == GT) gt

running time: \(O(\log n)\)

Constructs a Set using the given Order.

Note that this is dangerous as the resulting set may not abide the ordering expected of such sets.

running time: \(O(n\log n)\)

Given two sets l and r, such that all elements of l occur before r, join the two sets into a combined set.

running time: \(O(\log n)\)

Inserts an element into the set, assuming that the set is ordered by the given order.

>>> insertBy cmpS (S "ccc") $ fromListBy cmpS [S "a" , S "bb" , S "dddd"]
fromList [S "a",S "bb",S "ccc",S "dddd"]

When trying to insert an element that equals an element already in the set (according to the given comparator), this function replaces the old element by the new one:

>>> insertBy cmpS (S "cc") $ fromListBy cmpS [S "a" , S "bb" , S "dddd"]
fromList [S "a",S "cc",S "dddd"]

running time: \(O(\log n)\)

Deletes an element from the set, assuming the set is ordered by the given ordering.

>>> deleteAllBy cmpS (S "bb") $ fromListBy cmpS [S "a" , S "bb" , S "dddd"]
fromList [S "a",S "dddd"]
>>> deleteAllBy cmpS (S "bb") $ fromListBy cmpS [S "a" , S "bb" , S "cc", S "dd", S "ee", S "ff", S "dddd"]
fromList [S "a",S "dddd"]

running time: \(O(\log n)\)

Run a query, eg. lookupGE, on the set with the given ordering.

Note: The binarySearchIn function may be a useful alternative to queryBy

>>> queryBy cmpS Set.lookupGE (S "22") $ fromListBy cmpS [S "a" , S "bbb" , S "ddddddd"]
Just (S "bbb")
>>> queryBy cmpS Set.lookupLE (S "22") $ fromListBy cmpS [S "a" , S "bbb" , S "ddddddd"]
Just (S "a")
>>> queryBy cmpS Set.lookupGE (S "333") $ fromListBy cmpS [S "a" , S "bbb" , S "ddddddd"]
Just (S "bbb")

Flips an element by the given order