Rubyの内部実装：EnumeratorとEnumerableの仕組みを自作で理解する

Ruby Magicへようこそ！1年前、私たちはRubyのEnumerableモジュールについて学びました。これは配列、範囲、ハッシュなどの列挙可能なオブジェクトを操作する際に使うメソッドを提供します。

当時、LinkedListクラスを作成し、#eachメソッドを実装することでオブジェクトを列挙可能にする方法を示しました。Enumerableモジュールをincludeすることで、#count、#map、#selectなどのメソッドを、自前で実装せずともあらゆるリンクドリストで呼び出せるようになりました。

列挙可能オブジェクトの使い方は理解しましたが、それらは内部でどう動いているのでしょう？RubyのEnumerableの「魔法」の一端は、その内部実装が単一の#eachメソッドに基づいており、さらにEnumeratorのチェーンまで可能にしている点にあります。

今回は、Enumerableクラスのメソッドがどう実装されているか、そしてEnumeratorオブジェクトがいかにして列挙メソッドのチェーンを実現しているかを学びます。

恒例となりましたが、EnumerableモジュールとEnumeratorクラスの独自実装に挑み、深く掘り下げていきます。オーバーエンジニアリングのヘルメットをかぶり、始めましょう！

リンクドリスト

まずは前回書いたリンクドリストクラスの新バージョンから始めます。

class LinkedList
  def initialize(head = nil, *rest)
    @head = head

    if rest.first.is_a?(LinkedList)
      @tail = rest.first
    elsif rest.any?
      @tail = LinkedList.new(*rest)
    end
  end

  def <<(head)
    @head ? LinkedList.new(head, self) : LinkedList.new(head)
  end

  def inspect
    [@head, @tail].compact
  end

  def each(&block)
    yield @head if @head
    @tail.each(&block) if @tail
  end
end

前回のバージョンと異なり、この実装では空のリスト作成や、2要素以上のリスト作成が可能です。また、別のリンクドリストを初期化時のtailとして渡せるようにもなっています。

irb> LinkedList.new
=> []
irb> LinkedList.new(1)
=> [1]
irb> LinkedList.new(1, 2)
=> [1,[2]]
irb> LinkedList.new(1, 2, 3)
=> [1,[2,[3]]]
irb> LinkedList.new(1, LinkedList.new(2, 3))
=> [1,[2,[3]]]
irb> LinkedList.new(1, 2, LinkedList.new(3))
=> [1,[2,[3]]]

前回、LinkedListクラスはEnumerableモジュールをincludeしていました。Enumerableのメソッドでマッピングすると、結果は配列に格納されます。今回は独自実装を行い、メソッドが配列ではなく新しいリンクドリストを返すようにします。

Enumerableメソッドの実装

RubyのEnumerableモジュールには、#map、#count、#selectといった列挙メソッドが備わっています。#eachメソッドを実装し、Enumerableをクラスにincludeすれば、それらのメソッドを直接リンクドリストで使えるようになります。

しかしここでは、Ruby標準の代わりにDIYEnumerableを実装し、それをincludeします。これは実用的ではありませんが、列挙の内部動作を明確に理解するのに役立ちます。

まずは#countから。Enumerableのインクルード可能なメソッドはすべて、私たちがLinkedListで実装した#eachメソッドを使ってオブジェクトをループし、結果を計算します。

module DIYEnumerable
  def count
    result = 0
    each { |element| result += 1 }
    result
  end
end

この例では、LinkedListにincludeする新しいDIYEnumerableモジュールに#countメソッドを実装しました。カウンタを0で開始し、#eachメソッドを呼んでループごとに1を加算。全要素をループした後、カウンタを返します。

module DIYEnumerable
  # ...

  def map
    result = LinkedList.new
    each { |element| result = result << yield(element) }
    result
  end
end

#mapメソッドも同様に実装します。カウンタの代わりにアキュムレータ（蓄積用リスト）を使い、空のリストで開始。全要素をループし、渡されたブロックを各要素でyield。その結果をアキュムレータに追加していきます。全要素処理後、アキュムレータを返します。

class LinkedList
  include DIYEnumerable

  #...
end

DIYEnumerableをLinkedListにincludeしたら、新しく追加した#countと#mapをテストします。

irb> list = LinkedList.new(73, 12, 42)
=> [73, [12, [42]]]
irb> list.count
=> 3
irb> list.map { |element| element * 10 }
=> [420, [120, [730]]]

両方動きました！#countはリストのアイテム数を正しく数え、#mapは各アイテムに対してブロックを実行し、更新されたリストを返します。

リストが反転してしまう問題

しかし、#mapメソッドの結果を見るとリストが反転しています。これは、リンクドリストクラスの#<<メソッドがアイテムを「追加」ではなく「先頭に追加（prepend）」するためです。これはリンクドリストの再帰的な性質によるものです。

リストの順序を保持しなければならない状況では、マッピング時にリストを反転させる方法が必要です。RubyにはEnumerable#reverse_eachがあり、オブジェクトを逆順でループできます。これが解決策になりそうです。しかし残念ながら、私たちのリストはネスト構造なので、全体をループするまで長さがわかりません。reverse_eachのようなアプローチは使えません。

そこで、リストを逆順でループする代わりに、2ステップで処理する#reverse_eachを実装します。まずリストをループして新しいリストを作りながら反転させ、その後その反転リストに対してブロックを実行します。

module DIYEnumerable
  # ...

  def reverse_each(&block)
    list = LinkedList.new
    each { |element| list = list << element }
    list.each(&block)
  end

  def map
    result = LinkedList.new
    reverse_each { |element| result = result << yield(element) }
    result
  end
end

これで#mapメソッド内で#reverse_eachを使うようになり、元のリストと同じ順序で結果が返るようになりました。

irb> list = LinkedList.new(73, 12, 42)
=> [73, [12, [42]]]
irb> list.map { |element| element * 10 }
=> [730, [120, [420]]]

うまくいきました！これで#mapをリンクドリストで呼ぶたびに、元の順序と同じ新しいリストが得られます。

Enumeratorによる列挙のチェーン

リンクドリストクラスに実装した#eachメソッドと、includeしたDIYEnumerableによって、双方向のループとマッピングが可能になりました。

irb> list.each { |x| p x }
73
12
42
irb> list.reverse_each { |x| p x }
42
12
73
irb> list.reverse_each.map { |x| x * 10 }
=> [730, [120, [420]]]
=> [420, [120, [730]]]

しかし、リストを逆順でマッピングしたい場合はどうでしょう？今はマッピング前にリストを反転させるため、常に元の順序で結果が返ります。#reverse_eachと#mapは両方実装済みなので、それらをチェーンして逆順マッピングができれば便利です。ここでRubyのEnumeratorクラスが役立ちます。

前回、LinkedList#eachがブロックなしで呼ばれた場合にKernel#to_enumを呼ぶようにしました。これによりEnumeratorオブジェクトが返り、列挙メソッドのチェーンが可能になります。Enumeratorクラスの仕組みを知るため、独自実装してみましょう。

class DIYEnumerator
  include DIYEnumerable

  def initialize(object, method)
    @object = object
    @method = method
  end

  def each(&block)
    @object.send(@method, &block)
  end
end

RubyのEnumeratorと同様、私たちのEnumeratorクラスはオブジェクトのメソッドをラップするラッパーです。ラップされたオブジェクトに処理を委譲することで、列挙メソッドのチェーンを実現します。

これは、DIYEnumeratorインスタンス自体が列挙可能だから機能します。#eachを実装してラップ対象を呼び出し、DIYEnumerableをincludeすることで、すべての列挙メソッドを呼び出せるようになります。

LinkedList#each`メソッドにブロックが渡されなかった場合、DIYEnumerator`のインスタンスを返すようにします。

class LinkedList
  # ...

  def each(&block)
    if block_given?
      yield @head
      @tail.each(&block) if @tail
    else
      DIYEnumerator.new(self, :each)
    end
  end
end

irb> list = LinkedList.new(73, 12, 42)
=> [73, [12, [42]]]
irb> list.map { |element| element * 10 }
=> [420, [120, [730]]]