Set data type

2 files changed, 69 insertions, 6 deletions

diff --git a/src/gleam/list.gleam b/src/gleam/list.gleam
index 687eb61..bb35252 100644
--- a/src/gleam/list.gleam
+++ b/src/gleam/list.gleam
@@ -102,22 +102,22 @@ pub fn is_empty(list: List(a)) -> Bool {
 ///
 /// ## Examples
 ///
-///    > contains([], 0)
+///    > [] |> contains(any: 0)
 ///    True
 ///
-///    > contains([0], 0)
+///    > [0] |> contains(any: 0)
 ///    True
 ///
-///    > contains([1], 0)
+///    > [1] |> contains(any: 0)
 ///    False
 ///
-///    > contains([1, 1], 0)
+///    > [1, 1] |> contains(any: 0)
 ///    False
 ///
-///    > contains([1, 0], 0)
+///    > [1, 0] |> contains(any: 0)
 ///    True
 ///
-pub fn contains(list: List(a), has elem: a) -> Bool {
+pub fn contains(list: List(a), any elem: a) -> Bool {
   case list {
     [] -> False
     [head, ..rest] -> head == elem || contains(rest, elem)
diff --git a/src/gleam/set.gleam b/src/gleam/set.gleam
new file mode 100644
index 0000000..cd7cbe0
--- /dev/null
+++ b/src/gleam/set.gleam
@@ -0,0 +1,63 @@
+import gleam/map.{Map}
+import gleam/result
+
+/// A set is a collection of unique elements of the same type.
+///
+/// It is implemented using the `gleam/map` module, so inserts and lookups have
+/// logarithmic time complexity.
+///
+pub opaque type Set(element) {
+  // A list is used as the map value as an empty list has the smallest
+  // representation in Erlang's binary format
+  Set(map: Map(element, List(Nil)))
+}
+
+/// Create a new empty set.
+///
+pub fn new() -> Set(element) {
+  Set(map.new())
+}
+
+/// Get the number of elements in a set.
+///
+/// This function runs in constant time.
+///
+/// ## Examples
+///
+///    > new() |> insert(1) |> insert(2) |> size
+///    2
+///
+pub fn size(set: Set(element)) -> Int {
+  map.size(set.map)
+}
+
+/// Insert an element into the set.
+///
+/// This function runs in logarithmic time.
+///
+/// ## Examples
+///
+///    > new() |> insert(1) |> insert(2) |> size
+///    2
+///
+pub fn insert(into set: Set(element), this element: element) -> Set(element) {
+  Set(map: map.insert(set.map, element, []))
+}
+
+/// Check whether a set contains a given element.
+///
+/// This function runs in logarithmic time.
+///
+/// ## Examples
+///
+///    > new() |> insert(2) |> contains(2)
+///    True
+///
+///    > new() |> insert(2) |> contains(1)
+///    False
+///
+pub fn contains(in set: Set(element), this member: element) -> Bool {
+  set.map
+  |> map.get(member)
+  |> result.is_ok
+}