アドレスという考え方: prolog二分木

自然言語のprolog二分木の中をもっと自由に移動する方法がないかと考えてきたが、アドレスを入れることにした。

二分木はルートを持っている。このルートが原点となる。linuxなどのディレクトリ構造のルートと同じである。ただ、二分木であるから、分岐は全てバイナリである。

そこで、ルートから出発して、左の葉をたどる時には'l'（エル）を加え、右をたどる時には'r'を加えたprologリストを作成することによって、唯一のアドレスを与えることができる。

仮想的な二分木を考える。

node(a,
    node(b,
        node(c,
            d,
            e
        ),
        node(f,
            g,
            h
        )
    ),
    node(i,
        node(j,
            k,
            l
        ),
        node(m,
            n,
            o
        )
    )
)

ルートの値は、aである。左右対称のツリーになっている。これに対し、アドレス[l,r,l]は、値gとなる。あるいは、[l,r]にあるのはサブツリーで、node(f, g, h)である。同じく、[r,l]にあるのは、node(j, k, l)となる。

このように、そのアドレスの部分ツリーを取ってくるプログラムは次のようになる。

%% 現在位置（ツリーアドレス）からの部分ツリーを返す
getsubtree(Tree,[],Tree).  %% 位置が空だったら、そのものを返す
getsubtree([],_,[]).
getsubtree(node(_,L,R),[H|T],Out) :- 
        (T=[] -> 
            (H=l -> Out=L; Out=R)
        ;   (H=l -> getsubtree(L,T,Out)
            ;getsubtree(R,T,Out),
            true)
        ).