프롤로그에서 inorder 열거

Question

inorder 목록을 다시 BST로 바꾸어 인버스 순회를 "되돌리기"하고 있습니다.

BST를 술어 양식 node(Value,Left,Right) 또는 leaf이 있으므로 빈 나무는, 하나 개의 노드를 가진 나무는 node(_,leaf,leaf) 단지 leaf입니다.

술어 enumerate_bst(Elems,Bst)이 주어지면 Bst을 inorder 목록 Elems의 모든 가능성에 일치시키는 것이 목표입니다. 예를 들어 (주 setof/3)의 경우 : I 시도

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를의에

이미 주어진 BST 일치하는 조건이 있습니다

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

내가 할 노력은 무엇 역순으로 목록에 넣음으로써 사용하는 것이지만, 이것은 하나의 결과만을 반환합니다. 나는 정확히 그 이유를 모르겠습니다. 나는 현재 내가 역에 기본 조건 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)).

두 가지 목표를 우선적으로 두어 목표를 재정렬하는 것이 가장 이상적입니다. That works (즉, 두 번째 인수가 끝나면 끝납니다.) 프로그램은 이제 목록의 요소를 트리로 배포하기 위해 만 배포하기 때문에 상당히 만족스럽지 않습니다.

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

제 1 또는 제 2 인수는 접지 경우 inorder/2 종료한다고 : 여기

는 종단 조건에 의해 지시 된 바와 같이 both ways 작동 버전이다.

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. 

합니다 ('라이브러리'를 포함 떨어져) 코드의 유일한 변화는 -:-와 :-의 교체입니다. 양방향성을 제안하기 위해 심볼을 선택했습니다 ...