implements the list group function (#400)

3 files changed, 140 insertions, 29 deletions

diff --git a/src/gleam/list.gleam b/src/gleam/list.gleam
index 0fad104..4b5b683 100644
--- a/src/gleam/list.gleam
+++ b/src/gleam/list.gleam
@@ -26,6 +26,7 @@ import gleam/int
 import gleam/float
 import gleam/order.{Order}
 import gleam/pair
+import gleam/map.{Map}
 
 /// An error value returned by the `strict_zip` function.
 ///
@@ -248,6 +249,48 @@ pub fn rest(list: List(a)) -> Result(List(a), Nil) {
   }
 }
 
+fn update_group(
+  f: fn(element) -> key,
+) -> fn(Map(key, List(element)), element) -> Map(key, List(element)) {
+  fn(groups, elem) {
+    case map.get(groups, f(elem)) {
+      Ok(existing) -> map.insert(groups, f(elem), [elem, ..existing])
+      Error(_) -> map.insert(groups, f(elem), [elem])
+    }
+  }
+}
+
+/// Takes a list and groups the values by a key
+/// which is built from a key function.
+///
+/// Does not preserve the initial value order.
+///
+/// ## Examples
+///
+/// ```gleam
+/// > [Ok(3), Error("Wrong"), Ok(200), Ok(73)]
+///   |> group(by: fn(i) {
+///     case i {
+///       Ok(_) -> "Successful"
+///       Error(_) -> "Failed"
+///     }
+///   })
+///   |> map.to_list
+///
+/// [
+///   #("Failed", [Error("Wrong")]),
+///   #("Successful", [Ok(73), Ok(200), Ok(3)])
+/// ]
+///
+/// > group(from: [1,2,3,4,5], with: fn(i) {fn(i) { i - i / 3 * 3 }})
+/// |> map.to_list
+/// [#(0, [3]), #(1, [4, 1]), #(2, [5, 2])]
+/// ```
+///
+pub fn group(list: List(v), by key: fn(v) -> k) -> Map(k, List(v)) {
+  fold(list, map.new(), update_group(key))
+}
+
 fn do_filter(list: List(a), fun: fn(a) -> Bool, acc: List(a)) -> List(a) {
   case list {
     [] -> reverse(acc)
diff --git a/src/gleam/map.gleam b/src/gleam/map.gleam
index 6235dff..a1b7523 100644
--- a/src/gleam/map.gleam
+++ b/src/gleam/map.gleam
@@ -1,10 +1,5 @@
-import gleam/list
 import gleam/option.{Option}
 
-if javascript {
-  import gleam/pair
-}
-
 /// A dictionary of keys and values.
 ///
 /// Any type can be used for the keys and values of a map, but all the keys
@@ -96,8 +91,18 @@ if erlang {
 }
 
 if javascript {
+  fn fold_list_of_pair(
+    over list: List(#(k, v)),
+    from initial: Map(k, v),
+  ) -> Map(k, v) {
+    case list {
+      [] -> initial
+      [x, ..rest] -> fold_list_of_pair(rest, insert(initial, x.0, x.1))
+    }
+  }
+
   fn do_from_list(list: List(#(k, v))) -> Map(k, v) {
-    list.fold(list, new(), insert_pair)
+    fold_list_of_pair(list, new())
   }
 }
 
@@ -260,10 +265,25 @@ if erlang {
 }
 
 if javascript {
+  fn do_reverse_acc(remaining, accumulator) {
+    case remaining {
+      [] -> accumulator
+      [item, ..rest] -> do_reverse_acc(rest, [item, ..accumulator])
+    }
+  }
+
+  fn do_keys_acc(list: List(#(k, v)), acc: List(k)) -> List(k) {
+    case list {
+      [] -> do_reverse_acc(acc, [])
+      [x, ..xs] -> do_keys_acc(xs, [x.0, ..acc])
+    }
+  }
+
   fn do_keys(map: Map(k, v)) -> List(k) {
-    map
-    |> to_list
-    |> list.map(pair.first)
+    let list_of_pairs =
+      map
+      |> to_list
+    do_keys_acc(list_of_pairs, [])
   }
 }
 
@@ -290,10 +310,18 @@ if erlang {
 }
 
 if javascript {
+  fn do_values_acc(list: List(#(k, v)), acc: List(v)) -> List(v) {
+    case list {
+      [] -> do_reverse_acc(acc, [])
+      [x, ..xs] -> do_values_acc(xs, [x.1, ..acc])
+    }
+  }
+
   fn do_values(map: Map(k, v)) -> List(v) {
-    map
-    |> to_list
-    |> list.map(pair.second)
+    let list_of_pairs =
+      map
+      |> to_list
+    do_values_acc(list_of_pairs, [])
   }
 }
 
@@ -369,14 +397,25 @@ if erlang {
 }
 
 if javascript {
-  fn do_take(desired_keys: List(k), map: Map(k, v)) -> Map(k, v) {
+  fn insert_taken(
+    map: Map(k, v),
+    desired_keys: List(k),
+    acc: Map(k, v),
+  ) -> Map(k, v) {
     let insert = fn(taken, key) {
       case get(map, key) {
         Ok(value) -> insert(taken, key, value)
         _ -> taken
       }
     }
-    list.fold(over: desired_keys, from: new(), with: insert)
+    case desired_keys {
+      [] -> acc
+      [x, ..xs] -> insert_taken(map, xs, insert(acc, x))
+    }
+  }
+
+  fn do_take(desired_keys: List(k), map: Map(k, v)) -> Map(k, v) {
+    insert_taken(map, desired_keys, new())
   }
 }
 
@@ -408,10 +447,17 @@ if javascript {
     insert(map, pair.0, pair.1)
   }
 
+  fn fold_inserts(new_entries: List(#(k, v)), map: Map(k, v)) -> Map(k, v) {
+    case new_entries {
+      [] -> map
+      [x, ..xs] -> fold_inserts(xs, insert_pair(map, x))
+    }
+  }
+
   fn do_merge(map: Map(k, v), new_entries: Map(k, v)) -> Map(k, v) {
     new_entries
     |> to_list
-    |> list.fold(map, insert_pair)
+    |> fold_inserts(map)
   }
 }
 
@@ -465,7 +511,10 @@ if javascript {
 /// ```
 ///
 pub fn drop(from map: Map(k, v), drop disallowed_keys: List(k)) -> Map(k, v) {
-  list.fold(over: disallowed_keys, from: map, with: delete)
+  case disallowed_keys {
+    [] -> map
+    [x, ..xs] -> drop(delete(map, x), xs)
+  }
 }
 
 /// Creates a new map with one entry updated using a given function.
diff --git a/src/gleam/option.gleam b/src/gleam/option.gleam
index 2710d78..6015c0f 100644
--- a/src/gleam/option.gleam
+++ b/src/gleam/option.gleam
@@ -1,5 +1,3 @@
-import gleam/list
-
 /// `Option` represents a value that may be present or not. `Some` means the value is
 /// present, `None` means the value is not.
 ///
@@ -11,6 +9,21 @@ pub type Option(a) {
   None
 }
 
+fn do_all(list: List(Option(a)), acc: List(a)) -> Option(List(a)) {
+  case list {
+    [] -> Some(acc)
+    [x, ..rest] -> {
+      let accumulate = fn(acc, item) {
+        case acc, item {
+          Some(values), Some(value) -> Some([value, ..values])
+          _, _ -> None
+        }
+      }
+      accumulate(do_all(rest, acc), x)
+    }
+  }
+}
+
 /// Combines a list of `Option`s into a single `Option`.
 /// If all elements in the list are `Some` then returns a `Some` holding the list of values.
 /// If any element is `None` then returns`None`.
@@ -28,16 +41,7 @@ pub type Option(a) {
 /// ```
 ///
 pub fn all(list: List(Option(a))) -> Option(List(a)) {
-  list.fold_right(
-    list,
-    from: Some([]),
-    with: fn(acc, item) {
-      case acc, item {
-        Some(values), Some(value) -> Some([value, ..values])
-        _, _ -> None
-      }
-    },
-  )
+  do_all(list, [])
 }
 
 /// Checks whether the `Option` is a `Some` value.
@@ -312,6 +316,21 @@ pub fn lazy_or(first: Option(a), second: fn() -> Option(a)) -> Option(a) {
   }
 }
 
+fn do_values(list: List(Option(a)), acc: List(a)) -> List(a) {
+  case list {
+    [] -> acc
+    [x, ..xs] -> {
+      let accumulate = fn(acc, item) {
+        case item {
+          Some(value) -> [value, ..acc]
+          None -> acc
+        }
+      }
+      accumulate(do_values(xs, acc), x)
+    }
+  }
+}
+
 /// Given a list of `Option`s,
 /// returns only the values inside `Some`.
 ///
@@ -323,5 +342,5 @@ pub fn lazy_or(first: Option(a), second: fn() -> Option(a)) -> Option(a) {
 /// ```
 ///
 pub fn values(options: List(Option(a))) -> List(a) {
-  list.filter_map(options, fn(op) { to_result(op, "") })
+  do_values(options, [])
 }