What is the idiomatic and functional way to iterate over successive fold results?

Question

I have a sequence (list, iterator) a0, a1, a2, ..., and I use a function f to fold. I would like to have a generator which gives me

a0, f(a0, a1), f(f(a0, a1), a2), ...

This is similar to FoldList in Mathematica. Is there a fold_list function available? I couldn't find any.

Answer 1

I'd say the closest abstraction is Iterator::scan. It is a little bit more powerful, as it has an internal mutable state (i.e. can yield a different value for the resulting iterator) and can abort early.

You could use it like this to build an iterator extension trait:

Playground

pub trait FoldListExt: Iterator {
    fn fold_list<'a, St: 'a, F: 'a>(self, initial_state: St, f: F) -> Box<Iterator<Item = St> + 'a>
    where
        St: Clone,
        F: FnMut(St, Self::Item) -> St,
        Self: 'a;
}

impl<I: Iterator> FoldListExt for I {
    fn fold_list<'a, St: 'a, F: 'a>(
        self,
        initial_state: St,
        mut f: F,
    ) -> Box<Iterator<Item = St> + 'a>
    where
        St: Clone,
        F: FnMut(St, Self::Item) -> St,
        Self: 'a,
    {
        Box::new(self.scan(Some(initial_state), move |state, item| {
            let old_state = state.take().unwrap();
            *state = Some(f(old_state.clone(), item));
            Some(old_state)
        }))
    }
}

pub fn main() {
    println!(
        "{:?}",
        (0..16)
            .into_iter()
            .fold_list(0, |a, b| a + b)
            .collect::<Vec<_>>()
    );
}

I used Option<St> for the inner mutable state to avoid another clone() call.

You could use this instead:

Box::new(self.scan(initial_state, move |state, item| {
    let old_state = state.clone();
    *state = f(old_state.clone(), item);
    Some(old_state)
}))