イテレータとジェネレータの内部（遅延列の実装）

イテレータプロトコル：列を「引き出す」抽象

配列やリストは全要素をメモリに並べて持ちますが、イテレータはそうではありません。イテレータの本質は**「次の要素を要求されたら1つだけ計算して返す」**という最小限のプロトコルです。多くの言語でこれは次の2つに集約されます。

next() -> (要素, まだ続くか)     // 1つ進めて値を返す
                                 // もう要素が無ければ「終了」の印を返す

JavaScriptの反復子は{ value, done }を返すnext()、Pythonは値を返すかStopIterationを投げる__next__()、RustはSome(x)かNoneを返すnext()、JavaはhasNext()/next()の組です。表現は違っても意味は同じで、「1つ取り出す」操作と「終端」の表現だけがあれば反復は成立します。forループはこのプロトコルへの糖衣にすぎず、内部ではnextを終端まで呼び続けているだけです。

ここで決定的なのは、要素は要求された瞬間に初めて計算される点です。配列は生成時に全要素が確定しますが、イテレータは「次を出せ」と言われるまで何もしない。この性質を**遅延評価（lazy evaluation）**と呼び、これがあるからこそ無限に続く列や、巨大すぎてメモリに載らない列を扱えます。

ジェネレータ：yield による状態機械への変換

イテレータを手で書くと、状態（どこまで進んだか）を自分でフィールドに保持し、nextが呼ばれるたびに分岐させる必要があり煩雑です。これを劇的に楽にするのがジェネレータで、その中核がyieldです。

function* counter() {
  let i = 0;
  while (true) {
    yield i;   // ここで値を「1つ出して」中断する
    i++;
  }
}

yieldの意味は「値を1つ呼び出し元へ返し、その場で関数を中断して、次にnextが呼ばれたら続きから再開する」です。普通の関数は最後まで走って戻りますが、ジェネレータ関数はyield地点で止まり、ローカル変数（上のi）を保ったまま再開できます。これはasync/awaitとコルーチンの内部実装のawaitとまったく同じ「中断・再開」機構であり、コンパイラはyieldを含む関数を**状態機械（state machine）**へ変換することで実現します。

概念的には、上のcounterは次のような構造体＋next関数に書き換えられます。

struct CounterState {
  state: int     // 0=開始, 1=yield後の再開地点
  i: int         // yieldをまたいで生きるローカル変数
}

next(s):
  switch s.state:
    case 0:
      s.i = 0
      // while ループ本体へ
    case 1:
      s.i = s.i + 1   // 前回 yield の続き
  // 共通の継続
  value = s.i
  s.state = 1
  return (value, 続く)   // ここで中断して呼び出し元へ戻る

ポイントは2つあります。第一に、yieldをまたいで生きるローカル変数はスタックではなく状態オブジェクト（ヒープ上）に退避される。関数を中断して呼び出し元へ戻ると元のスタックフレームは消えるため、値を別の場所に保持しておかないと再開時に復元できないからです。これはクロージャが外側変数を閉じ込めて生かすのと同じ発想です。第二に、yield地点ごとに状態番号が割り当てられ、再開時はswitchが状態番号を見て続きへジャンプします。手続き的に見える関数の本体が、内部ではこのジャンプ表として制御構文に再構成されているわけです。

遅延評価される無限列

遅延評価の威力が最も際立つのが無限列です。先のcounterはwhile (true)で止まらないコードですが、状態機械化されているためyieldのたびに中断して呼び出し元へ戻ります。だから「無限ループ」でも固まりません。全体を生成してから使うのではなく、必要な1要素を要求された瞬間だけ計算が進むからです。

function* naturals() { let n = 1; while (true) yield n++; }
function* take(it, k) {
  for (let i = 0; i < k; i++) {  // k 個に達したら next を呼ばずに終える
    const { value, done } = it.next();
    if (done) return;
    yield value;
  }
}
// 無限列から先頭5個だけを取り出す（next は5回しか呼ばれない）
[...take(naturals(), 5)]; // [1,2,3,4,5]

naturalsは概念上「すべての自然数」ですが、take(_, 5)がnextを5回しか呼ばないため、naturals内部のループも5回しか進みません。これが遅延列の核心で、「何を計算するか」と「いくつ計算するか」を分離できます。フィボナッチ列、素数列、ストリームから無限に届くイベントなど、終わりの定まらない列を有限の消費側で安全に切り取れるのです。これは結果が変化しない値を扱うイミュータビリティとも相性がよく、各要素を「要求時に生成される確定値」として淡々と流せます。

イテレータ融合：中間配列を消す

遅延評価がもたらす実務的な最大の利得が**イテレータ融合（fusion）**です。配列に対するmapやfilterを素朴に連鎖すると、段ごとに中間配列が作られます。

// 各段が新しい配列を確保する（中間配列が2本生まれる）
data.map(f).filter(p).map(g);

100万要素なら、map(f)で100万要素の配列、filter(p)でさらに別配列…とメモリ確保とコピーが段数ぶん発生します。一方、map/filterを遅延イテレータとして合成すると様相が変わります。各段は「上流から1つ受け取り、変換して下流へ1つ渡す」だけの薄いラッパになり、nextを1回呼ぶと1個の要素が全段を一気通貫で流れます。

融合の効果は2つあります。1つは中間配列の消滅によるメモリ削減で、連続したメモリへのアクセスが増えキャッシュにも優しくなります（メモリ配置とキャッシュ局所性）。もう1つは早期終了の伝播です。融合されたtake(map(filter(...)), 3)は、下流が3個受け取った時点でnextを呼ぶのをやめるため、上流のfilterやmapも4個目以降を一切計算しません。素朴な連鎖が「全要素を変換してから先頭3個を取る」のに対し、融合は「3個ぶんしか計算しない」。RustのIteratorやJavaのStreamが高速なのは、まさにこの遅延合成＋融合をコンパイラ／ライブラリが徹底しているからです。

まとめ

イテレータとジェネレータの内部は、(1)「次を1つ返すnext＋終端の印」という最小プロトコルと遅延評価、(2)yieldをyield地点ごとの状態番号とヒープ退避したローカル変数からなる状態機械へ変換する仕組み、(3)map/filterを薄いラッパとして遅延合成し中間配列と多重周回を消すイテレータ融合、という3層で成り立ちます。「列は要求されるまで計算されない」という一点を握ると、無限列が固まらない理由、融合がメモリと走査を削る理由、早期終了が上流まで効く理由が一貫して説明できます。中断・再開機構の全体像はasync/awaitとコルーチンの内部実装と合わせて押さえると理解が盤石になります。