kmizuの日記

プログラミングや形式言語に関係のあることを書いたり書かなかったり。

与えられた木から，子→親への対応を作る，を Scalaで書いてみた

Scala

NyaRuRuさんの日記より引用：

流行っているっぽいのでやってみました．

与えられた木から、子→親への対応を作る

Shiro(2008/05/24 11:55:47 PDT): たまたま昨日、仕事で扱った小ネタ。初級編クイズになりそうなので書き留めておく。

木構造が与えられる。たとえばこんなの：

(define *tree*
  '(Root (Spine (Neck (Head))
                (RClavicle (RUpperArm (RLowerArm (RHand))))
                (LClavicle (LUpperArm (LLowerArm (LHand)))))
         (RHip (RUpperLeg (RLowerLeg (RFoot))))
         (LHip (LUpperLeg (LLowerLeg (LFoot))))))

つまり、 := ( ...) という構造。

これから、子→親の対応を表すalistを作る手続きを書け、というもの。結果の例はこんな感じ。各要素の順序は問わない。

((LHip . Root) (LUpperLeg . LHip) (LLowerLeg . LUpperLeg) (LFoot . LLowerLeg)
 (RHip . Root) (RUpperLeg . RHip) (RLowerLeg . RUpperLeg) (RFoot . RLowerLeg)
 (Spine . Root) (LClavicle . Spine) (LUpperArm . LClavicle)
 (LLowerArm . LUpperArm) (LHand . LLowerArm)
 (RClavicle . Spine) (RUpperArm . RClavicle)
 (RLowerArm . RUpperArm) (RHand . RLowerArm) (Neck . Spine) (Head . Neck))
http://practical-scheme.net/wiliki/wiliki.cgi?Scheme%3a%e3%83%aa%e3%82%b9%e3%83%88%e5%87%a6%e7%90%86#H-ne4pu7

これは確かに頻出問題っぽい気がします．

階層構造の表現として，汎用なツリーの他に，テーブル指向なストレージ向けのいくつかのツリー表現があって，今回の問題は汎用ツリーから「隣接リストモデル」への書き換えという感じでしょうか．

http://d.hatena.ne.jp/NyaRuRu/20080604/p1

なんか最近、こういうネタしか日記に書いてない気がするけど、とにかくScalaで解いてみた。まず、データ構造の定義。各ツリーは、名前と子ノードのリストを持っていると考えられるから、以下のようなクラス定義で。

case class Tree(name: Symbol, children: List[Tree])

ただ、これだけだと、ツリー構造を書き下すのが非常にしんどいので、簡単に書き下すためにimplicit conversionでメソッドを追加する。こういうときは、S式がリテラルとして書ける言語は便利でいいなあ、と思う。

class RichSymbol(sym: Symbol) {
  def apply(children: Any*) :Tree = {
    Tree(
      sym, children.toList.map{ case x:Symbol => Tree(x, Nil) case x:Tree => x }
    )
  }
}

implicit def toRichSymbol(sym: Symbol) = new RichSymbol(sym)

このように、Symbolにapplyメソッドをimplicit conversionで追加すると、以下のような感じでツリー構造を表記できる。これでもS式で書き下すのに比べるとやや面倒だけど、だいぶマシになった。

val tree = 
  'Root(
    'Spine(
      'Neck ('Head),
      'RClavicle ('RUpperArm ('RLowerArm ('RHand))),
      'LClavicle ('LUpperArm ('LLowerArm ('LHand)))
    ),
    'RHip('RUpperLeg ('RLowerLeg ('RFoot))),
    'LHip('LUpperLeg ('LLowerLeg ('LFoot))))

で、本題のプログラムだけど、これはTreeを引数に取って、List[(Symbol, Symbol)]を返すメソッドとして実装した。単純に、子ノードを引数にして再帰的に呼び出した結果をflatMapで結合しているだけなので、特に難しいところは無いと思う。

def makeAssocList(tree: Tree): List[(Symbol, Symbol)] = {
  tree.children.map{c => (c.name, tree.name)} ++
  tree.children.flatMap{makeAssocList(_)}
}

makeAssocList(tree).foreach(println)

実行結果。

('Spine,'Root)
('RHip,'Root)
('LHip,'Root)
('Neck,'Spine)
('RClavicle,'Spine)
('LClavicle,'Spine)
('Head,'Neck)
('RUpperArm,'RClavicle)
('RLowerArm,'RUpperArm)
('RHand,'RLowerArm)
('LUpperArm,'LClavicle)
('LLowerArm,'LUpperArm)
('LHand,'LLowerArm)
('RUpperLeg,'RHip)
('RLowerLeg,'RUpperLeg)
('RFoot,'RLowerLeg)
('LUpperLeg,'LHip)
('LLowerLeg,'LUpperLeg)
('LFoot,'LLowerLeg)

追記：

そういえば、解くのにかかった時間は測ってなかった。たぶん、makeAssocListの部分は5分くらいだったと思うけど、木構造を書き下すところで、どうすれば書きやすくなるかあれこれ悩んで、そこで30分くらい費やした気がする。最初、Tree('Root, ...)のようにして書いていたが、書きづらいし見づらいなあと思って、'Root --> ...のように中置演算子を使って書くようにしてみたんだけど、やっぱりこれでも見づらいなあ、ということで最終的に'Root(...)のような形式に落ち着いたのであった。その点、S式なら、と思わなくも無いんだけど、素のS式だと、プログラマの意図(ここでは、S式中のどの部分がノード名で、どの部分が子ノードか、などの情報)が抜け落ちてしまうのがあまり好きじゃなかったりする。