冻结多个变量

Question

我尝试编写一个谓词，它接受一个列表并将其转换为平衡树。我的代码如下所示：

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

这不是真的必要，但我还是接受了挑战，让它双向工作。我想通过在 split 上使用 freeze/2 来解决这个问题，例如 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)) 的事情。有人知道如何解决这个问题吗？

提前致谢

Answer 1

您很可能正在寻找 when/2。它由 SICStus Prolog (manual page) and SWI-Prolog (manual page) 提供。

示例使用：

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

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

Answer 2

这是一种不使用协程的方法。这个想法是首先建立树与其元素的 number 之间的关系，该关系由列表表示。请注意，我们首先不查看具体元素 (_)，因为我们还不知道它们的顺序。在固定元素数量的情况下，我们可以像以前一样进行但没有削减。

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 对于所有可能的树都会成功，无论它们是否平衡。

冻结多个变量

freeze for more than one variable

prolog

prolog-coroutining