如何递归传递函数指针？

Question

我想编写一个 Iterator 适配器，它将一个函数递归地应用到它的底层 Iterator。递归是因为变体IR::Loop包含一个Vec<IR>，其中一个迭代器也应该传递给函数

该函数应采用 &mut Iterator<Item = IR> 并使用它来计算迭代器的下一个值（如 itertools::batching）。

use std::iter::Peekable;

#[derive(Clone)]
enum IR {
    OperationA,
    OperationB,
    Loop(Vec<IR>),
}

pub trait MyItertools: Iterator {
    fn apply_recursive<F: Fn(&mut Peekable<Self>) -> Option<Self::Item>>(
        self,
        f: F,
    ) -> ApplyRecursive<Self, F>
    where
        Self: Sized,
        Self::Item: Clone,
    {
        ApplyRecursive {
            iter: self.peekable(),
            f: f,
        }
    }
}

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

//applies a function recursively to some Iterator with Item=IR
#[derive(Clone)]
struct ApplyRecursive<I, F>
where
    I: Iterator,
    I::Item: Clone,
{
    iter: Peekable<I>,
    f: F,
}

impl<I: Iterator<Item = IR>, F> Iterator for ApplyRecursive<I, F>
where
    F: Fn(&mut Peekable<I>)
       -> Option<I::Item>,
{
    type Item = I::Item;

    fn next(&mut self) -> Option<I::Item> {
        match self.iter.peek() {
            Some(&IR::Loop(code)) => {
                self.iter.next(); //advance the iterator
                let code: Vec<IR> = code.into_iter().apply_recursive(self.f).collect();

                Some(IR::Loop(code))
            }
            Some(x) => (self.f)(&mut self.iter),
            None => None,
        }
    }

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

fn main() {}

playground

我做错了什么？我什至不明白错误信息：

error[E0277]: the trait bound `for<'r> F: std::ops::Fn<(&'r mut std::iter::Peekable<std::vec::IntoIter<IR>>,)>` is not satisfied
  --> src/main.rs:54:54
   |
54 |                 let code: Vec<IR> = code.into_iter().apply_recursive(self.f).collect();
   |                                                      ^^^^^^^^^^^^^^^ the trait `for<'r> std::ops::Fn<(&'r mut std::iter::Peekable<std::vec::IntoIter<IR>>,)>` is not implemented for `F`
   |
   = help: consider adding a `where for<'r> F: std::ops::Fn<(&'r mut std::iter::Peekable<std::vec::IntoIter<IR>>,)>` bound

error[E0277]: the trait bound `for<'r> F: std::ops::FnOnce<(&'r mut std::iter::Peekable<std::vec::IntoIter<IR>>,)>` is not satisfied
  --> src/main.rs:54:54
   |
54 |                 let code: Vec<IR> = code.into_iter().apply_recursive(self.f).collect();
   |                                                      ^^^^^^^^^^^^^^^ the trait `for<'r> std::ops::FnOnce<(&'r mut std::iter::Peekable<std::vec::IntoIter<IR>>,)>` is not implemented for `F`
   |
   = help: consider adding a `where for<'r> F: std::ops::FnOnce<(&'r mut std::iter::Peekable<std::vec::IntoIter<IR>>,)>` bound

error: no method named `collect` found for type `ApplyRecursive<std::vec::IntoIter<IR>, F>` in the current scope
  --> src/main.rs:54:78
   |
54 |                 let code: Vec<IR> = code.into_iter().apply_recursive(self.f).collect();
   |                                                                              ^^^^^^^
   |
   = note: the method `collect` exists but the following trait bounds were not satisfied: `F : std::ops::Fn<(&mut std::iter::Peekable<std::vec::IntoIter<IR>>,)>`, `ApplyRecursive<std::vec::IntoIter<IR>, F> : std::iter::Iterator`
   = help: items from traits can only be used if the trait is implemented and in scope; the following trait defines an item `collect`, perhaps you need to implement it:
   = help: candidate #1: `std::iter::Iterator`

Answer 1

最后一个错误表明您没有Iterator。 Iterator 仅在特定条件下为您的结构实现，而您没有满足这些条件。第二个错误解释了原因。

the trait for<'r> Fn<(&'r mut IntoIter<IR>,)> is not implemented for the type F

那么，为什么编译器认为这行不通？让我们看看您的约束条件：

impl<I, F> Iterator for ApplyRecursive<I, F>
where
    I: Iterator<Item = IR>
    F: Fn(&mut Peekable<I>) -> Option<I::Item>,

此结构引用了实现 Iterator 的具体类型 I。然后 F 是一个具体类型，它接受对 与 I 相同 具体类型的可变引用。但是，您尝试在具体类型 IntoIter 上使用您的函数（专门针对它碰巧是什么类型） - 但这可能是不同具体类型！

最简单的解决方法是在此处删除泛型：

impl<F> Iterator for ApplyRecursive<vec::IntoIter<IR>, F>
where
    F: Fn(&mut vec::IntoIter<IR>) -> Option<IR>,
{
    type Item = IR;

    fn next(&mut self) -> Option<IR> {

这解决了关于可变性、访问私有字段和导出私有类型的一系列其他错误，但我认为它克服了这个困难。

或者，我们可以更改 F 以接受 trait 对象，而不用担心将其特化：

pub trait CustomIter: Iterator {
    fn apply_recursive<F>(self, f: F) -> ApplyRecursive<Self, F>
    where
        F: Fn(&mut Iterator<Item = Self::Item>) -> Option<Self::Item>,
        Self: Sized,
        Self::Item: Clone,
    {
        ApplyRecursive { iter: self.peekable(), f: f }
    }
}

impl<I, F> Iterator for ApplyRecursive<I, F>
where
    I: Iterator<Item = IR>,
    F: Fn(&mut Iterator<Item = IR>) -> Option<IR>,
{
    type Item = I::Item;

    fn next(&mut self) -> Option<IR> {

如何递归传递函数指针？

How do I pass a function pointer recursively?

iterator

rust