Module PSet


module PSet: Extlib.PSet
Polymorphic sets of elements.

This module defines a type of sets, a functional representation of sets of elements. The base operations are adding an element to a set or removing an element from a set. This implementation is functional insofar as the act of adding or substracting an element to/from a set does not modify the existing set, rather producing a new set. The implementation uses balanced binary trees, and is therefore reasonably efficient: insertion and membership take time logarithmic in the size of the set, for instance.

Note OCaml, Batteries Included, provides two implementations of sets: polymorphic sets (this module) and functorized sets (module Set). Module Set offers a more complex and slightly poorer set of features but stronger type-safety. Module PSet is easier to use and has a few more powerful features but makes it easier to shoot yourself in the foot. In case of doubt, use Set.
Author(s): Xavier Leroy, Nicolas Cannasse, Markus Mottl, David Rajchenbach-Teller


type 'a t 
The type of sets.
include PSet.Enumerable
include PSet.Mappable
val empty : 'a t
The empty set, using compare as comparison function
val create : ('a -> 'a -> int) -> 'a t
Creates a new empty set, using the provided function for key comparison.
val is_empty : 'a t -> bool
Test whether a set is empty or not.
val mem : 'a -> 'a t -> bool
mem x s tests whether x belongs to the set s.
val add : 'a -> 'a t -> 'a t
add x s returns a set containing all elements of s, plus x. If x was already in s, s is returned unchanged.
val remove : 'a -> 'a t -> 'a t
remove x s returns a set containing all elements of s, except x. If x was not in s, s is returned unchanged.
val iter : ('a -> unit) -> 'a t -> unit
iter f s applies f in turn to all elements of s. The elements of s are presented to f in increasing order with respect to the ordering over the type of the elements.
val map : ('a -> 'b) -> 'a t -> 'b t
map f x creates a new set with elements f a0, f a1... f an, where a1, ..., an are the values contained in x
val filter : ('a -> bool) -> 'a t -> 'a t
filter p s returns the set of all elements in s that satisfy predicate p.
val filter_map : ('a -> 'b option) -> 'a t -> 'b t
filter_map f m combines the features of filter and map. It calls calls f a0, f a1, f an where a0..an are the elements of m and returns the set of pairs bi such as f ai = Some bi (when f returns None, the corresponding element of m is discarded).
val fold : ('a -> 'b -> 'b) -> 'a t -> 'b -> 'b
fold f s a computes (f xN ... (f x2 (f x1 a))...), where x1 ... xN are the elements of s, in increasing order.
val exists : ('a -> bool) -> 'a t -> bool
exists p s checks if at least one element of the set satisfies the predicate p.
val cardinal : 'a t -> int
Return the number of elements of a set.
val enum : 'a t -> 'a Enum.t
Return an enumeration of all elements of the given set. The returned enumeration is sorted in increasing order with respect to the ordering of this set.
val of_enum : 'a Enum.t -> 'a t

Boilerplate code


S-Expressions

val t_of_sexp : (Sexplib.Sexp.t -> 'a) -> Sexplib.Sexp.t -> 'a t
val sexp_of_t : ('a -> Sexplib.Sexp.t) -> 'a t -> Sexplib.Sexp.t

Printing

val print : ?first:string ->
?last:string ->
?sep:string ->
('a Extlib.InnerIO.output -> 'b -> unit) ->
'a Extlib.InnerIO.output -> 'b t -> unit