Freeze for multiple variables
I tried to write a predicate that takes a list and converts it to a balanced tree. My code looks like this:
/* make_tree(list, tree)
*
* list: list with the elements of the tree in prefix order
* tree: balanced tree of the elements in the list
*
*/
make_tree([], empty).
make_tree([H|T], node(L, R, H)):-
split_half(T, T1, T2),
make_tree(T1, L),
make_tree(T2, R).
/* split_half(list, first, second)
*
* list: list with n elements
* first: list with first (n // 2) elements
* second: list with last (n - n // 2) elements
*
*/
split_half(L, L1, L2):-
split_half(L, L, L1, L2).
split_half(L, [], [], L):- !.
split_half(L, [_], [], L):- !.
split_half([H|T], [_,_|Acc], [H|L1], L2):-
split_half(T, Acc, L1, L2).
and this works when called like:
?- make_tree([1,2,3], Tree).
Tree = node(node(empty, empty, 2), node(empty, empty, 3), 1).
but it doesn't work when you call it in another way like:
?- make_tree(L, node(node(empty, empty, 2), node(empty, empty, 3), 1)).
false.
It's not necessary, but I took the challenge anyway to make it work both ways. I wanted to solve this using freeze/2
on split
for example freeze(T2, split(T, T1, T2))
and it does the job ?- make_tree(L, node(node(empty, empty, 2), node(empty, empty, 3), 1)).
, but the original idea no longer exists. So actually what I'm looking for is freeze/2
one that can do something like freeze((T;T2), split(T, T1, T2))
. Does anyone know how to fix this problem?
Thank you in advance
source to share
Most likely you are looking for when/2
. He offered as SICStus Prolog ( reference page ) and SWI-Prolog ( manual page ).
Using example:
myfreeze1(V,Goal) :-
when(nonvar(V),Goal).
myfreeze2(V1,V2,Goal) :-
when((nonvar(V1);nonvar(V2)),Goal).
source to share
Here's a method without using accompanying documentation. The idea is to first establish the relationship between the tree and the number of its elements, which is represented by the list. Note that we are not looking at specific elements ( _
) first, as we do not yet know their order. With a fixed number of elements, we can proceed as before, but without cuts.
list_tree(Xs, Tree) :-
phrase(tree_els(Tree), Xs),
make_tree(Xs, Tree).
tree_els(empty) -->
[].
tree_els(node(L, R, _)) -->
[_],
tree_els(L),
tree_els(R).
This version can benefit from processing for performance reasons. In the end, it tree_els/1
will be successful for all possible trees, whether balanced or not.
source to share