Эффективный Rust-коллектор Results Holding Vecs - PullRequest
Новая
       37

Эффективный Rust-коллектор Results Holding Vecs

1 голос
/ 02 мая 2020

Я изучаю Rust, и я натолкнулся на следующий шаблон, который сворачивает итератор Result<Vec<_>, _> s в один большой Vec<_>, терпя неудачу, если какой-либо из результатов итератора потерпел неудачу: 

fn accumulate<T, E>(it: impl Iterator<Item = Result<Vec<T>, E>>) -> Result<Vec<T>, E> {
    let mut result = Vec::new();
    for mut ts in it {
        result.append(&mut ts?)
    }
    Ok(result)
}

Я предполагаю, что можно написать очень короткую версию этой функции в «функциональном стиле», и я изо всех сил пытаюсь ее найти. Морально я хотел бы сделать что-то вроде 

it.map(|v| v?.into_iter()).flatten().collect()

, но это не проверка типа. Запустив небольшие примеры, я думаю, что смысл flatten в том, чтобы молча отбрасывать результаты ошибок, но вместо этого я бы хотел как-то «сопоставить flatten с Result s». Я также знаю, что в общем случае вы не можете собрать, скажем, итератор типа 

impl Iterator<Item = Result<impl Iterator<Item = T>, Error>>

в итератор 

Result<impl Iterator<Item = impl Iterator<Item = T>>, Error>

, так как вам действительно нужно выполнить все вычисления во внешнем итераторе, чтобы узнать конечный результат. Тем не менее, кажется, что вы можете сделать эту работу в этом особом случае, когда вы хотите .flatten(), а затем .collect() сразу после.

Наконец, я вижу, что это collect() дает мне путь построить вектор векторов из it, и тогда я смогу сгладить этот вектор в один большой вектор, который я хочу. Но у этого есть много ненужных выделений памяти.

Может ли стандартная библиотека помочь вам сделать это эффективным, Rust-i c способом?

Ответы [ 2 ]

1 голос
/ 02 мая 2020

Я думаю, я бы начал с try_fold, поскольку он может работать с Result и остановился на Err: 

fn acc2<T, E>(mut it: impl Iterator<Item = Result<Vec<T>, E>>) -> Result<Vec<T>, E> {
    it.try_fold(
        Vec::new(),
        |mut vec, res_ts: Result<Vec<_>, E>| {
            res_ts.map(move |mut ts| { // map preserves Err
                // In case of Ok(...), append to already found elements
                vec.append(&mut ts);
                vec
            })
        }
    )
}

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=f6f738ddedecda1875df283f221dbfdc

Оказывается, Itertools уже имеет fold_results, который должен делать то, что вы хотите: 

fn acc3<T, E>(mut it: impl Iterator<Item = Result<Vec<T>, E>>) -> Result<Vec<T>, E> {
    it.fold_results(
        Vec::new(),
        |mut vec, mut ts| {
            vec.append(&mut ts);
            vec
        }
    )
}
1 голос
/ 02 мая 2020

Чтобы достичь этого только с помощью методов итератора: 

use std::iter::{self, Iterator};

pub fn accumulate<T, E>(it: impl Iterator<Item = Result<Vec<T>, E>>) -> Result<Vec<T>, E> {
    it.flat_map(|v| {
        v.map_or_else(
            |e| Iter::A(iter::once(Err(e))),
            |t| Iter::B(t.into_iter().map(Ok)),
        )
    })
    .collect()
}

// Utility enum that can be generated by the #[auto_enum] derive macro
enum Iter<T, A: Iterator<Item = T>, B: Iterator<Item = T>> {
    A(A),
    B(B),
}
impl<T, A: Iterator<Item = T>, B: Iterator<Item = T>> Iterator for Iter<T, A, B> {
    type Item = T;
    fn next(&mut self) -> Option<T> {
        match self {
            Self::A(a) => a.next(),
            Self::B(b) => b.next(),
        }
    }
}

При этом используется flat_map, чтобы получить либо итератор Ok с, либо итератор Err для каждой записи. Это семантически эквивалентно вашему коду управления потоком, используемому для l oop.

Детская площадка: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=68558e27900940476e443d670a120e91

См. auto_enums для получение перечислимых делегирующих вариантов Iterator.

В качестве альтернативы вы можете использовать either::Either вместо Iter, который имеет одинаковую реализацию для двух элементов:

https://docs.rs/either/1.5.3/either/enum.Either.html#impl - Итератор

...