Day 019 — カスタムイテレータの実装（next()だけで70+メソッドが手に入る理由とFusedIterator）

📚 背景知識（読んでから問題へ）

Day 017・018ではIterator・DoubleEndedIterator・ExactSizeIteratorを自作し、next()を1つ実装するだけで.map()・.filter()・.rev()・.collect()のような70個以上のメソッドが無料で手に入ることを体験しました。今日はその「なぜ無料で手に入るのか」というメカニズムそのものと、Iterator契約の中でも見落とされやすい2つの仕様――size_hint()の契約範囲と「消費し尽くした後」の仕様の曖昧さ（FusedIterator）――を掘り下げます。

📋 コピーpub trait Iterator {
    type Item;

    // 唯一の必須メソッド（required method）
    fn next(&mut self) -> Option<Self::Item>;

    // 以下はすべて「デフォルト実装」を持つメソッド（provided methods）
    // next() の呼び出し列だけを使って書かれている
    fn size_hint(&self) -> (usize, Option<usize>) { (0, None) }
    fn count(self) -> usize where Self: Sized { /* next()をNoneまで呼んで数える */ }
    fn map<B, F>(self, f: F) -> Map<Self, F> where Self: Sized, F: FnMut(Self::Item) -> B { /* ... */ }
    fn filter<P>(self, predicate: P) -> Filter<Self, P> where Self: Sized, P: FnMut(&Self::Item) -> bool { /* ... */ }
    fn fold<B, F>(self, init: B, f: F) -> B where Self: Sized, F: FnMut(B, Self::Item) -> B { /* ... */ }
    fn collect<B: FromIterator<Self::Item>>(self) -> B where Self: Sized { /* ... */ }
    // ...他60個以上
}

mapやfilterのようなメソッドの本体は、Rust標準ライブラリのソース内で完全に書き切られています。あなたが自分の型に対して書くのはnext()の実装だけであり、それ以外のメソッドは「あなたのnext()を呼び出す汎用コード」としてトレイトの中にすでに存在しています。これはimplブロックでオーバーライドしない限りそのまま使われる、いわゆるデフォルトメソッド（provided methods）という仕組みです。

さらに重要なのは、これらのメソッドが実行時に呼ばれる際、Rustは単相化（monomorphization）によって、あなたの具体的な型専用のコードをコンパイル時に生成します。my_iter.map(f).filter(g).sum::<i32>()のようなメソッド連鎖は、実行時に「次は誰のnext()を呼ぶか」を毎回問い合わせる動的ディスパッチ（vtable経由の呼び出し）ではなく、コンパイル時にすべてインライン化された1つのループへと最適化されます。これが「ゼロコスト抽象化」の具体例であり、C++のテンプレートやGoのジェネリクス（型消去ベース）との大きな違いです。

📝 問題

以下の3つの問いに答えてください。いずれもコードを書く前に、まず言葉で説明することが主目的です（要求3のみ、説明の正しさを検証するための実装を伴います）。

要求1（メカニズムの説明）

上記のmapやfoldのようなデフォルトメソッドが、あなたが定義したnext()だけを使ってどうやって動作するのかを、トレイトのデフォルトメソッドという言語機能の観点から説明してください。また、これらのメソッド呼び出しが実行時にvtable経由の動的ディスパッチにならず、コンパイル時にインライン化される理由（単相化）を、Javaのインターフェースのデフォルトメソッド（defaultキーワード）との違いに触れながら説明してください。

要求2（size_hint()の契約範囲の説明）

size_hint()のシグネチャはfn size_hint(&self) -> (usize, Option<usize>)で、戻り値は(下限, 上限)を表します。標準ライブラリのドキュメントには次のように書かれています。

A default implementation is provided ... it is not enforced that an iterator implementation yields the declared number of elements. Cheating is allowed, but consumers relying on the values to be correct should not do so if the iterator implementation yields incorrect values, e.g. by yielding fewer elements than the lower bound indicates.
（出典: std::iter::Iterator::size_hintのドキュメント要約）

つまり、size_hint()が実際の要素数と食い違う値を返してもコンパイルエラーにもパニックにもならず、unsafeでもありません。しかしDay 018で扱ったExactSizeIterator::len()はsize_hint()の下限をベースにしつつ、より強い「正確性の表明」として使われます。Vec<T>::with_capacityを使うcollect::<Vec<T>>()がsize_hint()の値を信じて事前確保を行うとき、実際の要素数がその値を上回った場合と下回った場合とで、それぞれ何が起きるか（パニックか、単なる非効率か、それとも未定義動作か）を説明してください。そのうえで、なぜRustの設計者は「size_hint()が嘘をついてもメモリ安全性は破られない」という制約のもとでこの仕組みを設計したのかを述べてください。

要求3（FusedIteratorと検証実装）

Iteratorの公式な契約では、「一度next()がNoneを返した後、再びnext()を呼んだときに何を返すべきか」は規定されていません。多くのイテレータは一度Noneを返したら以後もずっとNoneを返す（これを「fusedである」と呼ぶ）よう実装されていますが、これは慣習であって言語仕様の強制ではありません。

次のAlternatorという非fusedなイテレータを実装し、.next()を5回呼び出した結果が[Some(1), None, Some(1), None, Some(1)]というNoneを挟んで値が復活するパターンになることを実際にテストで示してください。そのうえで、標準アダプタ.fuse()でラップすると、2回目以降はずっとNoneのままになる（[Some(1), None, None, None, None]）ことも同じテスト関数内で確認してください。

📋 コピーstruct Alternator {
    calls: u32,
}

impl Iterator for Alternator {
    type Item = i32;

    fn next(&mut self) -> Option<Self::Item> {
        self.calls += 1;
        // 奇数回目の呼び出しでは Some(1)、偶数回目では None を返す
        // （TODO: この仕様に合わせて実装する）
        todo!()
    }
}

.fuse()がなぜ必要とされるのか（FusedIteratorマーカートレイトが存在する理由を含めて）を、実装とテストの結果から説明してください。

🔍 ヒント（段階的開示）

📋 コピーimpl Iterator for Alternator {
    type Item = i32;

    fn next(&mut self) -> Option<Self::Item> {
        self.calls += 1;
        if self.calls % 2 == 1 {
            Some(1)
        } else {
            None
        }
    }
}

#[test]
fn alternator_and_fuse_behavior() {
    let mut raw = Alternator { calls: 0 };
    let raw_results: Vec<Option<i32>> = (0..5).map(|_| raw.next()).collect();
    assert_eq!(raw_results, vec![Some(1), None, Some(1), None, Some(1)]);

    let mut fused = Alternator { calls: 0 }.fuse();
    let fused_results: Vec<Option<i32>> = (0..5).map(|_| fused.next()).collect();
    assert_eq!(fused_results, vec![Some(1), None, None, None, None]);
}

✅ 模範解答

📋 コピー// ---- 要求3: Alternator の実装と .fuse() の検証 ----

struct Alternator {
    calls: u32,
}

impl Iterator for Alternator {
    type Item = i32;

    fn next(&mut self) -> Option<Self::Item> {
        self.calls += 1;
        // 奇数回目の呼び出しでは Some(1)、偶数回目では None を返す非fusedなイテレータ
        if self.calls % 2 == 1 {
            Some(1)
        } else {
            None
        }
    }
}

// ---- 要求1の検証用: next() のみで map/filter/fold/sum が使えることを示す ----

struct Counter {
    current: u32,
    max: u32,
}

impl Counter {
    fn new(max: u32) -> Self {
        Counter { current: 0, max }
    }
}

impl Iterator for Counter {
    type Item = u32;

    fn next(&mut self) -> Option<Self::Item> {
        if self.current >= self.max {
            return None;
        }
        self.current += 1;
        Some(self.current)
    }
}

fn main() {
    // next() しか実装していない Counter で map/filter/sum が動く
    let total: u32 = Counter::new(5)
        .map(|x| x * 2)      // デフォルトメソッド（next()の呼び出し列だけで書かれている）
        .filter(|x| x % 4 != 0)
        .sum();               // 消費アダプタもデフォルトメソッド
    println!("total = {total}"); // (2,4,6,8,10) -> 4 は除外 -> 2+6+8+10 = 26

    // Alternator: 非fusedな挙動をそのまま観測する
    let mut raw = Alternator { calls: 0 };
    println!("raw: {:?}", (0..5).map(|_| raw.next()).collect::<Vec<_>>());

    // .fuse() でラップすると一度 None が出た後は常に None になる
    let mut fused = Alternator { calls: 0 }.fuse();
    println!("fused: {:?}", (0..5).map(|_| fused.next()).collect::<Vec<_>>());
}

#[cfg(test)]
mod tests {
    use super::*;

    // 要求1の検証: next() のみの実装から map/filter/fold/sum がそのまま使える
    #[test]
    fn default_methods_work_from_next_only() {
        let total: u32 = Counter::new(5).map(|x| x * 2).filter(|x| x % 4 != 0).sum();
        assert_eq!(total, 26);

        let folded = Counter::new(4).fold(0, |acc, x| acc + x);
        assert_eq!(folded, 1 + 2 + 3 + 4);

        let collected: Vec<u32> = Counter::new(3).collect();
        assert_eq!(collected, vec![1, 2, 3]);
    }

    // 要求3: Alternator は非fused、.fuse() でラップすると fused になる
    #[test]
    fn alternator_and_fuse_behavior() {
        let mut raw = Alternator { calls: 0 };
        let raw_results: Vec<Option<i32>> = (0..5).map(|_| raw.next()).collect();
        assert_eq!(raw_results, vec![Some(1), None, Some(1), None, Some(1)]);

        let mut fused = Alternator { calls: 0 }.fuse();
        let fused_results: Vec<Option<i32>> = (0..5).map(|_| fused.next()).collect();
        assert_eq!(fused_results, vec![Some(1), None, None, None, None]);
    }
}

$ cargo run
total = 26
raw: [Some(1), None, Some(1), None, Some(1)]
fused: [Some(1), None, None, None, None]

$ cargo test
running 2 tests
test tests::alternator_and_fuse_behavior ... ok
test tests::default_methods_work_from_next_only ... ok

test result: ok. 2 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

🪜 Step-by-Step 解説

💡 設計思想・なぜこう書くのか

🌐 他言語との比較

JavaScriptのジェネレータが「完了後は常にdone: true」という挙動を言語仕様として保証しているのに対し、Rustが同じ挙動をFusedIteratorというopt-inのマーカートレイトとして切り出しているのは対照的です。これはRustが「保証を強制する」よりも「保証の有無を型で区別可能にし、必要な保証だけを選び取れるようにする」ことを好む言語だからです。ECMAScriptのように全ジェネレータに一律で強い保証を課すと、その保証を実現するための状態管理コスト（内部フラグ等）がすべての実装に強制されますが、Rustでは自明にfusedな実装（Counterのような単純な数値カウンタ）はそのコストを払わずに済み、必要な場合だけ.fuse()で明示的にコストを払う、という選択制になっています。

🏆 実務での使いどころ

• ページネーションAPIクライアントのイテレータ化: 「次ページがなくなったらもう二度と呼ばれない」という前提でHTTPリクエストの発行を止めるコードを書く場合、対象のイテレータがFusedIteratorかどうかを型境界で要求しておくと、「尽きた後にもう一度呼ばれてリクエストが飛んでしまう」バグを未然に防げます
• collect()のパフォーマンスチューニング: 大量データをパースしてVecに集約するホットパスでは、size_hint()を正確に実装するかどうかが再アロケーション回数に直結します。CSVパーサーやログパーサーで「既知の行数」がある場合にExactSizeIteratorまで実装しておくと、collect()のメモリ確保が1回で済みます
• 無限イテレータと.take()の組み合わせ: size_hint()のデフォルト実装(0, None)（上限不明）は、無限イテレータ（乱数生成器・カウンタ等）が自分の意思で「要素数は分からない」と正直に申告するための仕組みです。これを(固定値, Some(固定値))のように偽って実装してしまうと、collect()が誤った容量でVecを確保し、後続の再アロケーションで無駄なコピーが発生します

⚠️ よくある誤解・ミス

🚀 次のステップ

• 発展: Counterにimpl FusedIterator for Counter {}（マーカートレイトの空実装）を追加し、Counter::new(3).fuse()が余計なラップ構造体を持たずに元のCounterとほぼ同じコードへ最適化されることを、標準ライブラリのFuse<I>のドキュメント（I: FusedIteratorのときはFuse<I> = I相当に特殊化される旨の記述）で確認してみてください
• 次回予告: 自己評価で「完全理解」または「おおむね理解」が3回連続で記録された時点で、次のテーマスマートポインタ①（Box<T>）（ヒープ確保・再帰的データ構造）に進みます

🎯 自己評価

自分の回答

気づき・メモ