The `fold` method cannot be invoked on a trait object

Question

I'm trying to implement a generic Cons List, one somewhat more advanced than the one used in chapter 15 of the book:

use std::fmt::Debug;

#[derive(Debug)]
enum List<T> {
    Nil,
    Cons(T, Box<List<T>>),
}

impl<T> List<T>
where
    T: Debug,
{
    fn from_iterable(iterator: &Iterator<Item = T>) -> Self {
        iterator.fold(List::Nil, |acc, value| List::Cons(value, Box::new(acc)))
    }
}

fn main() {
    println!("{:?}", List::from_iterable(&(1..10)));
}

(playground)

My code does not compile and it has a really confusing message:

error: the `fold` method cannot be invoked on a trait object
  --> src/main.rs:14:18
   |
14 |         iterator.fold(List::Nil, |acc, value| List::Cons(value, Box::new(acc)))
   |                  ^^^^

What does this message mean?

I have seen this somehow related question, but even if this one is a duplicate my current knowledge is too limited to connect the dots.

Answer 1

You have a larger problem. You have accepted a reference to a trait object that is immutable. This means that you cannot call Iterator::next, the most primitive operation on an iterator:

impl<T> List<T>
where
    T: Debug,
{
    fn from_iterable(iterator: &dyn Iterator<Item = T>) -> Self {
        iterator.next();
        panic!();
    }
}

error[E0596]: cannot borrow `*iterator` as mutable, as it is behind a `&` reference
  --> src/main.rs:16:9
   |
15 |     fn from_iterable(iterator: &dyn Iterator<Item = T>) -> Self {
   |                                ----------------------- help: consider changing this to be a mutable reference: `&mut dyn std::iter::Iterator<Item = T>`
16 |         iterator.next();
   |         ^^^^^^^^ `iterator` is a `&` reference, so the data it refers to cannot be borrowed as mutable

If you follow this error suggestion and update the call site to pass in a mutable reference, your code works:

impl<T> List<T>
where
    T: Debug,
{
    fn from_iterable(iterator: &mut dyn Iterator<Item = T>) -> Self {
        iterator.fold(List::Nil, |acc, value| List::Cons(value, Box::new(acc)))
    }
}

fn main() {
    println!("{:?}", List::from_iterable(&mut (1..10)));
}

However, it's not common to use trait objects for this type of problem, as they involve dynamic dispatch and some (small) amount of runtime overhead. Instead, it's far more common to use static dispatch with generics:

impl<T> List<T>
where
    T: Debug,
{
    fn from_iterable(iterator: impl IntoIterator<Item = T>) -> Self {
        iterator
            .into_iter()
            .fold(List::Nil, |acc, value| List::Cons(value, Box::new(acc)))
    }
}

fn main() {
    println!("{:?}", List::from_iterable(1..10));
}

I also switched to IntoIterator as it's a bit more ergonomic for callers.

See also:

• The Rust Programming Language, chapter 10: generics
• The Rust Programming Language, chapter 17: trait objects
• What does "dyn" mean in a type?