Заморозить для более чем одной переменной

Я попытался написать предикат, который берет список и преобразует его в сбалансированное дерево. Мой код выглядит следующим образом:

/* 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).

и это работает, когда вызывается как:

?- make_tree([1,2,3], Tree).
Tree = node(node(empty, empty, 2), node(empty, empty, 3), 1).

но это не работает при вызове его другим способом, например:

?- make_tree(L, node(node(empty, empty, 2), node(empty, empty, 3), 1)).
false.

В этом нет необходимости, но я все равно принял вызов, чтобы он работал в обоих направлениях. Я хотел решить эту проблему с помощью freeze/2 на split, лайк freeze(T2, split(T, T1, T2)) и это делает это ?- make_tree(L, node(node(empty, empty, 2), node(empty, empty, 3), 1)). работает, но оригинальная идея больше не работает. Так что на самом деле я ищу какой-то freeze/2 что может сделать что-то вроде freeze((T;T2), split(T, T1, T2)), Кто-нибудь знает, как решить эту проблему?

заранее спасибо

2 ответа

Решение

Скорее всего, вы ищете when/2, Он предлагается как SICStus Prolog ( страница руководства), так и SWI-Prolog ( страница руководства).

Образец использования:

myfreeze1(V,Goal) :-
   when(nonvar(V),Goal).

myfreeze2(V1,V2,Goal) :-
   when((nonvar(V1);nonvar(V2)),Goal).

Вот метод без использования сопрограмм. Идея состоит в том, чтобы сначала установить связь между деревом и количеством его элементов, которые представлены списком. Обратите внимание, что сначала мы не смотрим на конкретные элементы (_) так как мы еще не знаем их порядок. С фиксированным количеством элементов мы можем продолжать работу, как и раньше, но без разрезов.

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).

Эта версия может получить выгоду от сопрограмм по соображениям производительности. В конце концов tree_els/1 удастся для всех возможных деревьев, будь они сбалансированы или нет.

Другие вопросы по тегам