在Prolog中枚举序列号

Question

我试图通过将序列列表重新转换为BST来“颠倒”序列遍历。

BST的谓词形式为node(Value,Left,Right)或leaf，所以空树只是leaf，一个节点的树是node(_,leaf,leaf)。

给定谓词enumerate_bst(Elems,Bst)，目标是将Bst与排序列表Elems的所有可能性匹配。例如（注setof/3）：

?- setof(Bst,enumerate_bst([],Bst),Enum). 
Enum = [leaf]. 

?- setof(Bst,enumerate_bst([1,2],Bst),Enum). 
Enum = [ 
    node(1, leaf, node(2, leaf, leaf)), 
    node(2, node(1, leaf, leaf), leaf) 
]. 

?- setof(Bst,enumerate_bst([1,2,3],Bst),Enum). 
Enum = [ 
    node(1, leaf, node(2, leaf, node(3, leaf, leaf))), 
    node(1, leaf, node(3, node(2, leaf, leaf), leaf)), 
    node(2, node(1, leaf, leaf), node(3, leaf, leaf)), 
    node(3, node(1, leaf, node(2, leaf, leaf)), leaf), 
    node(3, node(2, node(1, leaf, leaf), leaf), leaf) 
]. 

我试图这样做：

我已经有一个给定的BST相匹配的谓词是序列表：

inorder(leaf,[]). 
inorder(node(X,L,R),Elems) :- 
    inorder(L,Elems_L), 
    inorder(R,Elems_R), 
    append(Elems_L,[X],Tmp), 
    append(Tmp,Elems_R,Elems). 

我试着通过在列表中反向使用它，但这只返回一个结果，我不完全确定为什么。

什么我正在尝试做

我试图使用本地谓词append/3反向，但不能完全确定这将如何做。

任何想法，以最好的方式来做到这一点？谢谢！

Answer 1

反过来，你的程序不会终止。考虑：

?- inorder(Tree, []). 
    Tree = leaf 
; **LOOPS** 

我们希望它只是显示这个唯一的解决方案，然后停止。 实际的原因是你的程序的以下片段 - 一个failure-slice。没有必要再看比这更进一步。换句话说，根本不需要了解append/3。

 
?- inorder(Tree, []), false. 

inorder(leaf,[]) :- false. 
inorder(node(X,L,R),Elems) :- 
    inorder(L,Elems_L), false. 
    inorder(R,Elems_R), 
    append(Elems_L,[X],Tmp), 
    append(Tmp,Elems_R,Elems). 

首先，这个片段需要终止（并失败）。只有这样你才可以考虑终止整个程序。在这个片段中，第二个参数（Elems）完全被忽略！对此感兴趣的第一个目标是最后一个目标（append(Tmp,Elems_R,Elems)）。

一个天真的出路将重新排序的目标，把两个append/3目标第一。 That works（也就是说，它终止了第二个参数），但是它很不令人满意，因为该程序现在专门将列表的元素分配到树只有。

这里是由终止条件所指示的作品both ways一个版本：其中指出inorder/2终止如果第一或第二参数是接地

inorder(A,B)terminates_if b(A);b(B). 

。

inorder(Tree, Xs) :- 
    phrase(inorder(Tree, Xs,[]), Xs). 

inorder(leaf, Vs,Vs) --> 
    []. 
inorder(node(X,L,R), [_|Vs0],Vs) --> 
    inorder(L, Vs0,Vs1), 
    [X], 
    inorder(R, Vs1,Vs). 

Answer 2

前一段时间我写了一个“library”这项任务。使用：

:- use_module(carlo(snippets/when_)). 

inorder(leaf,[]). 
inorder(node(X,L,R),Elems) -:- 
    inorder(L,Elems_L), 
    inorder(R,Elems_R), 
    append(Elems_L,[X],Tmp), 
    append(Tmp,Elems_R,Elems). 

然后

?- inorder(T,[1,2,3]). 
T = node(1, leaf, node(2, leaf, node(3, leaf, leaf))) ; 
T = node(1, leaf, node(3, node(2, leaf, leaf), leaf)) ; 
T = node(2, node(1, leaf, leaf), node(3, leaf, leaf)) ; 
T = node(3, node(1, leaf, node(2, leaf, leaf)), leaf) ; 
T = node(3, node(2, node(1, leaf, leaf), leaf), leaf) ; 
false. 

你的代码的唯一变化（除了列入“图书馆”的）是-:-更换:-。我选择了符号来建议双向...