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

你的代碼的唯一變化（除了列入「圖書館」的）是-:-更換:-。我選擇了符號來建議雙向...