Repository: rust-itertools/itertools
Pull request #902 (2024-03-14 10:48:21)

Deprecate `GroupingMap::fold_first` for `reduce`
I just became aware of https://github.com/rust-lang/rust/issues/68125 and https://github.com/rust-lang/rust/pull/79805 and the names that were previously considered.

So we have:
- `Itertools::fold1` (deprecated) which basically is `Iterator::reduce`.
- `Itertools::tree_fold1` deprecated/renamed `tree_reduce` in #895 (not merged yet).
- And I now suggest to **deprecate `GroupingMap::fold_first` and rename it `reduce`** (before I finish #901 where I might have wrote a new `fold_first_in` instead of `reduce_in`).

What a _naming mess!_

Hopefully, we might be able to remove all three deprecated methods at the same time and close this page once and for all.


Patch:
diff --git a/Cargo.toml b/Cargo.toml
index d6dc3fa..7fb6a39 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -57,7 +57,7 @@ name = "combinations_with_replacement"
 harness = false
 
 [[bench]]
-name = "tree_fold1"
+name = "tree_reduce"
 harness = false
 
 [[bench]]
diff --git a/benches/tree_fold1.rs b/benches/tree_reduce.rs
similarity index 86%
rename from benches/tree_fold1.rs
rename to benches/tree_reduce.rs
index 5b76d54..051b148 100644
--- a/benches/tree_fold1.rs
+++ b/benches/tree_reduce.rs
@@ -6,7 +6,7 @@ use itertools::{cloned, Itertools};
 trait IterEx: Iterator {
     // Another efficient implementation against which to compare,
     // but needs `std` so is less desirable.
-    fn tree_fold1_vec<F>(self, mut f: F) -> Option<Self::Item>
+    fn tree_reduce_vec<F>(self, mut f: F) -> Option<Self::Item>
     where
         F: FnMut(Self::Item, Self::Item) -> Self::Item,
         Self: Sized,
@@ -91,14 +91,14 @@ def_benchs! {
 
 def_benchs! {
     10_000,
-    tree_fold1,
-    tree_fold1_stack_10k,
+    tree_reduce,
+    tree_reduce_stack_10k,
 }
 
 def_benchs! {
     10_000,
-    tree_fold1_vec,
-    tree_fold1_vec_10k,
+    tree_reduce_vec,
+    tree_reduce_vec_10k,
 }
 
 def_benchs! {
@@ -109,14 +109,14 @@ def_benchs! {
 
 def_benchs! {
     100,
-    tree_fold1,
-    tree_fold1_stack_100,
+    tree_reduce,
+    tree_reduce_stack_100,
 }
 
 def_benchs! {
     100,
-    tree_fold1_vec,
-    tree_fold1_vec_100,
+    tree_reduce_vec,
+    tree_reduce_vec_100,
 }
 
 def_benchs! {
@@ -127,24 +127,24 @@ def_benchs! {
 
 def_benchs! {
     8,
-    tree_fold1,
-    tree_fold1_stack_08,
+    tree_reduce,
+    tree_reduce_stack_08,
 }
 
 def_benchs! {
     8,
-    tree_fold1_vec,
-    tree_fold1_vec_08,
+    tree_reduce_vec,
+    tree_reduce_vec_08,
 }
 
 criterion_main!(
     fold1_10k,
-    tree_fold1_stack_10k,
-    tree_fold1_vec_10k,
+    tree_reduce_stack_10k,
+    tree_reduce_vec_10k,
     fold1_100,
-    tree_fold1_stack_100,
-    tree_fold1_vec_100,
+    tree_reduce_stack_100,
+    tree_reduce_vec_100,
     fold1_08,
-    tree_fold1_stack_08,
-    tree_fold1_vec_08,
+    tree_reduce_stack_08,
+    tree_reduce_vec_08,
 );
diff --git a/src/grouping_map.rs b/src/grouping_map.rs
index 47a7c09..f910e5f 100644
--- a/src/grouping_map.rs
+++ b/src/grouping_map.rs
@@ -220,14 +220,14 @@ where
     ///
     /// let lookup = (1..=7)
     ///     .into_grouping_map_by(|&n| n % 3)
-    ///     .fold_first(|acc, _key, val| acc + val);
+    ///     .reduce(|acc, _key, val| acc + val);
     ///
     /// assert_eq!(lookup[&0], 3 + 6);
     /// assert_eq!(lookup[&1], 1 + 4 + 7);
     /// assert_eq!(lookup[&2], 2 + 5);
     /// assert_eq!(lookup.len(), 3);
     /// ```
-    pub fn fold_first<FO>(self, mut operation: FO) -> HashMap<K, V>
+    pub fn reduce<FO>(self, mut operation: FO) -> HashMap<K, V>
     where
         FO: FnMut(V, &K, V) -> V,
     {
@@ -239,6 +239,15 @@ where
         })
     }
 
+    /// See [`.reduce()`](GroupingMap::reduce).
+    #[deprecated(note = "Use .reduce() instead", since = "0.13.0")]
+    pub fn fold_first<FO>(self, operation: FO) -> HashMap<K, V>
+    where
+        FO: FnMut(V, &K, V) -> V,
+    {
+        self.reduce(operation)
+    }
+
     /// Groups elements from the `GroupingMap` source by key and collects the elements of each group in
     /// an instance of `C`. The iteration order is preserved when inserting elements.
     ///
@@ -321,7 +330,7 @@ where
     where
         F: FnMut(&K, &V, &V) -> Ordering,
     {
-        self.fold_first(|acc, key, val| match compare(key, &acc, &val) {
+        self.reduce(|acc, key, val| match compare(key, &acc, &val) {
             Ordering::Less | Ordering::Equal => val,
             Ordering::Greater => acc,
         })
@@ -402,7 +411,7 @@ where
     where
         F: FnMut(&K, &V, &V) -> Ordering,
     {
-        self.fold_first(|acc, key, val| match compare(key, &acc, &val) {
+        self.reduce(|acc, key, val| match compare(key, &acc, &val) {
             Ordering::Less | Ordering::Equal => acc,
             Ordering::Greater => val,
         })
@@ -553,7 +562,7 @@ where
 
     /// Groups elements from the `GroupingMap` source by key and sums them.
     ///
-    /// This is just a shorthand for `self.fold_first(|acc, _, val| acc + val)`.
+    /// This is just a shorthand for `self.reduce(|acc, _, val| acc + val)`.
     /// It is more limited than `Iterator::sum` since it doesn't use the `Sum` trait.
     ///
     /// Returns a `HashMap` associating the key of each group with the sum of that group's elements.
@@ -574,12 +583,12 @@ where
     where
         V: Add<V, Output = V>,
     {
-        self.fold_first(|acc, _, val| acc + val)
+        self.reduce(|acc, _, val| acc + val)
     }
 
     /// Groups elements from the `GroupingMap` source by key and multiply them.
     ///
-    /// This is just a shorthand for `self.fold_first(|acc, _, val| acc * val)`.
+    /// This is just a shorthand for `self.reduce(|acc, _, val| acc * val)`.
     /// It is more limited than `Iterator::product` since it doesn't use the `Product` trait.
     ///
     /// Returns a `HashMap` associating the key of each group with the product of that group's elements.
@@ -600,6 +609,6 @@ where
     where
         V: Mul<V, Output = V>,
     {
-        self.fold_first(|acc, _, val| acc * val)
+        self.reduce(|acc, _, val| acc * val)
     }
 }
diff --git a/src/k_smallest.rs b/src/k_smallest.rs
index 4de1b25..fe699fb 100644
--- a/src/k_smallest.rs
+++ b/src/k_smallest.rs
@@ -2,7 +2,7 @@ use alloc::vec::Vec;
 use core::cmp::Ordering;
 
 /// Consumes a given iterator, returning the minimum elements in **ascending** order.
-pub(crate) fn k_smallest_general<I, F>(mut iter: I, k: usize, mut comparator: F) -> Vec<I::Item>
+pub(crate) fn k_smallest_general<I, F>(iter: I, k: usize, mut comparator: F) -> Vec<I::Item>
 where
     I: Iterator,
     F: FnMut(&I::Item, &I::Item) -> Ordering,
@@ -44,6 +44,7 @@ where
     if k == 0 {
         return Vec::new();
     }
+    let mut iter = iter.fuse();
     let mut storage: Vec<I::Item> = iter.by_ref().take(k).collect();
 
     let mut is_less_than = move |a: &_, b: &_| comparator(a, b) == Ordering::Less;
@@ -55,19 +56,15 @@ where
         sift_down(&mut storage, &mut is_less_than, i);
     }
 
-    if k == storage.len() {
-        // If we fill the storage, there may still be iterator elements left so feed them into the heap.
-        // Also avoids unexpected behaviour with restartable iterators.
-        iter.for_each(|val| {
-            if is_less_than(&val, &storage[0]) {
-                // Treating this as an push-and-pop saves having to write a sift-up implementation.
-                // https://en.wikipedia.org/wiki/Binary_heap#Insert_then_extract
-                storage[0] = val;
-                // We retain the smallest items we've seen so far, but ordered largest first so we can drop the largest efficiently.
-                sift_down(&mut storage, &mut is_less_than, 0);
-            }
-        });
-    }
+    iter.for_each(|val| {
+        if is_less_than(&val, &storage[0]) {
+            // Treating this as an push-and-pop saves having to write a sift-up implementation.
+            // https://en.wikipedia.org/wiki/Binary_heap#Insert_then_extract
+            storage[0] = val;
+            // We retain the smallest items we've seen so far, but ordered largest first so we can drop the largest efficiently.
+            sift_down(&mut storage, &mut is_less_than, 0);
+        }
+    });
 
     // Ultimately the items need to be in least-first, strict order, but the heap is currently largest-first.
     // To achieve this, repeatedly,
diff --git a/src/lib.rs b/src/lib.rs
index 0506a3d..ec374c4 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -2466,7 +2466,7 @@ pub trait Itertools: Iterator {
     /// - if `f` is a trivial operation like `u32::wrapping_add`, prefer the normal
     /// [`Iterator::reduce`] instead since it will most likely result in the generation of simpler
     /// code because the compiler is able to optimize it
-    /// - otherwise if `f` is non-trivial like `format!`, you should use `tree_fold1` since it
+    /// - otherwise if `f` is non-trivial like `format!`, you should use `tree_reduce` since it
     /// reduces the number of operations from `O(n)` to `O(ln(n))`
     ///
     /// Here "non-trivial" means:
@@ -2479,20 +2479,20 @@ pub trait Itertools: Iterator {
     ///
     /// // The same tree as above
     /// let num_strings = (1..8).map(|x| x.to_string());
-    /// assert_eq!(num_strings.tree_fold1(|x, y| format!("f({}, {})", x, y)),
+    /// assert_eq!(num_strings.tree_reduce(|x, y| format!("f({}, {})", x, y)),
     ///     Some(String::from("f(f(f(1, 2), f(3, 4)), f(f(5, 6), 7))")));
     ///
     /// // Like fold1, an empty iterator produces None
-    /// assert_eq!((0..0).tree_fold1(|x, y| x * y), None);
+    /// assert_eq!((0..0).tree_reduce(|x, y| x * y), None);
     ///
-    /// // tree_fold1 matches fold1 for associative operations...
-    /// assert_eq!((0..10).tree_fold1(|x, y| x + y),
+    /// // tree_reduce matches fold1 for associative operations...
+    /// assert_eq!((0..10).tree_reduce(|x, y| x + y),
     ///     (0..10).fold1(|x, y| x + y));
     /// // ...but not for non-associative ones
-    /// assert_ne!((0..10).tree_fold1(|x, y| x - y),
+    /// assert_ne!((0..10).tree_reduce(|x, y| x - y),
     ///     (0..10).fold1(|x, y| x - y));
     /// ```
-    fn tree_fold1<F>(mut self, mut f: F) -> Option<Self::Item>
+    fn tree_reduce<F>(mut self, mut f: F) -> Option<Self::Item>
     where
         F: FnMut(Self::Item, Self::Item) -> Self::Item,
         Self: Sized,
@@ -2505,7 +2505,7 @@ pub trait Itertools: Iterator {
             FF: FnMut(T, T) -> T,
         {
             // This function could be replaced with `it.next().ok_or(None)`,
-            // but half the useful tree_fold1 work is combining adjacent items,
+            // but half the useful tree_reduce work is combining adjacent items,
             // so put that in a form that LLVM is more likely to optimize well.
 
             let a = if let Some(v) = it.next() {
@@ -2555,6 +2555,16 @@ pub trait Itertools: Iterator {
         }
     }
 
+    /// See [`.tree_reduce()`](Itertools::tree_reduce).
+    #[deprecated(note = "Use .tree_reduce() instead", since = "0.13.0")]
+    fn tree_fold1<F>(self, f: F) -> Option<Self::Item>
+    where
+        F: FnMut(Self::Item, Self::Item) -> Self::Item,
+        Self: Sized,
+    {
+        self.tree_reduce(f)
+    }
+
     /// An iterator method that applies a function, producing a single, final value.
     ///
     /// `fold_while()` is basically equivalent to [`Iterator::fold`] but with additional support for
@@ -2949,7 +2959,7 @@ pub trait Itertools: Iterator {
     /// itertools::assert_equal(five_smallest, 0..5);
     /// ```
     #[cfg(feature = "use_alloc")]
-    fn k_smallest(mut self, k: usize) -> VecIntoIter<Self::Item>
+    fn k_smallest(self, k: usize) -> VecIntoIter<Self::Item>
     where
         Self: Sized,
         Self::Item: Ord,
@@ -2963,9 +2973,10 @@ pub trait Itertools: Iterator {
             return Vec::new().into_iter();
         }
 
-        let mut heap = self.by_ref().take(k).collect::<BinaryHeap<_>>();
+        let mut iter = self.fuse();
+        let mut heap: BinaryHeap<_> = iter.by_ref().take(k).collect();
 
-        self.for_each(|i| {
+        iter.for_each(|i| {
             debug_assert_eq!(heap.len(), k);
             // Equivalent to heap.push(min(i, heap.pop())) but more efficient.
             // This should be done with a single `.peek_mut().unwrap()` but


Test patch:
diff --git a/tests/quick.rs b/tests/quick.rs
index 7b163d8..bb08e21 100644
--- a/tests/quick.rs
+++ b/tests/quick.rs
@@ -1334,7 +1334,7 @@ quickcheck! {
 }
 
 quickcheck! {
-    fn tree_fold1_f64(mut a: Vec<f64>) -> TestResult {
+    fn tree_reduce_f64(mut a: Vec<f64>) -> TestResult {
         fn collapse_adjacent<F>(x: Vec<f64>, mut f: F) -> Vec<f64>
             where F: FnMut(f64, f64) -> f64
         {
@@ -1353,7 +1353,7 @@ quickcheck! {
             return TestResult::discard();
         }
 
-        let actual = a.iter().cloned().tree_fold1(f64::atan2);
+        let actual = a.iter().cloned().tree_reduce(f64::atan2);
 
         while a.len() > 1 {
             a = collapse_adjacent(a, f64::atan2);
@@ -1495,16 +1495,16 @@ quickcheck! {
         }
     }
 
-    fn correct_grouping_map_by_fold_first_modulo_key(a: Vec<u8>, modulo: u8) -> () {
+    fn correct_grouping_map_by_reduce_modulo_key(a: Vec<u8>, modulo: u8) -> () {
         let modulo = if modulo == 0 { 1 } else { modulo } as u64; // Avoid `% 0`
         let lookup = a.iter().map(|&b| b as u64) // Avoid overflows
             .into_grouping_map_by(|i| i % modulo)
-            .fold_first(|acc, &key, val| {
+            .reduce(|acc, &key, val| {
                 assert!(val % modulo == key);
                 acc + val
             });
 
-        // TODO: Swap `fold1` with stdlib's `fold_first` when it's stabilized
+        // TODO: Swap `fold1` with stdlib's `reduce` when it's stabilized
         let group_map_lookup = a.iter()
             .map(|&b| b as u64)
             .map(|i| (i % modulo, i))
diff --git a/tests/test_core.rs b/tests/test_core.rs
index 448f396..b5826ef 100644
--- a/tests/test_core.rs
+++ b/tests/test_core.rs
@@ -278,9 +278,9 @@ fn part() {
 }
 
 #[test]
-fn tree_fold1() {
+fn tree_reduce() {
     for i in 0..100 {
-        assert_eq!((0..i).tree_fold1(|x, y| x + y), (0..i).fold1(|x, y| x + y));
+        assert_eq!((0..i).tree_reduce(|x, y| x + y), (0..i).fold1(|x, y| x + y));
     }
 }
 
diff --git a/tests/test_std.rs b/tests/test_std.rs
index 5011053..1f319d8 100644
--- a/tests/test_std.rs
+++ b/tests/test_std.rs
@@ -1434,7 +1434,7 @@ fn fold_while() {
 }
 
 #[test]
-fn tree_fold1() {
+fn tree_reduce() {
     let x = [
         "",
         "0",
@@ -1461,7 +1461,7 @@ fn tree_fold1() {
             Some(s.to_string())
         };
         let num_strings = (0..i).map(|x| x.to_string());
-        let actual = num_strings.tree_fold1(|a, b| format!("{} {} x", a, b));
+        let actual = num_strings.tree_reduce(|a, b| format!("{} {} x", a, b));
         assert_eq!(actual, expected);
     }
 }