I am trying to process a lisp-like Sexp by recursively applying an optional simplifier to each node of the expression, and saving the result to an internal AST structure. The simplifier may stop processing sub-expressions (aka arguments) when they become unnecessary (lazyness). For example, one does not need to process C and D in the logical and expression (and A B false C D) because its simplification is false anyway.

I could not find a way to implement lazyness: please help. Furthermore, the strict implementation I wrote raised an expected IntoIter<Index>, found type parameter T error in the body of a function declared with where T: Iterator<Item=Index>. Yet, the definition of IntoInter<Index> is Iterator<Item=Index>. So, the types should match, shouldn’t they? I guess the explanation is that Iterator is a trait and IntoIter a type, but how do I resolve the problem?

Hopefully, the code below is detailed enough. Tags is an enum with the list of recognized node tags. Strings are mapped to Tags using strum_macros.

    // adds a symbolic expression to the target AST
    pub fn add_sexp<T>(
        &mut self, // the target AST structure
        sexp: Sexp,
        simplifier: Option<fn(Tags, T, &mut Asg) -> Either<Node, Index>>,
    ) -> Index where T: Iterator<Item=Index> {
        match sexp {
            Sexp::String(symb) => // a leaf of the tree
                return self.add_node(Node::String(symb)),
            Sexp::List(args) => {  // recursively process a node
                match &args[0] {
                    Sexp::List(_) => panic!("a tag cannot be a list"),
                    Sexp::String(t) => {  // use strum_macros
                        let tag = match Tags::from_str(t.as_str()) {
                            Ok(tag_) => tag_,
                            _ => panic!("Unknown tag")
                        };
                        // it should not be necessary to process each sub-expr in advance
                        // I should construct an Iterator<Item=Index> instead of a Vec
                        let args_ : Vec<Index> = args[1..].iter()
                            .map(|a|
                                self.add_sexp(a.clone(), simplifier)).collect();
                        return self.add_internal(tag,
                            args_.into_iter(),
                            simplifier)  // this is where the error occurs
                        }
                    Sexp::Empty => panic!("empty tag")
                }
            }
            Sexp::Empty => {
                panic!("empty input")
            }
        }
    }

    // adds an internal node to the target AST after simplifying it
    pub fn add_internal<T>(
        &mut self,
        tag: Tags,
        generator: T,
        simplifier: Option<fn(Tags, T, &mut Asg) -> Either<Node, Index>>
    ) -> Index where T: Iterator<Item=Index> {
        match simplifier {
            None => return self.add_node(Node::Internal{tag: tag, args: generator.collect()}),
            Some(s) => {
                match s(tag, generator, self) {
                    Left(n) => return self.add_node(n),
                    Right(i) => return i
                }}
        };
    }

The error is

error[E0308]: mismatched types
   --> src/asg/mod.rs:118:29
    |
97  | ...sexp<T>(
    |         - found this type parameter
...
116 | ...         return self.add_internal(tag,
    |                         ------------ arguments to this method are incorrect
117 | ...             args_.into_iter(),
118 | ...             simplifier)
    |                 ^^^^^^^^^^ expected `IntoIter<Index>`, found type parameter `T`
    |
    = note: expected enum `Option<for<'a> fn(Tags, std::vec::IntoIter<asg::Index>, &'a mut Asg) -> Either<_, _>>`
               found enum `Option<for<'a> fn(Tags, T, &'a mut Asg) -> Either<_, _>>`
note: method defined here
   --> src/asg/mod.rs:81:12
    |
81  | ...ub fn add_internal<T>(
    |          ^^^^^^^^^^^^
...
85  | ...   simplifier: Option<fn(Tags, T, &mut Asg) -> Either<Node, Index>>
    |       ----------------------------------------------------------------

But I’m really looking for a lazy solution.