I tried to write a predicate that takes a list and converts it to a balanced tree. My code looks as follows:
/* 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 calling it in the other way, like:
?- make_tree(L, node(node(empty, empty, 2), node(empty, empty, 3), 1)).
false.
It's not really necessary, but I accepted the challenge anyway to make it work both ways. I wanted to solve this by using freeze/2
on split
, like freeze(T2, split(T, T1, T2))
and this makes that ?- make_tree(L, node(node(empty, empty, 2), node(empty, empty, 3), 1)).
works, but the original idea doesn't anymore. So actually what I'm looking for is some kind of freeze/2
that can do something like freeze((T;T2), split(T, T1, T2))
. Does anybody know how to solve this issue?
Thanks in advance
Most likely you are looking for
when/2
. It is offered by both SICStus Prolog (manual page) and SWI-Prolog (manual page).Sample use: