Module ISet

concat3 l x r combines l, x and r into one balanced set.

All elements of l must be smaller than x and all elements of r greater than x. This precondition is not checked. Violating it builds a tree whose elements are out of order, and every later lookup on that tree may silently give a wrong answer, as the second half of the example shows: the search descends the wrong subtree and never finds the element.

Example:

> import "ISet" as ISet
> ISet.concat3 (ISet.set [1, 2]) 3 (ISet.set [4, 5])
set [1, 2, 3, 4, 5]
> bad = ISet.concat3 (ISet.set [1, 9]) 5 (ISet.set [2, 8])
> bad
set [1, 9, 5, 2, 8]
> ISet.member 9 bad
False

delete s x creates a set with the elements of s except x. The original set is not modified. Deleting an element that is not in the set returns a set with the same elements.

The set comes first and the element last, as in insert.

Example:

> import "ISet" as ISet
> s = ISet.set [1, 2, 3]
> ISet.delete s 2
set [1, 3]
> ISet.delete s 9
set [1, 2, 3]
> s
set [1, 2, 3]

The smallest element of the set together with a set containing the remaining elements. Both are returned as one pair; there is no separate function for just the smallest element.

Fails if the set is empty.

Example:

> import "ISet" as ISet
> ISet.delmin (ISet.set [3, 1, 2])
(1, set [2, 3])

The empty set.

fold f init s folds over the elements of s in ascending order, starting with init. The accumulator is the first argument of f and the element the second.

Unlike the hash-based Set and MSet, this set is ordered, so the traversal order is part of the contract and a fold like the one below can be relied on to produce a sorted result.

Example:

> import "ISet" as ISet
> ISet.fold (\accum x -> accum + [x]) [] (ISet.set [3, 1, 2])
[1, 2, 3]

insert s x creates a set with the elements of s and the element x. The original set is not modified. If x is already in s, the result is s itself.

Note the argument order: the set comes first and the element last, the opposite way round from member.

Example:

> import "ISet" as ISet
> s = ISet.set [1, 2, 3]
> ISet.insert s 4
set [1, 2, 3, 4]
> s
set [1, 2, 3]
> ISet.insert s 2 == s
True

Returns True if the set contains no elements.

member x s returns True if the set s contains the element x.

Note the argument order: the element comes first here, but last in insert, delete, splitL and splitR.

Example:

> import "ISet" as ISet
> s = ISet.set [1, 2, 3]
> ISet.member 2 s
True
> ISet.member 4 s
False

set l creates a set containing the elements of the list l. Duplicates are dropped.

The name gives little away: this is the fromList of this module, and the usual way to build a set from scratch.

Example:

> import "ISet" as ISet
> ISet.set ["b", "a", "b"]
set ["a", "b"]

A set containing just the given element.

The number of elements in the set.

splitL s x returns the elements of s that are strictly smaller than x.

The pivot x is excluded from the result and does not have to be an element of s. Together splitL s x and splitR s x cover all of s except x itself.

Example:

> import "ISet" as ISet
> s = ISet.set [1, 2, 3, 4, 5]
> ISet.splitL s 3
set [1, 2]
> ISet.splitR s 3
set [4, 5]
> ISet.splitL s 10
set [1, 2, 3, 4, 5]

splitR s x returns the elements of s that are strictly greater than x.

The pivot x is excluded from the result and does not have to be an element of s. See splitL for an example of both functions.

The union of the two sets: a new set with the elements of both. Neither argument is modified.

Example:

> import "ISet" as ISet
> ISet.union (ISet.set [1, 2]) (ISet.set [2, 3])
set [1, 2, 3]