Rust 中的可恢复连续传递样式迭代器减少

Question

我正在尝试编写一个可以在任何时候恢复的延续传递式 "reduce" 函数。我有一个版本可以工作，但是如果我希望它能够利用某种状态的借用，我需要明确地编写一个新版本的函数。 Rust Playground Link

fn reduce_async_with_store<'a, I, A, F, C>(
    store: &mut Store,
    mut iterator: I,
    accumulator: A,
    mut f: F,
    continuation: C,
) where
    I: Iterator + 'a,
    F: FnMut(&mut Store, I::Item, A, Box<dyn FnOnce(&mut Store, A) + 'a>) + Clone + 'a,
    C: FnOnce(&mut Store, A) + 'a,
{
    match iterator.next() {
        None => continuation(store, accumulator),
        Some(item) => {
            let next: Box<dyn FnOnce(&mut Store, A) + 'a> = {
                let f = f.clone();
                Box::new(move |store, accumulator| {
                    reduce_async_with_store(store, iterator, accumulator, f, continuation)
                })
            };
            f(store, item, accumulator, next);
        }
    }
}

fn some_operation(state: &mut Store, continuation: Box<dyn FnOnce(&mut Store) + 'static>) {
    let mut new_state = Store { foo: state.foo };
    continuation(&mut new_state);
}

#[derive(Debug)]
pub struct Store {
    foo: u8,
}

fn main() {
    let mut some_state = Store { foo: 0 };
    let arr = vec![1u8, 2u8, 3u8];
    reduce_async_with_store(
        &mut some_state,
        arr.into_iter(),
        Vec::new(),
        |store, item, mut acc, continuation| {
            println!("Item: {}", item);
            store.foo += item;
            acc.push(item);
            some_operation(
                store,
                Box::new(move |stor| {
                    continuation(stor, acc);
                }),
            );
        },
        |store, acc| {
            println!("Done!! {:?} {:?}", store, acc);
        },
    )
}

这是我想编写的这个函数的版本，我可以在其中将 Store 作为累加器的一部分传入，然后将其取出 - 但是，如果我这样做，我会得到 cannot infer an appropriate lifetime due to conflicting requirements.

Rust Playground Link

fn reduce_async<'a, I, A, F, C>(mut iterator: I, accumulator: A, mut f: F, continuation: C)
where
    I: Iterator + 'a,
    F: FnMut(I::Item, A, Box<dyn FnOnce(A) + 'a>) + Clone + 'a,
    C: FnOnce(A) + 'a,
{
    match iterator.next() {
        None => continuation(accumulator),
        Some(item) => {
            let next: Box<dyn FnOnce(A) + 'a> = {
                let f = f.clone();
                Box::new(move |accumulator| reduce_async(iterator, accumulator, f, continuation))
            };
            f(item, accumulator, next);
        }
    }
}

fn some_operation(state: &mut Store, continuation: Box<dyn FnOnce(&mut Store) + 'static>) {
    let mut new_state = Store { foo: state.foo };
    continuation(&mut new_state);
}

#[derive(Debug)]
pub struct Store {
    foo: u8,
}

fn main() {
    let mut some_state = Store { foo: 0 };
    let arr = vec![1u8, 2u8, 3u8];
    reduce_async(
        arr.into_iter(),
        (&mut some_state, Vec::new()),
        |item, mut acc, continuation| {
            let (store, vec) = acc;
            println!("Item: {}", item);
            store.foo += item;
            vec.push(item);
            some_operation(
                store,
                Box::new(move |store| {
                    continuation((store, vec));
                }),
            );
        },
        |(store, vec)| {
            println!("Done!! {:?} {:?}", store, vec);
        },
    )
}

我如何编写我的函数的这个非专用版本，并在尊重 Rust 的生命周期的同时传递 &mut Store 之类的东西？

为什么我的第一个 reduce_async_with_store 示例被允许，即使我没有为 &mut Store 指定明确的生命周期，它可以一直存在到 'static？

some_operation 采用盒装闭包，因为这是我调用的第 3 方 API 函数采用的方式。我想最终用异步迭代器替换此代码，但我使用的库尚不支持期货。

Answer 1

让我们从some_operation开始；检查常规函数总是比检查闭包更容易，因为编译器只检查它们的签名。

将删除的生命周期放回去，看起来像：

fn some_operation<'s>(state: &'s mut Store, continuation: Box<dyn for<'r> FnOnce(&'r mut Store) + 'static>) {
    let mut new_state = Store { foo: state.foo };
    continuation(&mut new_state);
}

涉及两个不同的生命周期：'s 和 'r — 它们之间没有任何联系。

现在让我们看这里：

Box::new(move |store| {
    continuation((store, vec));
}),

根据reduce_async的签名，continuation类型应该是Box<dyn FnOnce(A) + 'a>。单态化后 A 的类型是什么？传递给函数的参数是一个元组：

(&mut some_state, Vec::new()),

对于某些 'state，第一个元素的类型为 &'state mut State，第二个元素的类型为 Vec<u8>。回顾some_operation的签名：第一个参数是&'s mut State，所以我们在这里选择了'state = 's。然后我们使用类型为 &'r mut State.

的参数调用闭包

回到主程序，我们试图从 (&'r mut State, Vec<u8>) 类型的值构建累加器，它与 (&'state mut State, Vec<u8>) 不同。

这就是编译器试图解释的内容 :) 让我们通过更改 some_operation 的签名来检查此解释：

fn some_operation<'s>(state: &'s mut Store, continuation: Box<dyn FnOnce(&'s mut Store) + 's>) {
    continuation(state);
}

这里我们明确标记了两个生命周期应该是相同的，现在代码编译没有任何错误。

请注意，您的第一个代码片段没有问题，因为每次调用 reduce_async_with_store 时 store: &mut Store 参数的生命周期都不同！在第二个片段中，它被固定为 'state.

在我看来，最简单的解决方法是完全删除可变引用并通过转移所有权来传递 Store。

Rust playground link

fn reduce_async<'a, I, A, F, C>(mut iterator: I, accumulator: A, mut f: F, continuation: C)
where
    I: Iterator + 'a,
    F: FnMut(I::Item, A, Box<dyn FnOnce(A) + 'a>) + Clone + 'a,
    C: FnOnce(A) + 'a,
{
    match iterator.next() {
        None => continuation(accumulator),
        Some(item) => {
            let next: Box<dyn FnOnce(A) + 'a> = {
                let f = f.clone();
                Box::new(move |accumulator| reduce_async(iterator, accumulator, f, continuation))
            };
            f(item, accumulator, next);
        }
    }
}

fn some_operation(state: Store, continuation: Box<dyn FnOnce(Store) + 'static>) {
    let new_state = Store { foo: state.foo };
    continuation(new_state);
}

#[derive(Debug)]
pub struct Store {
    foo: u8,
}

fn main() {
    let some_state = Store { foo: 0 };
    let arr = vec![1u8, 2u8, 3u8];
    reduce_async(
        arr.into_iter(),
        (some_state, Vec::new()),
        |item, acc, continuation| {
            let (mut store, mut vec) = acc;
            println!("Item: {}", item);
            store.foo += item;
            vec.push(item);
            some_operation(
                store,
                Box::new(move |store| {
                    continuation((store, vec));
                }),
            );
        },
        |(store, vec)| {
            println!("Done!! {:?} {:?}", store, vec);
        },
    )
}

请记住，连续调用不是 tail-recursive，因此堆栈会在每次迭代时增长。您在这里可能需要一个蹦床。

Rust 中的可恢复连续传递样式迭代器减少

Resumable continuation-passing style iterator reduce in Rust

continuations

lifetime

rust