Создание структуры очереди на Прологе

У меня проблемы с подходом к языку, исходящему из опыта ООП.

Сделайте себе одолжение и забудьте все, что вы знаете об ООП при изучении Пролога, это только еще больше запутает вас при изучении Пролога. Другими словами, не думайте о концепции ООП, тогда как я перевел это на Пролог. Подумайте о синтаксической унификации как о основе того, как построить больше и более сложные предикаты.

Я не понимаю, как я создаю и затем ссылаюсь на структуру очереди в файле PL таким образом, чтобы другие предикаты могли затем манипулировать и преобразовывать.

Инструкции дают вам основу для структуры данных, т.е.

queue(Front,Back)

а Front и Back представляют собой список. Примеры списка

[]
[a]
[a,b]
[a|b]

Сослаться на очередь легко. Поскольку Пролог использует синтаксическую унификацию, одной стороной унификации является атом, с которым вы хотите объединиться, например. queue(Front,Back), а другая сторона объединения — это преобразование queue(Front,Back), вы можете просто использовать их в предикате, как написано.

Вы уже продемонстрировали это с помощью

add_to_q(A,queue(X,Y),queue(X,[A|Y])

Обратите внимание, что в нем отсутствует окончание ).

add_to_q(A,queue(X,Y),queue(X,[A|Y]). % gives Syntax error: Operator expected

Не хватает окончания ).

add_to_q(A,queue(X,Y),queue(X,[A|Y])).

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

Вот рабочий код, основанный на вопросе.

add(Item,queue(Front,Back),queue(Front,[Item|Back])).

remove(Item,queue([Item|[]],Back),queue(Back,[])).
remove(Item,queue([Item|Front],Back),queue(Front,Back)).

:- begin_tests(funny_queue).

funny_queue_test_case_generator(add   , 8    ,queue([2,5,7]  ,[   ] ) ,queue([2,5,7],[8]   ) ).
funny_queue_test_case_generator(remove, 2    ,queue([2,5,7]  ,[  8] ) ,queue([5,7]  ,[8]   ) ).
funny_queue_test_case_generator(remove, 5    ,queue([5,7]    ,[  8] ) ,queue([7]    ,[8]   ) ).
funny_queue_test_case_generator(add   , 9    ,queue([7]      ,[  8] ) ,queue([7]    ,[9,8] ) ).
funny_queue_test_case_generator(remove, 7    ,queue([7]      ,[9,8] ) ,queue([9,8]  ,[]    ) ).

test(add,[forall(funny_queue_test_case_generator(add,Item,Funny_queue_0,Funny_queue))]) :-
    add(Item,Funny_queue_0,Funny_queue_expected),

    assertion( Funny_queue == Funny_queue_expected ).

test(add,[nondet,forall(funny_queue_test_case_generator(remove,Item,Funny_queue_0,Funny_queue))]) :-
    remove(Item,Funny_queue_0,Funny_queue_expected),

    assertion( Funny_queue == Funny_queue_expected ).

:- end_tests(funny_queue).

Это забавная очередь. Когда конец очереди перемещается вперед, элементы извлекаются в обратном порядке. Это не совсем очередь.

Тем не менее, операции довольно прямолинейны.

Для начала мы представим очередь как составной термин 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). 

Выполнение кода с этим изменением дает нам ожидаемый результат очереди.

Что сказал Гай Кодер. Забудьте об ОО. Все дело в сопоставлении с образцом.

Это все, что вам нужно:

• Во-первых, средство для создания пустой очереди:

empty( q([],[]) ).

• Если у вас есть это, поставить что-то в очередь тривиально. Это просто вопрос добавления поставленного в очередь элемента в «обратную» очередь:

  enque( X , q(F,B) , q(F, [X|B] ) ) .
  

  Объяснение. Списки в прологе — это рекурсивные структуры данных. По соглашению пустой список обозначается как атом [] (подумайте об этом как о строке). Непустые списки записываются с использованием квадратных скобок ([1], [1,2] и т. д.). Но... это просто синтаксический сахар для структуры данных ./2:

  • [1] is shorthand for .( 1 , [] )
  • [1,2] — это сокращение от .( 1 , .( 2 , [] ) ).
  • ...и так далее.

  
  Вы можете оценить полезность записи в квадратных скобках. Если вы посмотрите на эту рекурсивную структуру данных, вы заметите, что список состоит из одного элемента, за которым следует еще один [вложенный] список. Этот отдельный элемент — голова списка, а вложенный список — его хвост.

  Примечание: рекурсивность – важная концепция Пролога. Умение думать о вещах с точки зрения рекурсии очень поможет вам.

  Нотация [H|T] — это способ разбиения списка на его голову и хвост. И это просто синтаксический сахар для .(H,T). Это означает, что его также можно использовать для создания списков посредством композиции.

  Таким образом, наш предикат enqueue/3 использует его для создания нового списка «назад» с добавленным к нему X.

• И, наконец, убрать что-то из очереди не намного сложнее:

  deque( q( []     , Bs ) , F , q( Fs , [] ) ) :- reverse( Bs, [F|Fs] ).
  deque( q( [F|Fs] , Bs ) , F , q( Fs , Bs ) ) .
  

  Пояснение:

  Первый термин в предикате касается случая удаления из очереди, когда «передний» список пуст. Мы просто переворачиваем задний список, берем его 1-й элемент, голову (F) в качестве элемента, удаленного из очереди, и берем его хвост (Fs) в качестве нового "переднего" списка. . И мы даем новой очереди пустой «обратный» список.

  А второй термин в предикате касается случая удаления из очереди, когда "передний" список не пуст. Еще проще: мы просто берем голову "переднего" списка, объединяем его как элемент, удаленный из очереди, и создаем новую очередь, используя хвост старого "переднего" списка. как новый «передний» список, оставив «задний» список как есть.

Пример

Запустите его по адресу https://swish.swi-prolog.org/p/phased-queue.pl

empty( q([],[]) ).

enque( X , q(F,B) , q(F, [X|B] ) ).

deque( q( []     , Bs ) , F , q(Fs,[]) ) :- reverse( Bs, [F|Fs] ).
deque( q( [F|Fs] , Bs ) , F , q(Fs,Bs) ).


run_example :-
  empty( Q0             ) , writeln( queue :         Q0  ) ,
  enque( 1   , Q0 , Q1  ) , writeln( enque :         Q1  ) ,
  enque( 2   , Q1 , Q2  ) , writeln( enque :         Q2  ) ,
  enque( 3   , Q2 , Q3  ) , writeln( enque :         Q3  ) ,
  enque( 4   , Q3 , Q4  ) , writeln( enque :         Q4  ) ,
  deque( Q4  , X1 , Q5  ) , writeln( deque : x(X1) : Q5  ) ,
  enque( 5   , Q5 , Q6  ) , writeln( enque :         Q6  ) ,
  enque( 6   , Q6 , Q7  ) , writeln( enque :         Q7  ) ,
  deque( Q7  , X2 , Q8  ) , writeln( deque : x(X2) : Q8  ) ,
  deque( Q7  , X3 , Q9  ) , writeln( deque : x(X3) : Q9  ) ,
  deque( Q9  , X4 , Q10 ) , writeln( deque : x(X4) : Q10 ) ,
  deque( Q10 , X5 , Q11 ) , writeln( deque : x(X5) : Q11 ) ,
  deque( Q11 , X6 , Q12 ) , writeln( deque : x(X6) : Q12 ) ,
  deque( Q12 , X7 , Q13 ) , writeln( deque : x(X7) : Q13 ) ,
  empty( Q13            )
  .