こんにちは。 Rust、日進月歩ですね。
ちょっと前¹に、私はこんな記事を書きました：

ざっと上記の記事の内容をまとめると、関数の定義時には戻り値の型を明示してやる必要があるので、型がめちゃくちゃ長く複雑になりがちなイテレータを返す関数を書くのは辛いよ、という内容でした。

しかしもう上記の記事の内容は古くなっていて、今ではいわゆるimpl Trait機能によって、イテレータを返す関数を書くときに、長ったらしいイテレータの型をわざわざ記述する必要はなくなっています。

しかし、しかしです。現在(2021年4月、Rust ver.1.51) impl Trait 機能はtrait中では使えません。つまり、イテレータをtraitから返すこんなコードを書こうとしても：

コンパイルが通らない例

trait ListOfInt32 {
    fn int32_iter(self) -> impl Iterator<Item=i32>;
}

コンパイラに怒られます。

error[E0562]: `impl Trait` not allowed outside of function and inherent method return types

本稿では、イテレータをtraitから返す際に遭遇するであろう問題２つと、それらに対するいくつかの解決策を記述します。

#問題0: trait内ではimpl Trait記法が使えない#

さて、上記のエラー自体は簡単な回避方法があります。イテレータの型を、traitの関連型(Associated type)に設定してやるのです：

trait ListOfInt32 {
    type Int32Iterator: Iterator<Item = i32>;
    fn int32_iter(self) -> Self::Int32Iterator;
}

これでコンパイルが通ります。　しかし、このtraitを実装するときには……：

impl ListOfInt32 for Vec<i32> {
    type Int32Iterator = /* ここにイテレータの型を書く */;
    fn int32_iter(self) -> Self::Int32Iterator {
        /* ... */
    }
}

はい、イテレータの型を書かなければならない問題が再燃します。

問題1: イテレータの型を書かされる

解決策z: 気合でイテレータの型を手動で書く

これはイヤですね。

解決策a: イテレータを`Box`で包む

これは常道の手段で、Box<dyn Iterator<Item=i32>>を返すようにすればイテレータの型を書かなくて済みます。　もちろんBoxを使っているのでヒープメモリのアロケーションも発生しますし、イテレータの静的ディスパッチも捨て去ることになります。
このデメリットが許容できるならこれでもいいのですが、実は他にも手段があります。

解決策b: nightlyのunstable機能を使う

割り切ってunstableの機能を使えるなら、type_alias_impl_traitのfeatureを使うことにより、上記のイテレータの型部分にもimpl Traitを書くことが可能になります。
(2021/08/02追記: feature名がmin_type_alias_impl_traitから上記の名前に変更になっています)

nightlyでのみ利用可能

#![feature(type_alias_impl_trait)]

// 前とおなじ
trait ListOfInt32 {
    type Int32Iterator: Iterator<Item=i32>;
    fn int32_iter(self) -> Self::Int32Iterator;
}

impl ListOfInt32 for Vec<i32> {
    type Int32Iterator = impl Iterator<Item=i32>; // <-- ここに使える！！
    fn int32_iter(self) -> Self::Int32Iterator {
        <Self as IntoIterator>::into_iter(self)
    }
}

これが使えるならこれが一番いいです。 nightlyでしか使えない以外、特に大きなデメリットも私は見つけていませんし、なんか実装がバグってるみたいなことも聞いていません。
結構前（2019年）にほぼ実装は完了しているみたいなのに、なんでstableに降りてこないんでしょうね？（←issueをロクに読んでない）

解決策c: イテレータのラッパ型を実装する

いくつかの条件が噛み合えば、イテレータのラッパ型を新しく実装すると記述が楽になる場合があります。たとえば、上述のtrait ListOfInt32をVec<String>にimplするために、Stringをint32に変換するイテレータを噛ます例を考えましょう：

impl ListOfInt32 for Vec<String> {
    type Int32Iterator = StringToInt32Iterator; // <-- かんたん！
    fn int32_iter(self) -> Self::Int32Iterator {
        StringToInt32Iterator {
            iter: self.into_iter(),
        }
    }
}

// Vec<String>のイテレータを受け取って、i32に変換するイテレータ
struct StringToInt32Iterator {
    iter: <Vec<String> as IntoIterator>::IntoIter, // <-- ギリ書けるレベル
}
impl Iterator for StringToInt32Iterator {
    type Item = i32;
    fn next(&mut self) -> Option<Self::Item> {
        use std::str::FromStr;
        self.iter.next().map(|s| i32::from_str(&s).unwrap())
    }
}

この例は値の変換途中にOption::map()が挟まっている例です。　これをイテレータで書く場合、Iterator::map()内でOption::map()を呼び出すことになりますが、もしIterator::map()に（関数ポインタではなく）クロージャを渡すと、なんとイテレータの型が記述不能になるので、そうなると上記の力技の解決策zは利用不能です。

一見この解決策は万能に見えますが、適用できないケースも多いです。
必要な条件がいくつかあります：

条件i: ラップ元のイテレータ型が記述可能であること

上記のコードで言う、この部分です：

struct StringToInt32Iterator {
    iter: <Vec<String> as IntoIterator>::IntoIter, // <-- ギリ書けるレベル
}

この種銭となるiterの型がそもそもクソ長だったり、記述不能だったりするケースというのがよくあります。今回はたまたまIntoIteratorのtraitで定義されたイテレータの型を使い回せたのでOKでしたが、そういうのがない場合というのもあり得ます。

条件ii: ラッパがイテレータに施す変更が、それほど複雑でないこと

これは別に記述が不可能になってしまう問題ではないのですが、ラッパの内容の複雑さ次第ではnext()メソッドの実装がかなり複雑になり得ます。　今回のようにただ型をマップするだけならともかく、ラップ元のイテレータとのnext()の呼び出しタイミングがズレる系の、たとえばIterator::flatten()相当のことを実現しようとすると、結構な実装量になってしまいがちですし、バグも混入してしまうかもしれません。
この解決策を採るということは、ラッパ内ではIteratorで定義された各種の便利メソッドを全て捨て去るということです。　処理内容によってはそれなりの覚悟で書く必要があるでしょう。

解決策d: イテレータを返すのではなく、渡す

そもそもなんでイテレータの型を記述する必要があるかというと、イテレータを返しているからです。　返すのではなく渡すように元のtraitを変更すれば、イテレータの型を一切書かないで済みます：

trait Int32IteratorHandler {
    type ReturnType;
    // イテレータの具体的な型を書かなくてよい！
    fn handle<I: Iterator<Item = i32>>(self, iter: I) -> Self::ReturnType;
}
// イテレータを返すかわりに、渡すように変更
trait ListOfInt32 {
    fn handle_int32_iter<H: Int32IteratorHandler>(self, handler: H) -> H::ReturnType;
}

impl ListOfInt32 for Vec<String> {
    fn handle_int32_iter<H: Int32IteratorHandler>(self, handler: H) -> H::ReturnType {
        use std::str::FromStr;
        // .map()も使い放題！
        handler.handle(self.into_iter().map(|s| i32::from_str(&s).unwrap()))
    }
}

// いちいちHandlerの型を定義するのは面倒なので、
// FromIteratorにblanket implementationを用意しておくと便利
impl<T: std::iter::FromIterator<i32>> Int32IteratorHandler for T {
    type ReturnType = Self;
    fn handle<I: Iterator<Item = i32>>(self, iter: I) -> Self::ReturnType {
        iter.collect::<Self>()
    }
}

// もしくはイテレータの値を受け取るクロージャにblanket implementationを用意しておくと便利
// ただしこの書き方だと、上記のblanket implementationと同時には定義できない
//impl<F: FnMut(i32)> Int32IteratorHandler for F {
//    type ReturnType = ();
//    fn handle<I: Iterator<Item = i32>>(mut self, iter: I) -> Self::ReturnType {
//        for v in iter {
//            self(v);
//        }
//    }
//}

この例では、先程の例と同じようにVec<String>に対してListOfInt32を定義していますが、先程の例と違いIteratorの便利メソッドも普通に使えていますし、イテレータの型を一切手動で記述していません。
利用するたびにいちいちHandler型を書かなければならないようにも見えますが、適切にblanket implementationを用意してやることにより、多くのユースケースではHandler型を自分で書かなくてもよくなります。　用途によってFromIteratorかFnMutのクロージャのどちらか、または両方にblanket implementationを用意してあげればいいでしょう²。

この方法もけっこう有用なのですが、最大のデメリットは「イテレータを返す関数の形に(ノーコストでは)書き換えられない」ことでしょう。　例えばforループ構文で回す対象として直接使うことができなくなりますし、イテレータをいったん変数に格納しておいて後で使いたい場合にも困ってしまいます。
また、handle()が本当に呼び出されるかどうかはtraitの実装に依存します。　実装者が信頼できない場合、handle()が呼び出されたかどうかのチェックを入れる必要があるかもしれません。

問題2: イテレータにlifetime引数を渡せない

ここまでの例では、イテレータはi32型を値渡しで返すイテレータ（Iterator<Item=i32>）でした。　一般に、コンテナの要素を値渡しで返すイテレータというのは：

コンテナ型の所有権を奪ってイテレータを返す関数（例：fn into_iter(self)、&selfではなくselfである点に注目）
CopyやCloneが軽い要素型を対象にした便利実装（例：std::str::Charsとか）

のどちらかで、普通のイテレータはコンテナの要素を参照渡しで返します。

ということで、先のListOfInt32を参照渡しのイテレータを返すように書き換えてみましょう：

trait ListOfInt32 {
    //  ここのlifetimeをどうする？？ ↓
    type Iterator: Iterator<Item = &i32>;
    fn iter(&self) -> Self::Iterator;
}

しかし、ここに参照を置く場合、lifetimeを明示的に指定してやる必要があります。
この場合ですと、この参照はコンテナの要素への参照なので、コンテナのlifetime（&selfのlifetime）と同じlifetimeに設定してやればよさそうですね。
その気持ちを素直にコードにすると、こうなります：

trait ListOfInt32 {
    type Iter<'a>: Iterator<Item = &'a i32>;
    fn iter<'a>(&'a self) -> Self::Iter<'a>;
    // ちなみに、lifetime elisionによりこう書いても同じ
    //fn iter(&self) -> Self::Iter<'_>;
}

そしてこの記事で取り上げるくらいですから当然、これはコンパイルが通りません。

error[E0658]: generic associated types are unstable
 --> src/lib.rs:2:5
  |
2 |     type Iter<'a>: Iterator<Item = &'a i32>;
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  |
  = note: see issue #44265 <https://github.com/rust-lang/rust/issues/44265> for more information
  = help: add `#![feature(generic_associated_types)]` to the crate attributes to enable

現在のRustでは、関連型(Associated type)にジェネリック引数を設定してやることができないのです。　そのため、コンテナの(普通の)iter()メソッドは、traitに落とし込むことができません。　よくよく考えてみると、標準ライブラリでも、VecやLinkedListなどのコンテナ「型」はあっても、それらコンテナ型をまとめたtraitってあんまりないですよね。一番近いのはtrait IntoIteratorですが、このtraitが提供するイテレータは、先述のようにコンテナの所有権を奪うfn into_iter(self)から返ってくるので参照を使っておらず、見事にこの地雷を避けているのです。

解決策a: Box<dyn Iterator>を返す

パフォーマンスを多少犠牲にして簡単にコードを書くいつもの方法です。

trait ListOfInt33 {
    fn iter2(&self) -> Box<dyn Iterator<Item = &i32> + '_>;
    // Lifetime elisionを展開するとこんな感じ
    //fn iter2<'a>(&'a self) -> Box<dyn Iterator<Item = &'a i32> + 'a>;
}

この問題に関しては、正直他の解決策が微妙なのでこれは十分考慮に値すると思います。

解決策b: nightlyのunstable機能を使う

エラーメッセージにも書いてあるように、#![feature(generic_associated_types)]を書くと(nightlyビルドで)コンパイルが通るようになります。　ただし注意点として、上で利用したmin_type_alias_impl_traitと比べて、generic_associated_typesは実装がより不完全である"incomplete features"に分類されているという点です。コンパイル時には常にwarningを言われ続けますし、コンパイラがクラッシュするケースもまだ確認されています。　この記事で取り上げるくらいの典型的な使用例ならまず大丈夫でしょうが、ちょっと凝ったことをしようとすると危ないという認識でいましょう。

このfeatureについてはこちらのissueを参照してください。　最新のまとめコメントへのリンクを貼っておきます：

(↑ちょっとQiitaさ～んリンクタイトルの絵文字バグってんよ～)

解決策c: trait自体にlifetime引数を設定する

関連型でlifetime 'aを導入できないなら、traitの定義のときに導入しちゃえばいいじゃない³、ということで、このような書き方ができます：

trait ListOfInt32<'a> {
    type Iter: Iterator<Item = &'a i32>;
    fn iter(&'a self) -> Self::Iter;
}

Vec<i32>へのimplも、なんとなくで書けます：

impl<'a> ListOfInt32<'a> for Vec<i32> {
    type Iter = std::slice::Iter<'a, i32>; // <-- Vec::iter()の戻り値型をコピペ
    fn iter(&'a self) -> Self::Iter {
        self.iter()
    }
}

よさそうですね。　個人的にどうも直感的に怪しい気がしたので、なんとか頑張ってうまいことコンパイルエラーになる悪いケースを作ろうとしてみましたが、意外と作れませんでした。　うまいことエラーが出るケースを作れた方は教えてください。

この手法の最大の問題は、要らんところ（impl<'a>）にlifetime引数を導入してしまったがために、このtraitを利用する場所全て、そしてその場所を利用する場所全て、……というように際限ない範囲に、ロクに使いもしない<'a>の記述を追加しなければならなくなる点です。
たとえば、適当にstruct Hogeで囲んでやるだけでこの有様です：

struct Hoge<'a, T: ListOfInt32<'a>> {
    list: T,
    _phantom: std::marker::PhantomData<&'a T>,
}

要りもしないlifetime 'aを導入させられ、さらにコンパイラには'aを使っていないぞと怒られるので、PhantomDataまで導入させられてしまっています。　これは結構面倒くさいですし、影響範囲が場合によっては甚大になります。

まとめ

次の２つのどちらも許容できないのなら、イテレータを返すtraitは2021年4月現在書かないほうがいいです：

nightlyのunstable featuresを利用する
Box<dyn Iterator>を返す
これらを満たさずに書く方法は、上で挙げた通りないでもないのですが、どれも小さくないデメリットが存在します。

２，３年前ですかね……えっ６年前！？　うせやろ！？？ ↩
コメントにも書いてあるように、この書き方だとこれらのblanket implementationは衝突の可能性があるとコンパイラに怒られるので同時に存在させることができません。　それぞれを適当な単要素structで囲ってやることにより解消できます。 ↩
lifetime引数をとるstructやtraitは（例：struct Container<'a>）、「このContainer型は内部に'aのlifetimeの参照を持っているから、この型は'aより早く死ぬ型だよ」という表明になります。 ↩

問題1: イテレータの型を書かされる

解決策z: 気合でイテレータの型を手動で書く

解決策a: イテレータをBoxで包む

解決策b: nightlyのunstable機能を使う

解決策c: イテレータのラッパ型を実装する

条件i: ラップ元のイテレータ型が記述可能であること

条件ii: ラッパがイテレータに施す変更が、それほど複雑でないこと

解決策d: イテレータを返すのではなく、渡す

問題2: イテレータにlifetime引数を渡せない

解決策a: Box<dyn Iterator>を返す

解決策b: nightlyのunstable機能を使う

解決策c: trait自体にlifetime引数を設定する

まとめ

解決策a: イテレータを`Box`で包む