部分的に具体化

Tech Prolog

「フィジカルを鍛える練習問題：二分探索木」で作ったプログラムを「部分的に具体化」を使うように修正してみました．
一番肝心な (？) add_value/3 はこんな感じになりました．

add_value(Value, Node, node(Value, _, _)) :-
	var(Node).
add_value(Value, Node, Node) :-
	get_value(Node, Value).
add_value(Value1, Node, Node) :-
	get_value(Node, Value2),
	Value1 < Value2,
	get_left(Node, Left),
	add_value(Value1, Left, Left).
add_value(Value1, Node, Node) :-
	get_value(Node, Value2),
	Value1 > Value2,
	get_right(Node, Right),
	add_value(Value1, Right, Right).

最初の節以外は第 2 引数と第 3 引数が同じ．なので，ツリーのコピーは行われていないはず．
ちなみに旧版はこんな感じでした．

add_value(Value, nil, node(Value, nil, nil)).
add_value(Value, Node, Node) :-
	get_value(Node, Value).
add_value(Value1, node(Value2, Left, Right), node(Value2, Left2, Right)) :-
	Value1 < Value2,
	add_value(Value1, Left, Left2).
add_value(Value1, node(Value2, Left, Right), node(Value2, Left, Right2)) :-
	Value1 > Value2,
	add_value(Value1, Right, Right2).

大きく違うのは 3 番目の節と 4 番目の節．ツリーに新しいノードを追加する場合，こちらは再帰的に新しいノードを作成しています．
この旧版だと例えば．．．

2 ?- add_value(3, _, N1), add_value(2, N1, N2), add_value(1, N2, N3), add_value(4, N3, N4), add_value(5, N4, N5).

N1 = node(3, nil, nil)
N2 = node(3, node(2, nil, nil), nil)
N3 = node(3, node(2, node(1, nil, nil), nil), nil)
N4 = node(3, node(2, node(1, nil, nil), nil), node(4, nil, nil))
N5 = node(3, node(2, node(1, nil, nil), nil), node(4, nil, node(5, nil, nil))) 

Yes

というように，ツリーに要素を追加するたびに新たなツリーを作成している様子が窺えます．
一方新版だと，

5 ?- add_value(3, _, N1), add_value(2, N1, N2), add_value(1, N2, N3), add_value(4, N3, N4), add_value(5, N4, N5).

N1 = node(3, node(2, node(1, _G1034, _G1035), _G1031), node(4, _G1038, node(5, _G1042, _G1043)))
N2 = node(3, node(2, node(1, _G1034, _G1035), _G1031), node(4, _G1038, node(5, _G1042, _G1043)))
N3 = node(3, node(2, node(1, _G1034, _G1035), _G1031), node(4, _G1038, node(5, _G1042, _G1043)))
N4 = node(3, node(2, node(1, _G1034, _G1035), _G1031), node(4, _G1038, node(5, _G1042, _G1043)))
N5 = node(3, node(2, node(1, _G1034, _G1035), _G1031), node(4, _G1038, node(5, _G1042, _G1043))) 

Yes

と，最終的には全てのツリーが同じになっています．ツリーに要素を追加しても新たなツリーが作成されていないということが分かります．
やったね！！


でもでも，ツリーから要素を削除する場合をどうすればいいかが分からない．．．
一度具体化した変数をもう一度具体化されていない変数に戻すなんてあり得ないような気のせいが．
ってことは，削除の場合はツリーのコピーを作るしかないのだろうか？ うーみゅ．．．