概要
階層が浅い順に左から1,(2,3),(4,5,6,7),...と詰められた2分木がある。これを先行順巡回し指定番目のノードを答えよ。
解答の出自
この問題の回答に行き着くまでの経緯は以下の通りである。
CodeIQ 結城先生のTriany問題
Triany Low Level Interface(TLLI)およびDICT Interface(DICTI)を実装する問題。
「ウチに来ない？」(企業が管理者ページから評価を閲覧できる)問題であり、コードのインターフェース部を含めて評価されるものであった。
DICTIは実際にはどういうデータ構造でもよく、線形リストでも良かったのだが、2分木で解くことにした。
多分初めての木構造の実装だと思う。
AOJの2分木問題(ALDS1 8A/8B)
TrianyのDICTI(Dict-Interface)を派生させて解いた。DICTではなくSETでよかったのでTrianyの範疇でもそこそこくどくなく書けたらしい。
AOJの2分木問題(巡回のみ)(ALDS1 7C)
BioRuby(Bio::Tree)を用いて解いた。RosalindでBioRubyを多用していた1ためその流れ。
ALDS1 7Cを標準機能のみで
C++で解くと同時にRubyでも標準機能だけで解いた。2
https://github.com/cielavenir/procon/commit/d3b38f9115e924a2b531013026a3902b7b2be734
表題、yieldに変形
リストを返す再帰関数
なぜここまで長々と経緯を書いたかというと、この答案の原型は巡回結果を出力するのみであり、値を返すものではなかったということを述べるためである。
さてリストを返す関数の再帰は思ったよりも面倒である。C++で値を返すためには返値用の配列を持って回るのが一般的であるが。Ruby(やPython)には別の手段がある。 yield である。Pythonでは、(Python3であれば) yield from を使えば良い。しかし、Rubyにはyield fromは存在しない。
しかし擬似的にyield fromを実現することは可能である。具体的には、以下の3要素で構成される(はずだった。後述)。
- block_given? を確認し、偽ならEnumerator化する
- 返す要素を yield する
- 再帰時に &proc を渡し、再帰先でのyieldにより親のブロックが実行されるようにする。再帰においては最も肝要な要素である。
&proc
残念ながら&procの表記法はRuby 3.0で使えなくなった。 ブロックを渡したいなら明示的にブロックを引数として受けよということである。であれば、yieldとはなんなのだろうか。
まず、Pythonにおいて、yield fromは本来必要ではない。以下の2つは同じものである3。
yield from rec()
for e in rec(): yield e
また、Rubyにおいてyieldは必要ではない。以下の4つは同じものである(f1はRuby 3.0では動作しないが)。
def f1(n)
return to_enum(:f1, n) if !block_given?
return if n<=0
yield n
f1(n-1,&proc)
end
def f2(n, &blk)
return to_enum(:f2, n) if !block_given?
return if n<=0
blk.call(n)
f2(n-1, &blk)
end
def f2x(n, &blk)
blk or return to_enum(:f2x, n)
return if n<=0
blk.(n)
f2x(n-1, &blk)
end
def f3(n)
return to_enum(:f3, n) if !block_given?
return if n<=0
yield n
f3(n-1){|e|yield e}
end
blk.callの糖衣構文としてyieldが用意されたのであるという理解でいる。
ならば、Sub-Enumeratorへの移譲を(blk変数無しで)行えるようにすべきであると信じる。(f2xで)blkのnil判定に取って代わられた4block_given?は不遇。