Ruby 中的枚举内部

欢迎回到新一期的 Ruby Magic！一年前，我们学习了Ruby 的Enumerable模块，它提供了在处理可枚举对象（如数组、范围和哈希）时使用的方法。

当时，我们创建了一个LinkedList类来演示如何通过实现对象#each上的 `numerable` 方法使其可枚举。通过引入该Enumerable模块，我们就可以在任何链表上调用 `get` #count、 `get`#map和`get` 等方法，#select而无需自己实现它们。

我们已经学习了如何使用枚举类型，但它们是如何工作的呢？Ruby 中枚举类型的神奇之处在于它们的内部实现，而这种实现完全基于单个#each方法，甚至允许枚举器链式调用。

今天，我们将学习类中的方法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

与之前的版本不同，此实现允许创建空列表，以及包含两个以上元素的列表。此外，此版本还允许在初始化另一个链表时，将一个链表作为尾部传递。

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课程中包含了` map` 模块。Enumerable当使用该模块的方法遍历对象时Enumerable，结果会存储在一个数组中。这次，我们将实现自己的版本，以确保我们的方法返回的是新的链表。

枚举方法

Ruby 的Enumerable模块提供了诸如`include` #map、#count`include` 和 `include` 之类的枚举方法#select。通过实现该#each方法并将该Enumerable模块包含在我们的类中，我们就可以直接在链表上使用这些方法。

相反，我们将实现DIYEnumerable并导入它，而不是使用 Ruby 的版本。这并非通常的做法，但它能让我们更清楚地了解枚举的内部工作原理。

我们先来看#count……。该类中的每个可导入方法Enumerable都使用#each我们在LinkedList类中实现的方法来遍历对象并计算结果。

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

在这个例子中，我们#count在一个新DIYEnumerable模块上实现了该方法，该模块将被添加到我们的链表中。它从零开始创建一个计数器，并#each在每次循环中调用该方法将计数器加一。遍历完所有元素后，该方法返回最终的计数器值。

module DIYEnumerable
  # ...

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

该#map方法的实现方式类似。它不使用计数器，而是使用累加器，初始状态为空列表。我们将遍历列表中的所有元素，并对每个元素执行 yield 操作。每次 yield 操作的结果都会添加到累加器列表中。

该方法遍历输入列表中的所有元素后，返回累加器。

class LinkedList
  include DIYEnumerable

  #...
end

将 添加DIYEnumerable到我们的之后LinkedList，我们可以测试我们新添加#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方法似乎将列表顺序颠倒了。这可以理解，因为#<<我们链表类中的该方法是在列表前面添加元素而不是在列表后面添加元素，这是链表递归特性的一个体现。

在必须保持列表顺序的情况下，我们需要一种方法在遍历列表时反转列表顺序。Ruby 实现了 ` Enumerable#reverse_eachreverse` 函数，它可以反向遍历对象。这听起来像是解决我们问题的绝佳方案。遗憾的是，我们不能使用这种方法，因为我们的列表是嵌套的。在完全遍历列表之前，我们无法知道列表的长度。

我们不再直接反向遍历列表，而是添加一个#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

现在，我们将#reverse_each在#map方法中使用它，以确保它按正确的顺序返回。

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

它奏效了！每当我们#map对链表调用我们的方法时，我们都会得到一个与原始链表顺序相同的新链表。

使用枚举器进行链式枚举

通过#each链表类中实现的方法和包含的方法DIYEnumerator，我们现在可以双向循环并遍历链表。

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 }
=> [420, [120, [730]]]

但是，如果我们需要反向遍历列表呢？由于我们在遍历之前会先反转列表，所以返回的结果始终与原始列表的顺序相同。我们已经实现了 `map`#reverse_each和 ` #mapmap` 函数，因此应该能够将它们链接起来以实现反向遍历。幸运的是，Ruby 的 ` Enumeratormap` 类可以帮助我们做到这一点。

上次，我们确保在Kernel#to_enum方法LinkedList#each调用时没有使用代码块，从而能够通过返回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，我们的枚举器类是对对象上一个方法的封装。通过向上冒泡到被封装的对象，我们可以链式调用枚举方法。

之所以能做到这一点，是因为DIYEnumerator实例本身是可枚举的。它#each通过调用包装对象来实现，并且包含了DIYEnumerable模块，因此可以对其调用所有可枚举的方法。

DIYEnumerator如果没有向该方法传递任何代码块，我们将返回我们类的一个实例LinkedList#each。

class LinkedList
  # ...

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

使用我们自己的枚举器，我们现在可以链式枚举，以按原始顺序获得结果，而无需将空块传递给#reverse_each方法调用。

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

急切和懒惰的枚举

Enumerable至此，我们对模块和类的实现部分就结束了Enumerator。我们已经了解了一些可枚举方法的工作原理，以及枚举器如何通过包装可枚举对象来帮助链式调用枚举。

不过，我们的方法也存在一些问题。枚举本质上是急切的，这意味着一旦调用列表的枚举方法，它就会立即遍历该列表。虽然这在大多数情况下没有问题，但反向遍历列表会导致列表反转两次，这是不必要的。

为了减少循环次数，我们可以将Enumerator::Lazy循环延迟到最后一刻，让重复列表反转相互抵消。

不过，我们得把这个留到以后的节目里再讲。不想错过这些内容，以及对 Ruby 神奇内部运作机制的进一步探索吗？订阅Ruby Magic 电子邮件简讯，即可在文章发布后第一时间收到推送。