Add reductions()

[nikic]

Unless I missed it, there doesn't seem to currently exist a function to get an iterator of the intermediate values of a reduction function. Here is an example of how this can be used to easily create a cumulative sum iterator:

#[test]
fn test_cumsum() {
    let expected = vec![1, 3, 6, 10, 15];
    let result: Vec<_> = (1..6).reductions(|a,b| a+b).collect();
    assert_eq!(expected, result);
}

For me this use-case up when I needed a cumulative sum over an addition operator without inverse, to optimize sums of certain structure.

Does this seem like something that could be part of this library? (The name "reductions" is not great, as rust uses "fold" instead of "reduce", there's probably some other term for this.)

---

I came up with the following implementation for my own use, though me being new to Rust it likely does everything wrong:

pub struct Reductions<I, R> where I : Iterator {
    iter: I,
    reductor: R,
    prev: Option<I::Item>
}

impl<I, R> Iterator for Reductions<I, R>
        where I: Iterator, I::Item: Clone,
              R: FnMut(I::Item, I::Item) -> I::Item {
    type Item = I::Item;

    fn next(&mut self) -> Option<Self::Item> {
        self.iter.next().map(|item| {
            let value = match self.prev.take() {
                Some(prev) => (self.reductor)(prev, item),
                None => item
            };
            self.prev = Some(value.clone());
            value
        })
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.iter.size_hint()
    }
}

impl<I, R> ExactSizeIterator for Reductions<I, R>
    where I: Iterator, I::Item: Clone,
          R: FnMut(I::Item, I::Item) -> I::Item {}

pub trait IteratorExt : Iterator {
    fn reductions<R>(self, reductor: R) -> Reductions<Self, R>
            where R: FnMut(Self::Item, Self::Item) -> Self::Item,
                  Self: Sized {
        Reductions {
            iter: self,
            reductor: reductor,
            prev: None
        }
    }
}

impl<T> IteratorExt for T where T: Iterator { }

[nikic]

Note that as suggested above I'm using a variant where the first element of the reductions() iterator will match the first element of the original iterator. Closure has another variant which allows you to specify an initial element, so that it will be the first element of the returned iterator instead.

Edit: Python calls this function accumulate, and defaults it to computing the cumsum over the standard addition operator. This name probably fits Rust better than "reductions".

[bluss]

It's similar to scan

[nikic]

@bluss You're right, I have missed that function. This does seem to be easy to implement on top of scan().

Sorry for the noise!

Edit: The ergonomics of scan() are not great if the reduction function has no identity element:

iter.scan(None, |mut st, item| {
    *st = Some(match *st {
        Some(st_inner) => some_function(st_inner, item),
        None => item
     });
     *st
})
// vs
iter.accumulate(some_function)