MEMO:はてな支店 このページをアンテナに追加 RSSフィード

2008-06-03

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

木構造が与えられる。

<tree> := (<name> <tree> ...) という構造。

これから、子→親の対応を表すalistを作る手続きを書け、というもの。

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

この問題をやってみた

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

(define foo (match-lambda
  ((_) ())
  ((p (c . cs) . ps) `(,(cons c p) ,@(foo (cons c cs)) ,@(foo (cons p ps))))))

実行結果

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

shiroshiro 2008/06/03 18:56 おお、これはエレガントだ。
(foo (cons c cs))のところは、パターンの方で (and (c . cs) ccs) としておけば (foo ccs) とできます (Haskellのas pattern)。まあ見やすいかどうかには疑問がありますが。

katonakatona 2008/06/04 03:43 shiroさんにそういわれるとうれしいです!
そうか、アズパターンはandで出来るんですね。