diff options
| -rw-r--r-- | CHANGELOG.md | 3 | ||||
| -rw-r--r-- | src/gleam/map.gleam | 2 | ||||
| -rw-r--r-- | src/gleam/set.gleam | 57 | ||||
| -rw-r--r-- | test/gleam/set_test.gleam | 6 |
4 files changed, 48 insertions, 20 deletions
diff --git a/CHANGELOG.md b/CHANGELOG.md index e91f104..a6308c1 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -6,7 +6,7 @@ `from_list`, `fold`, `run`, `to_list`, `take`, `drop`, `map`, `filter`, `cycle`, and `range` functions. - Created the `set` module with the `new`, `insert`, `delete`, `to_list`, - `from_list` and `contains` functions. + `from_list`, `fold`, and `contains` functions. - Created the `io` module with the `print`, `println`, and `debug` functions. - Created the `queue` module with the `new`, `from_list`, `to_list`, `is_empty`, `length`, `push_back`, `push_front`, `pop_back`, `pop_front`, @@ -28,6 +28,7 @@ - The `list.contains` label `has` has been changed to `any`. - The `list.sort` label `sort_by` has been changed to `by`. - The `list.fold`'s first argument gained the label `over`. +- The `map.fold`'s first argument gained the label `over`. ## v0.8.0 - 2020-04-28 diff --git a/src/gleam/map.gleam b/src/gleam/map.gleam index 76b6300..e59a042 100644 --- a/src/gleam/map.gleam +++ b/src/gleam/map.gleam @@ -315,7 +315,7 @@ fn do_fold( /// "abc" /// pub fn fold( - map: Map(k, v), + over map: Map(k, v), from initial: acc, with fun: fn(k, v, acc) -> acc, ) -> acc { diff --git a/src/gleam/set.gleam b/src/gleam/set.gleam index 09e92a5..d958919 100644 --- a/src/gleam/set.gleam +++ b/src/gleam/set.gleam @@ -2,24 +2,24 @@ import gleam/map.{Map} import gleam/result import gleam/list -/// A set is a collection of unique elements of the same type. +/// A set is a collection of unique members 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) { +pub opaque type Set(member) { // 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))) + Set(map: Map(member, List(Nil))) } /// Create a new empty set. /// -pub fn new() -> Set(element) { +pub fn new() -> Set(member) { Set(map.new()) } -/// Get the number of elements in a set. +/// Get the number of members in a set. /// /// This function runs in constant time. /// @@ -28,11 +28,11 @@ pub fn new() -> Set(element) { /// > new() |> insert(1) |> insert(2) |> size /// 2 /// -pub fn size(set: Set(element)) -> Int { +pub fn size(set: Set(member)) -> Int { map.size(set.map) } -/// Insert an element into the set. +/// Insert an member into the set. /// /// This function runs in logarithmic time. /// @@ -41,11 +41,11 @@ pub fn size(set: Set(element)) -> Int { /// > 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, [])) +pub fn insert(into set: Set(member), this member: member) -> Set(member) { + Set(map: map.insert(set.map, member, [])) } -/// Check whether a set contains a given element. +/// Check whether a set contains a given member. /// /// This function runs in logarithmic time. /// @@ -57,13 +57,13 @@ pub fn insert(into set: Set(element), this element: element) -> Set(element) { /// > new() |> insert(2) |> contains(1) /// False /// -pub fn contains(in set: Set(element), this member: element) -> Bool { +pub fn contains(in set: Set(member), this member: member) -> Bool { set.map |> map.get(member) |> result.is_ok } -/// Remove an element from a set. If the set does not contain the element then +/// Remove an member from a set. If the set does not contain the member then /// the set is returned unchanged. /// /// This function runs in logarithmic time. @@ -73,11 +73,11 @@ pub fn contains(in set: Set(element), this member: element) -> Bool { /// > new() |> insert(2) |> delete(2) |> contains(1) /// False /// -pub fn delete(from set: Set(element), this member: element) -> Set(element) { +pub fn delete(from set: Set(member), this member: member) -> Set(member) { Set(map: map.delete(set.map, member)) } -/// Convert the set into a list of the contained elements. +/// Convert the set into a list of the contained members. /// /// The list has no specific ordering, any unintentional ordering may change in /// future versions of Gleam or Erlang. @@ -89,11 +89,11 @@ pub fn delete(from set: Set(element), this member: element) -> Set(element) { /// > new() |> insert(2) |> to_list /// [2] /// -pub fn to_list(set: Set(element)) -> List(element) { +pub fn to_list(set: Set(member)) -> List(member) { map.keys(set.map) } -/// Create a new set of the elements in a given list. +/// Create a new set of the members in a given list. /// /// This function runs in loglinear time. /// @@ -103,11 +103,32 @@ pub fn to_list(set: Set(element)) -> List(element) { /// > [1, 1, 2, 4, 3, 2] |> from_list |> to_list |> list.sort /// [1, 3, 3, 4] /// -pub fn from_list(elements: List(element)) -> Set(element) { +pub fn from_list(members: List(member)) -> Set(member) { let map = list.fold( - over: elements, + over: members, from: map.new(), with: fn(k, m) { map.insert(m, k, []) }, ) Set(map) } + +/// Combine all entries into a single value by calling a given function on each +/// one. +/// +/// Sets are not ordered so the values are not returned in any specific order. +/// Do not write code that relies on the order entries are used by this +/// function as it may change in later versions of Gleam or Erlang. +/// +/// # Examples +/// +/// > from_list([1, 3, 9]) +/// > |> fold(0, fn(member, accumulator) { accumulator + member }) +/// 13 +/// +pub fn fold( + over set: Set(member), + from initial: acc, + with reducer: fn(member, acc) -> acc, +) -> acc { + map.fold(over: set.map, from: initial, with: fn(k, _, a) { reducer(k, a) }) +} diff --git a/test/gleam/set_test.gleam b/test/gleam/set_test.gleam index d3bab3e..b0f6ebd 100644 --- a/test/gleam/set_test.gleam +++ b/test/gleam/set_test.gleam @@ -58,3 +58,9 @@ pub fn from_list_test() { |> list.sort(by: int.compare) |> should.equal([1, 3, 3, 4]) } + +pub fn fold_test() { + [1, 3, 9] + |> set.from_list + |> set.fold(from: 0, with: fn(m, a) { m + a }) +} |