Rubyで独自に作成したクラスにeachメソッドを定義する場合について

Question

前提・実現したいこと

こんにちは。
プログラミング初心者なのですが、Rubyの練習問題を解いていてわからないところが出てきてしまったので質問させていただきました。

以下の問題は二分探索木の問題で、解答例を見ていて理解できていない部分を見つけました。

Rubyで独自にクラスを作成した場合、そのクラスのインスタンスメソッドとしてeachメソッドは定義されていないため、使いたい場合は自分で定義する必要があるということは分かるのですが、ここで定義されているBst#eachの仕組みがよく分からないです。
なぜ、Bst#each内では@leftに対してeachを呼び出すことで@leftに入ったBstクラスのインスタンス変数である@dataの２を取り出すことができるのでしょうか？
ためしにBst#each内で、self.each(&block)としてみたのですが、SystemStacErrorが発生してしまいました。SystemStacErrorはなぜ@left.eachの場合は発生しないのでしょうか？

発生している問題・エラーメッセージ

エラーなし

該当のソースコード

# Binary Search Tree

Insert and search for numbers in a binary tree.

When we need to represent sorted data, an array does not make a good
data structure.

Say we have the array `[1, 3, 4, 5]`, and we add 2 to it so it becomes
`[1, 3, 4, 5, 2]` now we must sort the entire array again! We can
improve on this by realizing that we only need to make space for the new
item `[1, nil, 3, 4, 5]`, and then adding the item in the space we
added. But this still requires us to shift many elements down by one.

Binary Search Trees, however, can operate on sorted data much more
efficiently.

A binary search tree consists of a series of connected nodes. Each node
contains a piece of data (e.g. the number 3), a variable named `left`,
and a variable named `right`. The `left` and `right` variables point at
`nil`, or other nodes. Since these other nodes in turn have other nodes
beneath them, we say that the left and right variables are pointing at
subtrees. All data in the left subtree is less than or equal to the
current node's data, and all data in the right subtree is greater than
the current node's data.

For example, if we had a node containing the data 4, and we added the
data 2, our tree would look like this:

      4
     /
    2

If we then added 6, it would look like this:

      4
     / \
    2   6

If we then added 3, it would look like this

       4
     /   \
    2     6
     \
      3

And if we then added 1, 5, and 7, it would look like this

          4
        /   \
       /     \
      2       6
     / \     / \
    1   3   5   7

* * * *

class Bst
  attr_reader :data, :left, :right

  def initialize(data)
    @data = data
  end

  def insert(data)
    data > @data ? self.go_right(data) : self.go_left(data)
  end

  def go_right(data)
    @right ? @right.insert(data) : @right = Bst.new(data)
  end

  def go_left(data)
    @left ? @left.insert(data) : @left = Bst.new(data)
  end

  def each(&block)
    return enum_for(:each) unless block_given?
    @left.each(&block) if @left
    block.call(data)
    @right.each(&block) if @right
  end
end

require 'minitest/autorun'
require_relative 'binary_search_tree'

class BstTest < Minitest::Test
  def test_data_is_retained
    assert_equal 4, Bst.new(4).data
  end

  def test_inserting_less
    #skip
    four = Bst.new 4
    four.insert 2
    assert_equal 4, four.data
    assert_equal 2, four.left.data
  end

  def test_inserting_same
    #skip
    four = Bst.new 4
    four.insert 4
    assert_equal 4, four.data
    assert_equal 4, four.left.data
  end

  def test_inserting_right
    #skip
    four = Bst.new 4
    four.insert 5
    assert_equal 4, four.data
    assert_equal 5, four.right.data
  end

  def test_complex_tree
    #skip
    four = Bst.new 4
    four.insert 2
    four.insert 6
    four.insert 1
    four.insert 3
    four.insert 7
    four.insert 5
    assert_equal 4, four.data
    assert_equal 2, four.left.data
    assert_equal 1, four.left.left.data
    assert_equal 3, four.left.right.data
    assert_equal 6, four.right.data
    assert_equal 5, four.right.left.data
    assert_equal 7, four.right.right.data
  end

  def record_all_data(bst)
    all_data = []
    bst.each { |data| all_data << data }
    all_data
  end

  def test_iterating_one_element
    #skip
    assert_equal [4], record_all_data(Bst.new(4))
  end

  def test_iterating_over_smaller_element
    #skip
    four = Bst.new 4
    four.insert 2
    assert_equal [2, 4], record_all_data(four)
  end

  def test_iterating_over_larger_element
    #skip
    four = Bst.new 4
    four.insert 5
    assert_equal [4, 5], record_all_data(four)
  end

  def test_iterating_over_complex_tree
    #skip
    four = Bst.new 4
    four.insert 2
    four.insert 1
    four.insert 3
    four.insert 6
    four.insert 7
    four.insert 5
    assert_equal [1, 2, 3, 4, 5, 6, 7], record_all_data(four)
  end

  def test_each_returns_enumerator_if_no_block
    #skip

    tree = Bst.new 4
    [2, 1, 3, 6, 7, 5].each { |x| tree.insert x }
    each_enumerator = tree.each

    assert_kind_of Enumerator, each_enumerator

    (1..7).each { |x| assert_equal(x, each_enumerator.next) }

    assert_raises(StopIteration) { each_enumerator.next }
  end
end

試したこと

ここに問題に対して試したことを記載してください。

補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください。

Answer 1

SystemStackErrorとは、メソッド呼び出しが多すぎて
仮引数を置く場所がなくなった時にでる一種の無限ループ的なエラーです。

インスタンスメソッドeachからself.eachを呼び出すということは

def m
  m
end

と同じなのでメソッドを呼び出し続けて終わりません。

一方、@leftをたどっていくと、そのうち未初期化にたどり着きます。

初期化されていない インスタンス変数を参照した時の値はnil

なので、@left.each(&block) if @leftは、条件を満たさず実行されないときがいつか来ます
そしたら、自身をブロックに渡し(block.call(data))ます。

---

追記
値を取り出せる事を不思議がってるようなので簡単にしてみます。

class Val
  def initialize(val)
    @val = val
  end
  def each(&blk)
    blk.call @val
  end
end

Val.new(100).each{|el| p el} # => 100

クラスValは値１つを保持し、Val#eachメソッドは保持してる値を引数としてブロックを呼び出します。

次に連結リストを考えます。

class LinkedList
  def initialize(val)
    @val = val
  end
  def <<(val)
    @link = LinkedList.new val
  end
  def each(&blk)
    blk.call(@val)
    @link.each(&blk) if @link
  end
  def rev_each(&blk)
    @link.rev_each(&blk) if @link
    blk.call(@val)
  end
end

ll = LinkedList.new(1)
ll << 2 << 3 << 4 << 5
pp ll
# => #<LinkedList:0x0000000006a9e128
#    @link=
#     #<LinkedList:0x0000000006b7f8d0
#      @link=
#       #<LinkedList:0x0000000006b7f880
#        @link=
#         #<LinkedList:0x0000000006b7f858
#          @link=#<LinkedList:0x0000000006b7f830 @val=5>,
#          @val=4>,
#        @val=3>,
#      @val=2>,
#    @val=1>

ll.each{|el| p el}
# => 1
#    2
#    3
#    4
#    5
ll.rev_each{|el| p el}
# => 5
#    4
#    3
#    2
#    1

@valをブロックに渡した後に
@listが偽でないならば@listのメソッドも同様にeachメソッドを呼び出してやる事で
値を取り出していく事ができます。

Comments

[sachatete]

回答ありがとうございます！
処理を順に追って理解するのに少し時間がかかりそうなので、よろしければまた質問させて頂けると嬉しいです。

一つ別の疑問が浮かんだのですが、なぜ Array#eachを持っていないBst#each ではBstクラスのインスタンスを一つずつ取り出すことができるのでしょうか？
Array#each とここで使われている Bst#each は全く別物という解釈は正しいでしょうか？
インスタンス変数からインスタンス自身を取り出すような処理は書いていないように見えるので混乱してしまいました。

[asm]

> Array#each とここで使われている Bst#each は全く別物
別物ですが、
「メソッド名がeachで結果が値を一つずつ取り出してブロックに投げる」
のでRuby的にはあんまり区別する必要はないですね(強いて言えば戻り値が違いますが)

あるBstインスタンスの
leftには自身より小さい値のBstインスタンスが
rightには自身よりも大きい値のBstインスタンスが
格納されています

自身の値を取り出してブロックへ投げた後に、rightへも同様にしろと命令すると
取り出される値はどんどん大きくなっていくでしょう。

そんな感じです

[sachatete]

納得することができました！！！
eachの中でeachを呼び出す時にレシーバがどんどん変わって行くのですね。
丁寧な説明ありがとうございました、とても助かりました！

Answer 2

    @left.each(&block) if @left
    block.call(data)
    @right.each(&block) if @right

は、 left を each で処理してから、 data を処理して、 right を each で処理しています。
そのあたりのことは参考にしているテキストで説明がされているはずとおもいます。

self.each(&block)　は対象操作が全然進んでいかないので stack over flow となってしまいます。
処理対象が小さくなっていくことで、再帰処理が tree の末端まで進み return してくるようになっていることが重要です。

Comments

[sachatete]

回答ありがとうございます！