Add `sample` function to List module, add `log` and `exp` functions to Float module (#772)

3 files changed, 145 insertions, 0 deletions

diff --git a/src/gleam/float.gleam b/src/gleam/float.gleam
index b313632..34dba05 100644
--- a/src/gleam/float.gleam
+++ b/src/gleam/float.gleam
@@ -572,3 +572,68 @@ pub fn multiply(a: Float, b: Float) -> Float {
 pub fn subtract(a: Float, b: Float) -> Float {
   a -. b
 }
+
+/// Returns the natural logarithm (base e) of the given as a `Result`. If the
+/// input is less than or equal to 0, returns `Error(Nil)`.
+///
+/// ## Examples
+///
+/// ```gleam
+/// logarithm(1.0)
+/// // -> Ok(0.0)
+/// ```
+///
+/// ```gleam
+/// logarithm(2.718281828459045)  // e
+/// // -> Ok(1.0)
+/// ```
+///
+/// ```gleam
+/// logarithm(0.0)
+/// // -> Error(Nil)
+/// ```
+///
+/// ```gleam
+/// logarithm(-1.0)
+/// // -> Error(Nil)
+/// ```
+///
+pub fn logarithm(x: Float) -> Result(Float, Nil) {
+  // In the following check:
+  // 1. If x is negative then return an error as the natural logarithm
+  //    of a negative number is undefined (would be a complex number)
+  // 2. If x is 0 then return an error as the natural logarithm of 0
+  //    approaches negative infinity
+  case x <=. 0.0 {
+    True -> Error(Nil)
+    False -> Ok(do_log(x))
+  }
+}
+
+@external(erlang, "math", "log")
+@external(javascript, "../gleam_stdlib.mjs", "log")
+fn do_log(x: Float) -> Float
+
+/// Returns e (Euler's number) raised to the power of the given exponent, as
+/// a `Float`.
+///
+/// ## Examples
+///
+/// ```gleam
+/// exponential(0.0)
+/// // -> Ok(1.0)
+/// ```
+///
+/// ```gleam
+/// exponential(1.0)
+/// // -> Ok(2.718281828459045)
+/// ```
+///
+/// ```gleam
+/// exponential(-1.0)
+/// // -> Ok(0.36787944117144233)
+/// ```
+///
+@external(erlang, "math", "exp")
+@external(javascript, "../gleam_stdlib.mjs", "exp")
+pub fn exponential(x: Float) -> Float
diff --git a/src/gleam/list.gleam b/src/gleam/list.gleam
index 6c41df0..c4211f8 100644
--- a/src/gleam/list.gleam
+++ b/src/gleam/list.gleam
@@ -2337,3 +2337,70 @@ pub fn max(
     }
   })
 }
+
+/// Take a random sample of k elements from a list using reservoir sampling via
+/// Algo L. Returns an empty list if the sample size is less than or equal to 0.
+///
+/// Order is not random, only selection is.
+///
+/// ## Examples
+///
+/// ```gleam
+/// reservoir_sample([1, 2, 3, 4, 5], 3)
+/// // -> [2, 4, 5]  // A random sample of 3 items
+/// ```
+///
+pub fn sample(list: List(a), k: Int) -> List(a) {
+  case k <= 0 {
+    True -> []
+    False -> {
+      let #(reservoir, list) = split(list, k)
+
+      case length(reservoir) < k {
+        True -> reservoir
+        False -> {
+          let reservoir =
+            reservoir
+            |> map2(range(0, k - 1), _, fn(a, b) { #(a, b) })
+            |> dict.from_list
+
+          let w = float.exponential(log_random() /. int.to_float(k))
+
+          sample_loop(list, reservoir, k, k, w) |> dict.values
+        }
+      }
+    }
+  }
+}
+
+fn sample_loop(
+  list,
+  reservoir: Dict(Int, a),
+  k,
+  index: Int,
+  w: Float,
+) -> Dict(Int, a) {
+  let skip = {
+    let assert Ok(log_result) = float.logarithm(1.0 -. w)
+
+    log_random() /. log_result |> float.floor |> float.round
+  }
+
+  let index = index + skip + 1
+
+  case drop(list, skip) {
+    [] -> reservoir
+    [elem, ..rest] -> {
+      let reservoir = int.random(k) |> dict.insert(reservoir, _, elem)
+      let w = w *. float.exponential(log_random() /. int.to_float(k))
+
+      sample_loop(rest, reservoir, k, index, w)
+    }
+  }
+}
+
+fn log_random() -> Float {
+  let min_positive = 2.2250738585072014e-308
+  let assert Ok(random) = float.logarithm(float.random() +. min_positive)
+  random
+}
diff --git a/src/gleam_stdlib.mjs b/src/gleam_stdlib.mjs
index 4f804f7..339963b 100644
--- a/src/gleam_stdlib.mjs
+++ b/src/gleam_stdlib.mjs
@@ -1010,3 +1010,16 @@ export function bit_array_starts_with(bits, prefix) {
 
   return true;
 }
+
+export function log(x) {
+  // It is checked in Gleam that:
+  // - The input is strictly positive (x > 0)
+  // - This ensures that Math.log will never return NaN or -Infinity
+  // The function can thus safely pass the input to Math.log
+  // and a valid finite float will always be produced.
+  return Math.log(x);
+}
+
+export function exp(x) {
+  return Math.exp(x);
+}