Попытка распечатать предварительный заказ в прологе

Question

Я внедряю двоичное дерево поиска в пролог и пытаюсь получить распечатки для каждого типа обхода, preOrder, inOrder и postOrder.

Мое тестовое дерево:bst(bst(bst(empty,2,empty),4,empty),5,bst(bst(empty,6,empty),8,empty)).

Вот что у меня так далеко:

preOrder(bst(_,X,_)) :- write(X).
preOrder(bst(L,_,_)) :- preOrder(L).
preOrder(bst(_,_,R)) :- preOrder(R).

И это работает, но пользователь должен нажать пробел, чтобы получить каждый элемент.

5
True
4
True
2
True
8
True
6
False

Я бы предпочел распечатать в форме 5 4 2 8 6

Поэтому я изменил код выше, чтобы:

preOrder(bst(L,X,R)) :- write(X), write(" "), preOrder(L), preOrder(R).

Теперь это только распечатывает 5 4 2 false

Я довольно новичок в прологе, может кто-нибудь объяснить, почему добавление отдельных предикатов в один предикат действует не так, как 3 отдельных?

Answer 1

Почему добавление отдельных предикатов в один отдельный предикат действует не так, как 3 отдельных?

Предикат с несколькими предложениями (то, что вы называете отдельными предикатами) оценивается как ORи один предикат предложения с несколькими операторами, разделенными , оценивается как AND,

Если вы измените это

preOrder(bst(L,X,R)) :-
    write(X),
    write(" "),
    preOrder_04(L),
    preOrder_04(R).

который также может быть записан как

preOrder(bst(L,X,R)) :-
    write(X),
    write(" "),
    (
        preOrder_04(L)
    ,
        preOrder_04(R)
    ).

в

preOrder(bst(L,X,R)) :-
    write(X),
    write(" "),
    (
        preOrder_04(L)
    ;
        preOrder_04(R)
    ).

тогда вы получите то, что ищете.

---

Поскольку вы новичок в Прологе, я также дам вам обзор вашего кода.

Чтобы использовать ваше оригинальное дерево и предикаты

bst(bst(bst(empty,2,empty),4,empty),5,bst(bst(empty,6,empty),8,empty))

preOrder(bst(_,X,_)) :- write(X).
preOrder(bst(L,_,_)) :- preOrder(L).
preOrder(bst(_,_,R)) :- preOrder(R).

я сделал это

tree(bst(bst(bst(empty,2,empty),4,empty),5,bst(bst(empty,6,empty),8,empty))).

test_01 :-
    tree(T),
    preOrder_01(T).

preOrder_01(bst(_,X,_)) :- write(X).
preOrder_01(bst(L,_,_)) :- preOrder_01(L).
preOrder_01(bst(_,_,R)) :- preOrder_01(R).

линия tree(T) прочитайте дерево как факт, а затем привязайте дерево к переменной T, чтобы мне не приходилось вводить его каждый раз.

Затем я создал тестовый предикат с именем _01 так что я бы не стал сталкиваться с другим тестом.

Пример выполнения:

?- test_01.
5
true ;
4
true ;
2
true ;
8
true ;
6
true ;
false.

---

Почему вы должны нажимать пробел после каждого ответа?

(Это было сделано с помощью SWI-Prolog).

Этот пример показывает почему.

test_02 :- write("First").
test_02 :- write("Second").

?- test_02.
First
true ;
Second
true.

Каждый раз, когда предикат test_02/0 выполняется, это приводит к решению, и когда решение дано, вы должны нажать пробел, чтобы увидеть следующее решение.

Также обратите внимание на ; в конце первого ответа. Это Пролог, говорящий вам, что точка выбора существует, и может быть другой ответ. Если бы это было . тогда не было бы больше ответов.

---

Для вашего переписать, который не работает

preOrder_03(bst(L,X,R)) :-
    write(X),
    write(" "),
    preOrder_03(L),
    preOrder_03(R).

test_03 :-
    tree(T),
    preOrder_03(T).

Пример выполнения:

?-  test_03.
5 4 2 
false.

Если вы запустите его с трассировкой, вы увидите, что она не достигает точки выбора.
См. Что такое повтор в Прологе при трассировке?

---

Однако, если вы сделаете это

preOrder_04(bst(L,X,R)) :-
    write(X),
    write(" "),
    (
        preOrder_04(L)
    ;
        preOrder_04(R)
    ).

test_04 :-
    tree(T),
    preOrder_04(T).

Пример выполнения:

?- test_04.
5 4 2 8 6 
false.

Вы получите то, что ищете. Ключевая разница между preOrder_03 а также preOrder_04 в том, что preOrder_03 имеет , в одном месте и preOrder_04 имеет ; в одном месте. Запятая (,) логично AND и точка с запятой (;) логично OR,