How to iterate over and filter an array?

Question

I'm trying to write a program that involves filtering and folding over arrays. I've been using The Rust Programming Language, first edition as a reference, but I don't understand what happens when I form iterators over arrays. Here is an example:

fn compiles() {
    let range = (1..6);
    let range_iter = range.into_iter();
    range_iter.filter(|&x| x == 2);
}

fn does_not_compile() {
    let array = [1, 4, 3, 2, 2];
    let array_iter = array.into_iter();
    //13:34 error: the trait `core::cmp::PartialEq<_>` is not implemented for the type `&_` [E0277]
    array_iter.filter(|&x| x == 2);
}

fn janky_workaround() {
    let array = [1, 4, 3, 2, 2];
    let array_iter = array.into_iter();
    // Note the dereference in the lambda body
    array_iter.filter(|&x| *x == 2);
}

(Rust playground)

In the first function, I follow that the iterator over the range does not take ownership, so I must take a &x in filter's lambda, but I don't understand why the second example with the array behaves differently.

Answer 1

Arrays are the type [T; N] in Rust, for any element type T and a constant number N. It's a fixed size array.

Rust doesn't implement by-value iterators for arrays at the moment. All arrays coerce to slices (type [T]) and the slice methods are available on the array because of this. The arrays also get the slice's iterator, which is called std::slice::Iter<'a, T> and has elements of type &'a T: it iterates by reference!

This is why into_iter() on a Range<i32> produces an iterator of i32 and into_iter() on a [i32; 5] produces an iterator of &i32.

If you need by value iterators for arrays, they have been implemented in the broader ecosystem, see (1) and (2).

Answer 2

In cases like this, it's very useful to force the compiler to tell you the type of the variable. Let's trigger a type error by assigning the closure argument to an incompatible type:

array_iter.filter(|x| { let () = x; true });

This fails with:

error[E0308]: mismatched types
  --> src/main.rs:12:33
   |
12 |     array_iter.filter(|x| { let () = x; true });
   |                                 ^^ expected &&{integer}, found ()
   |
   = note: expected type `&&{integer}`
              found type `()`

Now we know the type of x is a &&{integer} - a reference to a reference to some kind of integer. We can then match against that instead:

fn hooray() {
    let array = [1, 4, 3, 2, 2];
    let array_iter = array.into_iter();
    array_iter.filter(|&&x| x == 2);
}

The question now becomes "why is it a reference to a reference"? The short version is that the iterator of an array returns references (see the type Item = &'a T part). In addition, Iterator::filter passes a reference to the closure to prevent moving and subsequently losing non-Copy types.

Answer 3

As Shepmaster and bluss said, you can check the documentation for the array type, which mentions:

Arrays of sizes from 0 to 32 (inclusive) implement the following traits if the element type allows it:

• IntoIterator (implemented for &[T; N] and &mut [T; N])

As it says, this is only for references, and is reflected in its Item type: type Item = &'a T and type Item = &'a mut T.