質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.48%

  • Ruby

    9614questions

    Rubyはプログラミング言語のひとつで、オープンソース、オブジェクト指向のプログラミング開発に対応しています。

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

解決済

回答 2

投稿

  • 評価
  • クリップ 0
  • VIEW 280

sachatete

score 8

 前提・実現したいこと

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

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

Rubyで独自にクラスを作成した場合、そのクラスのインスタンスメソッドとしてeachメソッドは定義されていないため、使いたい場合は自分で定義する必要があるということは分かるのですが、ここで定義されているBst#eachの仕組みがよく分からないです。
なぜ、Bst#each内では@leftに対してeachを呼び出すことで@leftに入ったBstクラスのインスタンス変数である@dataの2を取り出すことができるのでしょうか?
ためしに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/ツールのバージョンなど)

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

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

checkベストアンサー

+2

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は値1つを保持し、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メソッドを呼び出してやる事で
値を取り出していく事ができます。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/09/08 23:26

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

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

    キャンセル

  • 2018/09/09 00:45

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

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

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

    そんな感じです

    キャンセル

  • 2018/09/09 08:34

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

    キャンセル

+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 してくるようになっていることが重要です。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/09/08 23:27

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

    キャンセル

同じタグがついた質問を見る

  • Ruby

    9614questions

    Rubyはプログラミング言語のひとつで、オープンソース、オブジェクト指向のプログラミング開発に対応しています。