Set data type

4 files changed, 103 insertions, 6 deletions

diff --git a/CHANGELOG.md b/CHANGELOG.md
index fd6a73a..90221f6 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -2,6 +2,7 @@
 
 ## Unreleased
 
+- Created the `set` module with the `new`, `insert`, and `contains` functions.
 - Created the `io` module with the `print` function.
 - Created the `queue` module with the `new`, `from_list`, `to_list`,
   `is_empty`, `length`, `push_back`, `push_front`, `pop_back`, `pop_front`,
@@ -19,6 +20,7 @@
   `query_to_string` and `to_string`.
 - The `dynamic` module gains the `map`, `opaque_list`, `tuple2`, and `tuple2_of` functions.
 - The `list` module gains the `filter_map` function.
+- The `list.contains` label `has` has been changed to `any`.
 
 ## v0.8.0 - 2020-04-28
 
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
+}
diff --git a/test/gleam/set_test.gleam b/test/gleam/set_test.gleam
new file mode 100644
index 0000000..7247c5c
--- /dev/null
+++ b/test/gleam/set_test.gleam
@@ -0,0 +1,32 @@
+import gleam/should
+import gleam/set
+
+pub fn size_test() {
+  set.new()
+  |> set.size
+  |> should.equal(0)
+
+  set.new()
+  |> set.insert(1)
+  |> set.insert(2)
+  |> set.size
+  |> should.equal(2)
+
+  set.new()
+  |> set.insert(1)
+  |> set.insert(1)
+  |> set.insert(2)
+  |> set.size
+  |> should.equal(2)
+}
+
+pub fn contains_test() {
+  set.new()
+  |> set.insert(1)
+  |> set.contains(this: 1)
+  |> should.be_true
+
+  set.new()
+  |> set.contains(this: 1)
+  |> should.be_false
+}