【Rust】なぜ filter に渡す関数の引数は二重参照なのか

想定読者

• 所有権の基本は分かるけど、変数の関数への受け渡しや struct が絡むと分からなくなる
• rust-analyzer に怒られたとき、ぶっちゃけ当てずっぽうで clone() を足している

なぜ filter に渡す関数の引数は二重参照なのか？

Rust で配列をフィルタしたいとき、我々は filter 関数を使います。
例えば、配列から偶数の要素のみを取り出したいときは以下のように書きます。

let data = vec![3, 20, 21];
let result: Vec<&i32> = data.iter()
    .filter(|x: &&i32| **x % 2 == 0)
    .collect();

x に ** (二重参照外し) がついています。これは x の型が &&i32 (二重参照) であり、値にアクセスするのに必要だからです。

ここで、今回のテーマは、 なぜ x の型は &&i32 になるのか？ です。

分かりやすくするために、上のコードを分解して考えましょう。すると、以下のようになります。

let vec: Vec<i32> = vec![3, 20, 21];
let iter: Iter<i32> = vec.iter();
let filtered: Filter<Iter<i32>, fn(&&i32) -> bool> = iter.filter(|x: &&i32| **x % 2 == 0);
let collected: Vec<&i32> = filtered.collect();

動作は同じですが、各ステップでの変数の型が明示されています。それでは、一行ずつ見ていきます。

1. リストの定義

let vec: Vec<i32> = vec![3, 20, 21];

ここでは、数値型の要素をもつリスト vec を定義しています。 vec は Vec<i32> 型です。

2. イテレータの生成

let iter: Iter<i32> = vec.iter();

ここでは、リストに対して、 iter() を呼び出してイテレータに変換しています。 iter() のシグネチャは以下のとおりです。

// iter
fn iter(self: &Vec<i32>) -> Iter<i32>

iter() メソッドは、リストの 参照 を受け取ってイテレータを返します。よって、 vec の所有権は移動せず、引き続き我々は vec を使うことができます。

そもそもイテレータとは？

そもそもイテレータとは何でしょうか？

例えば、JavaScript では、以下のようにリストに対して直接フィルタを呼び出すことができます。

const data = [3, 20, 21];
const result = data.filter(x => x % 2 === 0);

ここにはイテレータという概念はありません。 イテレータとは Rust 固有の概念なのでしょうか？

そんなことはありません。 JavaScript の配列も、実はイテレータを内部的に使っていて、平易のため、イテレータを意識せずに済むようにされているだけです。

もしも JavaScript であえて原始的にフィルタを実装するとしたら、以下のようになるでしょう。

const data = [3, 20, 21];
const result = [];
for (let i = 0; i < data.length; i++) {
    const x = data[i];
    if (x % 2 === 0) {
        result.push(x);
    }
}

そう、for ループで一つずつ要素を取り出します。.filter() や .map() といったメソッドを使ってると意識しにくいですが、フィルタ処理の実装には必ず for ループが必要です。

そして、イテレータが担っているのは、上記のコードのこの部分です。

const x = data[i];

至極単純です。イテレータは、 対象から一つずつ要素を取り出すという操作 を提供しているのです。

この操作をさらに分離して、実際のイテレータに近い形でフィルタを実装すると、以下のようになります。

const data = [3, 20, 21];

// ここからイテレータ
const iter = {
    array: data,
    index: 0
}
function next(iter) {
    if (iter.index < iter.array.length) {
        const next = iter.array[iter.index];
        iter.index++;
        return next;
    } else {
        return null;
    }
}
// ここまでイテレータ

let result = [];
while (true) {
    x = next(iter);
    if (x === null) {
        break;
    }
    if (x % 2 === 0) {
        result.push(x);
    }
}

iter というオブジェクトが、配列と現在のインデックスをもっています。 next() 関数は、iter から次の要素を取り出す操作を提供しています。 while ループで next() を呼び出して次々と要素を取り出し、フィルタ処理を行っています。そして最終的に result にはフィルタされた要素が入ります。

このように、イテレータとは、 対象から一つずつ要素を取り出す操作をカプセル化したオブジェクト なのです。

イテレータのもつ情報

いま一度 Rust のイテレータに戻りましょう。Rust で、イテレータであることの条件は、 Iterator トレイトを実装していることです。 Iterator トレイトは以下のように定義されています。

trait Iterator {
    type Item;
    fn next(&mut self) -> Option<Self::Item>;
}

要するに、next() メソッドをもっていて、Iterator::Item 型の要素を返すことができれば、それはイテレータということです。要素がもう無い場合は next() は None を返します。

Iter<i32> がする動作

ここで重要なのは、イテレータは必ずしも要素の「値」を返すとは限らない、ということです。 Iterator::Item 型は、参照型であっても良いのです。

もとのフィルタのコードにおいて、 vec.iter() が返すイテレータ Iter<i32> は、 Iterator::Item 型が &i32 (i32 への参照) になっています。 つまり、 next() を呼び出すと、 i32 の値そのものではなく、&i32 が返されます。

実際の Iter<i32> の next() メソッドは以下のような実装になっていることでしょう。

// イメージであり、構文が多少異なります
struct Iter<i32> { vec: &Vec<i32>, current_index: usize, }

impl Iterator for Iter<i32> {
    type Item = &i32;
    
    fn next(self: &mut Iter<i32>) -> Option<&i32> {
        let value: &i32 = &self.vec[self.current_index];
        self.current_index += 1;
        if self.current_index < self.vec.length {
            Some(value)
        } else {
            None
        }
    }
}

ここではイテレータ Iter<i32> は、Iterator トレイトに要求される next() と Item の他に、もとのリストへの参照 vec と、現在のインデックス current_index をもっています。イテレータ自体は非常に軽量です。

next() メソッドは、現在のインデックスに対応する要素への参照 &i32 を返し、インデックスを進めます。対象から要素を一つずつ取り出す、イテレータの役割を果たしています。

iter() の動作

注意点として、 iter() メソッドが行うのは、Iter<i32> イテレータの構造体にリストへの参照を格納して返すことだけです。 next() メソッドは呼び出されません。

イテレータとはあくまで、要素を一つずつ取り出すことが できる 道具のようなもので、実際に要素を取り出す行為は next() を呼び出して初めて行われるのです。

まとめ

ここでもう一度最初のコードを見てみましょう。

let iter: Iter<i32> = vec.iter();

すなわち、ここで作っている iter とは、もとのリストについて、各要素への参照 (&i32) を返す next() メソッドをもつ、イテレータなのです。

3. フィルタの適用

let filtered: Filter<Iter<i32>, fn(&&i32) -> bool> = iter.filter(|x: &&i32| **x % 2 == 0);

ここでは、いよいよイテレータに対して iter.filter(...) を呼び出して、偶数のみを取り出しています。

filter() の動作を理解するのには、特にシグネチャが重要になります。 filter() のシグネチャは以下のとおりです。

// filter
fn filter<P>(self: Iter<i32>, predicate: P) -> Filter<Iter<i32>, P>
where
    P: FnMut(&Self::Item) -> bool,

注目すべきポイントは以下の2点です。

• イテレータとコールバック関数を受け取り、 新しいイテレータ を返している。
• self の型が Iter<i32> であり、イテレータの所有権を奪っている。

まず、 filter() はイテレータとコールバック関数を受け取って 新しいイテレータ を返します。「いやいや、 返してるのはイテレータじゃなく Filter じゃないか」と思うかもしれませんが、この Filter は Iterator<Item = &i32> を実装してるので、イテレータの一種なのです。

また、 self の型が Iter<i32> であることにも注意してください。 filter() は、もとのイテレータを消費して新しいイテレータを返すのです。つまり、 iter の所有権は filter() に移動し、以降は iter を使うことはできません。

filter() の動作

filter() 自体の行う処理は実に単純です。
始めに、以下のような Filter という構造体が存在します。

struct Filter<I, P> {
    iter: I,
    predicate: P,
}

filter() は、受け取ったイテレータとコールバック関数を Filter に格納して返します。

fn filter<P>(self: Iter<i32>, predicate: P) -> Filter<Iter<i32>, P>
where
    P: FnMut(&Self::Item) -> bool,
{
    Filter {
        iter: self,
        predicate,
    }
}

これだけです。一つ注目すべき点は、受け取ったイテレータの所有権は Filter に移動しているところです。

Filter の定義

それではどこにフィルタ処理が存在するのかというと、それは Filter のもつ next() メソッドです。

前述のとおり、 Filter は Iterator を実装しているので、 next() メソッドをもっています。 next() メソッドは以下のような定義になっています。

// if let 文で型注釈をつけるのはコンパイルエラーですが、イメージのために書いています。以下同様
impl Iterator for Filter<Iter<i32>, fn(&&i32) -> bool>
{
    type Item = &i32;

    fn next(&mut self) -> Option<&i32> {
        while let Some(value: &i32) = self.iter.next() {
            if (self.predicate)(&value) {
                return Some(value);
            }
        }
        None
    }
}

この next() メソッドは、もとのイテレータから要素を一つずつ取り出し、フィルタに合致しない要素はスキップして、フィルタに合致する要素だけを返す、という動作をします。もとのイテレータをラップして、フィルタ処理を追加しているのです。

しかし、この next() メソッドは、 filter() を呼び出した時点ではまだ呼び出されません。 filter() はあくまで、フィルタ処理を行うための Filter イテレータを返すだけで、実際のフィルタ処理は、その next() を呼び出したときに初めて行われるのです。 (iter() と同じです。)

このように、処理の定義だけ定めて、実際の処理の実行は後回しにすることを、 遅延評価 といいます。

そして、このあとイテレータに対して collect() を呼び出すと、 Filter イテレータの next() が呼び出されて、ついに実際にフィルタ処理が実行されることになります。

しかし、その前に、当初の疑問である、なぜ x の型が &&i32 になるのか、を解明しておきましょう。

filter() に渡す関数の引数はなぜ二重参照なのか

上記の Filter の next() メソッドの定義を抜き出してみます。

fn next(&mut self) -> Option<&i32> {
    while let Some(value: &i32) = self.iter.next() {
        if (self.predicate)(&value) {
            return Some(value);
        }
    }
    None
}

このコードを見ると、 self.predicate に渡されている引数 &value の型が &&i32 であることが分かります。

なぜなら、 self.iter の型は Iter<i32> であり、よって self.iter.next() 返り値の型は &i32 であり、すなわち &value の型は &&i32 だからです。したがって、それを受け取る predicate の引数の型も &&i32 になります。

ようやく、なぜ filter() に渡す関数の引数が二重参照になるのか、が解明されました。

4. イテレータをコレクションに変換

let collected: Vec<&i32> = filtered.collect();

最後に、フィルタ済みのイテレータを collect() でリストに変換しています。collect() のシグネチャは以下のとおりです。

// collect
fn collect<Vec<i32>>(self: Filter<Iter<i32>, fn(&&i32) -> bool>) -> Vec<Self::Item>

collect() は、イテレータの next() を繰り返し呼び出してイテレータから要素を一つずつ取り出し、コレクションに格納していきます。つまり、ようやく Filter イテレータの next() が呼び出されて、フィルタ処理が実行されることになります。

collect() の実装は以下のようになっています。

fn collect<Vec<i32>>(self: Filter<Iter<i32>, fn(&&i32) -> bool>) -> Vec<Self::Item> {
    let mut result = Vec::new();
    while let Some(value: &i32) = self.next() {
        result.push(value);
    }
    result
}
// Self::Item は &i32 です。

このコードは、 Filter イテレータの next() を呼び出して要素を一つずつ取り出し、フィルタに合致する要素だけを result に格納していきます。つまり、 collect() の呼び出しは、先の JavaScript のフィルタの実装における、 while ループの部分に相当します。

collect() は、ここまで構築してきたイテレータという道具を実際に使って (=消費して)、コレクションを構築する関数なのです。

これが、rust のイテレータの所有権の流れと、 filter() と collect() の動作の全体像になります。

なぜ二重参照でなければならないのか？

さて、ここまでの説明で、なぜ filter() に渡す関数の引数が二重参照になるのか、は解明されました。しかし、なぜそうしなければならないのか、という疑問は残るかもしれません。

二重参照になるロジックは分かりましたが、もっとシンプルに、 filter() に渡す関数の引数を &i32 にできないのでしょうか？

答えとしては、Rust の所有権システムの制約上、 値を検査したあとに通過させるには、二重参照でなければならない 、ということになります。

これを理解するために、もしも filter() に渡す関数の引数を &i32 にできるとしたら、どのようなコードになるかを考えてみます。

1. into_iter() を使うアプローチ

はじめに、 filter() に渡す関数の引数を &i32 にするパターンの一つとして、まずフィルタするイテレータの Item を i32 にするアプローチが考えられます。

実は、この場合には、目的実現は可能です。 iter() の代わりに into_iter() を使うことで達成できます。

let data = vec![3, 20, 21];
let result: Vec<i32> = data
    .into_iter()
    .filter(|x: &i32| *x % 2 == 0)
    .collect();

このコードでは、 into_iter() を使うことで、最初のイテレータ (IntoIter<i32>) は i32 の値を所有権ごと返すようにしています。これにより、 filter() に渡す関数の引数は &i32 になります。

ただし、このアプローチは、元のリスト data の所有権を into_iter() に移動させることになるため、以降は data を使うことができなくなります。

ということで、filter() に渡す関数の引数が二重参照になってしまう理由の一つは、 iter() を使って元のリストの所有権をケチっているから 、ということでした。

2. そもそも filter() に渡す関数の引数を &i32 にできない理由

さて、 iter() を使ったアプローチで、 filter() に渡す関数の引数を &i32 にすることはできないでしょうか？

試しに、 filter() に渡す関数の引数を &i32 にしてみましょう。

let data = vec![3, 20, 21];
let iter: Iter<i32> = data.iter();
let filtered: Filter<Iter<i32>, fn(&&i32) -> bool> = iter.filter(|x: &i32| *x % 2 == 0);
let result: Vec<&i32> = filtered.collect();

まあ当然コンパイルエラーとなりますが、あくまで仮定の話です。

このコードが成立するとしたら、 Filter の next() メソッドは以下のような定義になっている必要があります。

impl Iterator for Filter<Iter<i32>, fn(&i32) -> bool>
{
    type Item = &i32;

    fn next(&mut self) -> Option<&i32> {
        while let Some(value: &i32) = self.iter.next() {
            if (self.predicate)(value) {
                return Some(value);
            }
        }
        None
    }
}

元との違いは分かりますか？以下の部分が、 &value から value に変わっています。

        while let Some(value: &i32) = self.iter.next() {
-           if (self.predicate)(&value) {
+           if (self.predicate)(value) {
                return Some(value);
            }
        }

このとき、何が起こるでしょう。 predicate は value を検査するための関数ですが、ここでは predicate に value の所有権を渡してしまいました。すると、そのあとで return Some(value) を呼び出すことができません。

rustc は、おなじみのエラーを出すことでしょう！

error[E0382]: use of moved value: `value`
  --> src/main.rs:XX:20
   |
XX |             if (self.predicate)(value) {
   |                ----------------------- value moved here
XX |                 return Some(value);
   |                             ^^^^^ value used here after move

(なんて親切なエラーメッセージ)

ということで、 filter() に渡す関数の引数を &i32 にできない理由は、 値を検査したあとに通過させるには、二重参照でなければならない 、でした。

まとめ

• filter() に渡す関数の引数が二重参照になる理由
  • iter() を使うと、イテレータの Item は &i32 になるため、 filter() に渡す関数の引数も &&i32 になる。
  • into_iter() を使うと、イテレータの Item は i32 になるため、 filter() に渡す関数の引数は &i32 になる。
• filter() に渡す関数の引数を &i32 にできない理由
  • filter() の next() メソッドで、値を検査したあとに通過させるには、二重参照でなければならないから。
  • into_iter() を使えばできる (ただ多分 data を使いたい場面で困っているはず)