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.

Why did you decide to use a trait object in the first place? — Shepmaster, Feb 16 '18 at 18:53
@Shepmaster I thought it was good idea to have a factory method that could create a list from any iterator because I only need argument to be foldable. Are there any reasons not to make my code that generic? — Yury Tarabanko, Feb 16 '18 at 18:56

Shepmaster · Accepted Answer · 2019-06-07T14:05:01.103

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.

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

1 Answers1