Это забавная очередь. Когда задняя часть очереди перемещается вперед, элементы появляются в обратном порядке. Это не совсем очередь.
Тем не менее, операции довольно просты.
Для начала представим очередь в виде составного термина queue(X,Y)
, где X
и Y
являются списками, представляющими начало и конец очереди.
Нам нужен способ получить пустую очередь:
empty(queue([],[])).
Чтобы добавить элемент в очередь, мы делаем это:
add(A,queue(X,Y),queue(X,[A|Y])).
Теперь инструкции противоречивы. Они говорят, что два пустых списка представляют пустую очередь, и новые элементы всегда добавляются в черный список. Так как же первый список может стать пустым , если он начинается пустым и никогда не добавляется в?
Итак, мы должны предоставить предикат, который позволит нам удалить из пустого списка, пока задняя часть не пуста.
remove(queue([],[A|X]),A,queue(X,[])).
Это переносит хвост списка назад вперед и возвращает первый элемент хвоста в A
.
Наконец, если передний список не пуст, тогда мы делаем это:
remove(queue([A|T],X),A,queue(T,X)).
Давайте проверим эти 4 предиката.
?-
empty(Q),
add(7,Q,Q2),
add(5,Q2,Q3),
add(2,Q3,Q4),
write(Q4),nl,
remove(Q4,A,Q5),
add(3,Q5,Q6),
remove(Q6,B,Q7),
remove(Q7,C,Q8),
remove(Q8,D,Q9),
empty(Q9),
write([A,B,C,D]).
Q9
должен быть пустым после добавления 4 атомов в очередь и затем удаления их. [A,B,C,D]
унифицируется до [2,5,7,3]
.
Q4
- это начальное состояние, описанное в инструкциях, хотя оно queue([],[2,5,7])
, поскольку мы всегда добавляемся в черный список.
Так что все это ведет себя так, как нам было приказано.
Но это не настоящая очередь!
Если это была истинная очередь, то первый добавленный элемент должен быть первым удаленным элементом , Ожидаемый результат будет [7,5,2,3]
. Чтобы это работало, мы переписали бы первый предикат remove
следующим образом:
remove(queue([],Z),A,queue(X,[])) :- reverse(Z,[A|X]).
reverse(X,Y):- reverse(X,[],Y).
reverse([],A,A).
reverse([H|T],A,R) :- reverse(T,[H|A],R).
Выполнение кода с этим изменением дает нам ожидаемый результат очереди.