id | title | description | category |
---|---|---|---|
sets |
Sets |
The standard library's Set module
|
Data Structures |
Set
provides the functor Set.Make
. You must start by passing Set.Make
a module. It specifies the element type for your set. In return, you get another module with those elements' set operations.
Disclaimer: The examples in this tutorial require OCaml 5.1. If you're running a previous version of OCaml , you can either use elements
instead of to_list
, which is a new function in OCaml 5.1, or upgrade OCaml by running opam update
, then opam upgrade ocaml
. Check your current version with ocaml --version
.
If you need to work with string sets, you must invoke Set.Make(String)
. That returns a new module.
# module StringSet = Set.Make(String);;
module StringSet :
sig
type elt = string
type t = Set.Make(String).t
val empty : t
val add : elt -> t -> t
val singleton : elt -> t
val remove : elt -> t -> t
val union : t -> t -> t
val inter : t -> t -> t
...
end
After naming the newly-created module StringSet
, OCaml's toplevel displays the module's signature. Since it contains a large number of functions, the output copied here is shortened for brevity (...
).
This module also defines two types:
type elt = string
for the elements, andtype t = Set.Make(String).t
for the sets.
- We can create an empty set using
StringSet.empty
:
# StringSet.empty ;;
- : StringSet.t = <abstr>
# StringSet.empty |> StringSet.to_list;;
- : string list = []
For StringSet.empty
, you can see that the OCaml toplevel displays the placeholder <abstr>
instead of the actual value. However, converting the string set to a list using StringSet.to_list
results in an empty list.
(Remember, for OCaml versions before 5.1, it will be StringeSet.empty |> StringSet.elements;;
)
- A set with a single element is created using
StringSet.singleton
:
# StringSet.singleton "hello";;
- : StringSet.t = <abstr>
# StringSet.(singleton "hello" |> to_list);;
- : string list = ["hello"]
- Converting a list into a set using
StringSet.of_list
:
# StringSet.of_list ["hello"; "hi"];;
- : StringSet.t = <abstr>
# StringSet.(of_list ["hello"; "hi"] |> to_list);;
- : string list = ["hello"; "hi"]
There's another relevant function StringSet.of_seq: string Seq.t -> StringSet.t
that creates a set from a sequence.
Let's look at a few functions for working with sets using these two sets.
# let first_set = ["hello"; "hi"] |> StringSet.of_list;;
- : val first_set : StringSet.t = <abstr>
# let second_set = ["good morning"; "hi"] |> StringSet.of_list;;
- : val second_set : StringSet.t = <abstr>
# StringSet.(first_set |> add "good morning" |> to_list);;
- : string list = ["good morning"; "hello"; "hi"]
The function StringSet.add
with type string -> StringSet.t -> StringSet.t
takes both a string and a string set. It returns a new string set. Sets created with the Set.Make
functor in OCaml are immutable, so every time you add or remove an element from a set, a new set is created. The old value is unchanged.
# StringSet.(first_set |> remove "hello" |> to_list);;
- : string list = ["hi"]
The function StringSet.remove
with type string -> StringSet.t -> StringSet.t
takes both a string and a string set. It returns a new string set without the given string.
# StringSet.(union first_set second_set |> to_list);;
- : string list = ["good morning"; "hello"; "hi"]
With the function StringSet.union
, we can compute the union of two sets.
# StringSet.(inter first_set second_set |> to_list);;
- : string list = ["hi"]
With the function StringSet.inter
, we can compute the intersection of two sets.
# StringSet.(diff first_set second_set |> to_list);;
- : string list = ["hello"]
With the function StringSet.diff
, we can remove the elements of the second set from the first set.
# ["good morning"; "hello"; "hi"]
|> StringSet.of_list
|> StringSet.filter (fun str -> String.length str <= 5)
|> StringSet.to_list;;
- : string list = ["hello"; "hi"]
The function StringSet.filter
of type (string -> bool) -> StringSet.t -> StringSet.t
creates a new set by keeping the elements that satisfy a predicate from an existing set.
# ["good morning"; "hello"; "hi"]
|> StringSet.of_list
|> StringSet.mem "hello";;
- : bool = true
To check if an element is contained in a set, use the StringSet.mem
function.
The Set.Make
functor expects a module with two definitions: a type t
that represents the element type and the function compare
,
whose signature is t -> t -> int
. The
String
module matches that structure, so we could
directly pass String
as an argument to Set.Make
. Incidentally, many
other modules also have that structure, including Int
and Float
,
so they too can be directly passed into Set.Make
to construct a corresponding set module.
The StringSet
module we created uses the built-in compare
function provided by the String
module.
Let's say we want to create a set of strings that performs a case-insensitive
comparison instead of the case-sensitive comparison provided by String.compare
.
We can accomplish this by passing an ad-hoc module to the Set.Make
function:
# module CISS = Set.Make(struct
type t = string
let compare a b = compare (String.lowercase_ascii a) (String.lowercase_ascii b)
end);;
- : sig
type elt = string
type t
val empty : t
val is_empty : t -> bool
val mem : elt -> t -> bool
val add : elt -> t -> t
(...)
We name the resulting module CISS
(short for "Case Insensitive String Set").
You can see that this module has the intended behavior:
# CISS.singleton "hello" |> CISS.add "HELLO" |> CISS.to_list;;
- : string list = ["hello"]
The value "HELLO"
is not added to the set because it is considered equal to the value "hello"
, which is already contained in the set.
You can use any type for elements, as long as you define a meaningful compare
operation.
# type color = Red | Green | Blue;;
type color = Red | Green | Blue
# module SC = Set.Make(struct
type t = color
let compare a b =
match a, b with
| (Red, Red) -> 0
| (Red, Green) -> 1
| (Red, Blue) -> 1
| (Green, Red) -> -1
| (Green, Green) -> 0
| (Green, Blue) -> 1
| (Blue, Red) -> -1
| (Blue, Green) -> -1
| (Blue, Blue) -> 0
end);;
...
We gave an overview of OCaml's Set
module by creating a StringSet
module using the Set.Make
functor. Further, we looked at how to create sets based on a custom comparison function. For more information, refer to Set in the Standard Library documentation.