絶対アドレスと節の位置との相互変換

二分木の中のノードやリーフの位置は、lとrの系列で示している。が、語と語の距離をそのアドレスから計算するのがとてもややこしいプログラムになっていた。そこで、アドレスと語の位置を相互に交換できるようにした。

ベースにしたのは、次のような、二分木を平板に出力するプログラムだ。記録のために書いておく

print_top :-
    data(Tree),
    set_flag(location,0),
    print(Tree,[]).

print(Tree,Address):-
    atom(Tree),
    get_flag(location,No),
    format('~w(~w:~w), ',[Tree,No,Address]),
    asserta(address(Address,No)),
    No1 is No + 1,
    set_flag(location,No1).

print(Tree,Address):-
    node(N,L,R)=Tree,
    append(Address,[l],Address_l),
    append(Address,[r],Address_r),
    print(L,Address_l),print(N,Address),print(R,Address_r).

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

実行すると次のようになる。

?- print_top.
a(0:[l,l,l]), b(1:[l,l]), c(2:[l,l,r]), d(3:[l]), e(4:[l,r,l]), f(5:[l,r]), g(6:[l,r,r]), h(7:[]), i(8:[r,l,l]), j(9:[r,l]), k(10:[r,l,r]), l(11:[r]), m(12:[r,r,l]), n(13:[r,r]), o(14:[r,r,r]), 
true .

assertaでprologの説も構成している。