Как мне скопировать Haskell `scanl (+) 0 xs` в Rust?

Question

Если у меня есть список чисел [1, 2, 3, 4, 5], и я хотел бы создать список кумулятивных сумм, в Haskell я бы сделал следующее:

> let xs = [1, 2, 3, 4, 5]

> scanl (+) 0 xs
[0,1,3,6,10,15]

Попытка получить такое же поведение кажется излишне хлопотной вRust.

let xs = [1, 2, 3, 4, 5];

let vs = vec![0]
    .into_iter()
    .chain(xs.iter().scan(0, |acc, x| {
        *acc += x;
        Some(*acc)
    }))
    .collect::<Vec<_>>();

Неловкое поведение scan необходимости мутировать аккумулятор может быть объяснено отсутствием GC.Но scan также не включает в себя начальное значение аккумулятора, что требует необходимости вручную добавлять 0 вперед.Само по себе это было хлопотно, так как мне нужно было добавить его с chain, а [0].iter() не сработало, равно как и с [0].into_iter() и vec![0].iter().Нужно было vec![0].into_iter().

Я чувствую, что, должно быть, здесь что-то не так.Но что?Есть ли лучший способ получить совокупную сумму?Это обратно в for цикл?

Answer 1

Редактировать:

Несмотря на то, что старая версия этого ответа имитирует поведение промежуточной формы scanl, выполнение не было ленивым. Обновил обобщенную реализацию из моего старого ответа с помощью @ French Boiethios's answer .

Это реализация:

fn scanl<'u, T, F>(op: F, initial: T, list: &'u [T]) -> impl Iterator<Item = T> + 'u
where
    F: Fn(&T, &T) -> T + 'u,
{
    let mut iter = list.iter();
    std::iter::successors(Some(initial), move |acc| iter.next().map(|n| op(n, acc)))
}
//scanl(|x, y| x + y, 0, &[1, 2, 3, 4, 5]).collect::<Vec<_>>()

Детская площадка

---

Это может быть легко реализовано с помощью fold

Для операции Add:

let result = xs.iter().fold(vec![0], |mut acc, val| {
    acc.push(val + acc.last().unwrap());
    acc
});

Детская площадка

---

Вот общая версия:

fn scanl<T, F>(op: F, initial: T, list: &[T]) -> Vec<T>
where
    F: Fn(&T, &T) -> T,
{
    let mut acc = Vec::with_capacity(list.len());
    acc.push(initial);

    list.iter().fold(acc, |mut acc, val| {
        acc.push(op(val, acc.last().unwrap()));
        acc
    })
}
//scanl(|x, y| x + y, 0, &[1, 2, 3, 4, 5])

Детская площадка

Answer 2

Я бы сделал это с successors:

fn main() {
    let mut xs = vec![1, 2, 3, 4, 5].into_iter();
    let vs = std::iter::successors(Some(0), |acc| xs.next().map(|n| n + *acc));

    assert_eq!(vs.collect::<Vec<_>>(), [0, 1, 3, 6, 10, 15]);
}

Answer 3

Неловкое поведение при необходимости мутировать аккумулятор можно объяснить отсутствием ГХ.

Ничто не мешает Rust выполнять то, что вы просите.

Пример возможной реализации:

pub struct Mapscan<I, A, F> {
    accu: Option<A>,
    iter: I,
    f: F,
}

impl<I, A, F> Mapscan<I, A, F> {
    pub fn new(iter: I, accu: Option<A>, f: F) -> Self {
        Self { iter, accu, f }
    }
}

impl<I, A, F> Iterator for Mapscan<I, A, F>
where
    I: Iterator,
    F: FnMut(&A, I::Item) -> Option<A>,
{
    type Item = A;

    fn next(&mut self) -> Option<Self::Item> {
        self.accu.take().map(|accu| {
            self.accu = self.iter.next().and_then(|item| (self.f)(&accu, item));
            accu
        })
    }
}

trait IterPlus: Iterator {
    fn map_scan<A, F>(self, accu: Option<A>, f: F) -> Mapscan<Self, A, F>
    where
        Self: Sized,
        F: FnMut(&A, Self::Item) -> Option<A>,
    {
        Mapscan::new(self, accu, f)
    }
}

impl<T: ?Sized> IterPlus for T where T: Iterator {}

fn main() {
    let xs = [1, 2, 3, 4, 5];

    let vs = xs
        .iter()
        .map_scan(Some(0), |acc, x| Some(acc + x));

    assert_eq!(vs.collect::<Vec<_>>(), [0, 1, 3, 6, 10, 15]);
}