木、子→親

Schemeはまだまともに書けないのでGroovyで挑戦。

Tree = ['Root',
         ['Spine',
           ['Neck',
             ['Head']],
           ['RClavicle',
             ['RUpperArm',
               ['RLowerArm',
                 ['RHand']]]],
           ['LClavicle',
             ['LUpperArm',
               ['LLowerArm',
                 ['LHand']]]]],
         ['RHip',
           ['RUpperLeg',
             ['RLowerLeg',
               ['RFoot']]]],
         ['LHip',
           ['LUpperLeg',
             ['LLowerLeg',
               ['LFoot']]]]]

f1 = { def alist = [], f
  (f = {
    def p = it[0]
    it[1] && it[1..-1].each{ alist << [f(it), p] }
    p
  }) it
  alist
}
print f1(Tree)

> groovy tpc.groovy
[["Head", "Neck"], ["Neck", "Spine"], ["RHand", "RLowerArm"], ["RLowerArm", "RUp
perArm"], ["RUpperArm", "RClavicle"], ["RClavicle", "Spine"], ["LHand", "LLowerA
rm"], ["LLowerArm", "LUpperArm"], ["LUpperArm", "LClavicle"], ["LClavicle", "Spi
ne"], ["Spine", "Root"], ["RFoot", "RLowerLeg"], ["RLowerLeg", "RUpperLeg"], ["R
UpperLeg", "RHip"], ["RHip", "Root"], ["LFoot", "LLowerLeg"], ["LLowerLeg", "LUp
perLeg"], ["LUpperLeg", "LHip"], ["LHip", "Root"]]

def の挙動にはまって10分では解けなかった。

> groovy -e "def a = { print a }; a()"
Caught: groovy.lang.MissingPropertyException: No such property: a for class...

上のように書くとクロージャ生成の後で変数定義が成されるため，自身の名前を参照出来ず再帰にならないのだ。*1。

で，他の人の解答例を眺めていたらGroovyでもパターンマッチもどきが出来ることを思い出した。sumimさんにならってalistをMapに置き換えつつ書き直し。

f2 = { def pmap = [:], f
  (f = { name, ...tree ->
    tree.each{ pmap[f(*it)] = name }
    name
  })(*it)
  pmap
}

+

カコイイ。こういうの見るとLisp覚えねばと思う。Groovyに訳すと…

class foo {
  static Map bar(String n, List t, ...ts){
    [(t[0]): n, *: bar(*t), *: bar(n, *ts)]
  }
  static Map bar(List t){ bar(*t) }
  static Map bar(_){ [:] }
}
print foo.bar(Tree)

動くことは動くが冗長な感じ。

*1:JSは事前に var の評価をしておくので「var f = function()... 」が期待通りに動作する。