与えられた木から，子→親への対応を作る，を C# で

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

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

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))))))

つまり、 <tree> := (<name> <tree> ...) という構造。

これから、子→親の対応を表す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))

30分で初級。10分で中級。

これは確かに頻出問題っぽい気がします．
階層構造の表現として，汎用なツリーの他に，テーブル指向なストレージ向けのいくつかのツリー表現があって，今回の問題は汎用ツリーから「隣接リストモデル」への書き換えという感じでしょうか．
「隣接リストモデル」の他にも，「入れ子集合モデル」や「経路列挙モデル」を聞いたことがあります．あまり本格的に使ったことはありませんが．

• 隣接リストモデル (Adjacency List Model)
• 入れ子集合モデル (Nested Set Model)
• 経路列挙モデル (Path Emuneration Model)

さて，「隣接リストモデル」で定義されたツリーに対して再帰処理を行う C# 関数群は『ToLookup の基本と応用 - NyaRuRuの日記』で既に用意してあります．今回の問題は，その少し見方を変えたバージョンと言えるかもしれません．

頻出再帰構造のパターン化

C# の場合，遅延評価の恩恵も末尾再帰の最適化の恩恵も基本的に受けることができないため，関数の再帰は何かと不自由です．必然的に，C# でのアプローチは，頻出再帰構造はとにかく事前に関数化しておいてのカウンター戦略に偏ることになります．(本当は再帰形も関数形も両方自由に使える方がいいのでしょうけど)
さて，f:a->[a] という関数 f (C# 風に書けば Func<T, IEnumerable<T>> f;) に注目し，これを深さ優先に unfold していく感じの CascadeDepthFirst と，幅優先に unfold していく感じの CascadeBreadthFirst というふたつの関数が拙作 Achiral に用意されています．つまり，f:a->[a] という関数形に当てはまる関数であれば，何でも一発で再帰させることができるわけです．unfold 自身，幅優先探索 CascadeBreadthFirst の特殊系とみなせます．
CascadeBreadthFirst，CascadeBreadthFirst，いずれの関数も末尾再帰の最適化に相当することを手動で行っており，不要になったデータはすぐに捨てるように実装してあります．どうしても保持しておく必要がある探索途中のテンポラリデータについても，全てヒープに確保されるようになっているので，ネストレベルが増加しても，関数の呼び出しスタックがあふれることはありません．もちろん yield による遅延評価も行っているので，探索中止条件を後段に分離することが可能です．
今回の問題であれば，(tree, tree) という tuple から [(tree, tree)] という tuple のリストを返す関数を考えると良さそうです．ここで tuple の第一要素を注目しているノードそのもの，第二要素を注目しているノードの親ノードとしましょう．つまりは (theNode, parent) を受け取って，theNode の全ての子要素について同種の tuple を返す関数を考えるわけです．C# 3.0 のラムダ式で書けばこんな感じになるでしょう．

(Tuple<Tree<string>, Tree<string>> pair) => pair.Item1.Select(child => Make.Tuple(child, pair.Item1))

Achiral では Func<T, IEnumerable<T>> というデリゲートにマッチする Extension Methods が定義してあります．
以下に全ソースを示します．ビルドには Achiral 1.1.0.0 が必要です．

using System;
using System.Linq;
using System.Collections.Generic;
using Achiral;
using Achiral.Extension;

using ST = Tree<string>;
public class Tree<T> : List<Tree<T>>
{
    public readonly T Value;
    public Tree(T value, params Tree<T>[] children)
    {
        this.Value = value;
        this.AddRange(children);
    }
}

static class Program
{
    static void Main(string[] args)
    {
        var root =
        new ST("Root",
            new ST("Spine",
                new ST("Neck",
                    new ST("Head")),
                new ST("RClavicle",
                    new ST("RUpperArm",
                        new ST("RLowerArm",
                            new ST("RHand")))),
                new ST("LClavicle",
                    new ST("LUpperArm",
                        new ST("LLowerArm",
                            new ST("LHand"))))),
            new ST("RHip",
                new ST("RUpperLeg",
                    new ST("RLowerLeg",
                        new ST("RFoot")))),
            new ST("LHip",
                new ST("LUpperLeg",
                    new ST("LLowerLeg",
                        new ST("LFoot"))))
        );

        // Item1 := the node, Item2 := parent
        Make.Func((Tuple<ST, ST> pair)
                => pair.Item1.Select(child => Make.Tuple(child, pair.Item1)))
            .CascadeDepthFirst(Make.Tuple(root, default(ST)))
            .Where(pair => pair.Item2 != null)
            .ConsoleWriteLine(pair => string.Format("{0} . {1}", pair.Item1.Value, pair.Item2.Value));
    }
}

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