Creating a queue structure in Prolog

user_12918268 0
Viewed 1317

I am in the process of learning Prolog and I'm have trouble approaching the language coming from the object-oriented background.

I am attempted to complete the following instructions:

Implement a phased queue. This is a structure consisting of two lists: the front end and the back end, represented as queue(Front, Back). The queue is empty iff both lists are empty. If elements are added to the queue they are added to the back end; if they are removed they are removed from the front end; if the front end becomes empty (and the back end is not empty) then the back end becomes the new front end with [] as the new back end. For example, we could start with a queue like queue([2,5,7], []), adding 8 gives us queue([2,5,7], [8]), removing two elements gives queue([7], [8]), adding a 9 gives queue([7], [9,8]), and removing an element gives queue([9,8], [])

I don't understand how I create and then refer to a queue structure in the .pl file, in a way that other predicates can then manipulate and transform

I have sketched out roughly what I believe I should be doing, both defined queue structure and as just a list of lists. 

add_to_q(X, [[H|T]|[H2|T2]], [[H|T]|[X|[H2|T2]]).

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

------------------

remove_from_q( [[H | [T|T3]] | [H2|T2]], [[T|T3]] | [H2|T2]]).

queue(X, Y)
remove_from_q( queue(X,[H|T]), queue(H,T).

How do I define and work with a structure in Prolog, how would I add what would be in a OO language methods such as getHead or getTail, I have seen examples of how you would do this with just lists but I am not working with a list of lists rather a "queue" of two separate lists?

Feeling lost!

custom-data-type prolog structure data-structures queue
3 Answers

I'm have trouble approaching the language coming from a OO background.

Do yourself a favor and forget what you know about OO while learning Prolog, it will only confuse you more when learning Prolog. In others words, don't think OO concept then how do I translated that to Prolog. Think about syntactic unification as the basis of how to construct more and more complex predicates.

I don't understand how I create and then refer to a queue structure in the PL file, in a way that other predicates can then manipulate and transform.

The instructions give you the basis for the data structure, i.e. 

queue(Front,Back)

and Front and Back are a list. Examples of a list

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

To refer to the queue is easy. Since Prolog uses syntactic unification, one side of the unification is the atom you want to unify with, e.g. queue(Front,Back) and the other side of the unification is a transformation of queue(Front,Back) you can just use them in a predicate as written.

You demonstrated this already with

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

Note that it is missing an ending ).

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

It is missing an ending ).

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

Since the instructions give very limited examples it is hard to create many test cases to ensure the code would work in a real production system.

Here is working code based on the question.

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).
user_12437620

This is a funny queue. When the back of the queue gets moved to the front then the items are popped in reverse order. It's not really a queue.

Nevertheless, the operations are fairly straight-forward.

To start with we will represent the queue as the compound term queue(X,Y) where X and Y are lists representing the front and the back of the queue.

We need a way to obtain an empty queue:

empty(queue([],[])).

To add an item to the queue we do this:

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

Now, the instructions are inconsistent. They say that two empty lists represent an empty queue and new items are always added to the back list. So how can the first list ever become empty if it starts empty and is never added to?

So we must provide a predicate that allows us to remove from an empty front list so long as the back is not empty.

remove(queue([],[A|X]),A,queue(X,[])).

That brings the the tail of the back list to the front and returns the first element of the tail to A.

Finally, if the front list is not empty then we do this:

remove(queue([A|T],X),A,queue(T,X)).

Let's test these 4 predicates.

?-
    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 must be empty after adding 4 atoms to the queue and then removing them. [A,B,C,D] unifies to [2,5,7,3].

Q4 is the starting state described in the instructions, albeit it's queue([],[2,5,7]) as we are instructed to always add to the back list.

So this all behaves in the way we were instructed to do so.

But it's not a true queue!

If this were a true queue then the first item added should be the first item removed. The expected output would be [7,5,2,3]. To make that work we would rewrite the first remove predicate like this:

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

Running the code with that change gives us the expected output of a queue.

user_2597690

What Guy Coder said. Forget OO anything. It's all about pattern matching.

This is about all you need:

  • First, a means to create an empty queue:
empty( q([],[]) ).

  • Once you have that, enqueuing something is trivial. It's just a matter of prepending the enqueued item to the "back" queue:

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

    Explanation: Lists in prolog are recursive data structures. By convention, an empty list is denoted as the atom [] (think of it as a string). Non-empty lists are written using square bracket notation ([1], [1,2], etc). But... that's just syntactic sugar for the data structure ./2:

    • [1] is shorthand for .( 1 , [] )
    • [1,2] is shorthand for .( 1 , .( 2 , [] ) )
    • ...and so on.


    You can appreciate the utility of the square bracket notation. If you look at this recursive data structure, you'll notice that a list consist of a single item, followed by another [nested] list. That single item is the head of the list, and the nested list is its tail.

    nota bene: recursivity is an important concept in prolog. Learning to think about things in terms of recursion will help you a LOT.

    The notation [H|T] is a way of decomposing a list into its head and its tail. And that is just syntactic sugar for .(H,T). That means that it can also be used to create lists through composition.

    So our enqueue/3 predicate is using that to construct the new "back" list with X prepended to it.

  • And finally, dequeueing something isn't much more complicated:

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

    Explanation:

    The first term in the predicate deals with the case of dequeuing when the "front" list is empty. We just reverse the back list, grab its 1st element, the head (F) as the dequeued item, and grab its tail (Fs) as the new "front" list. And we give the new queue an empty "back" list.

    And the second term in the predicate deals with the case of dequeueing when the "front" list is not empty. Even simpler: we just grab the head of the "front" list, unify it as the dequeued item, and construct new queue using the tail of the old "front" list as the new "front" list, leaving the "back" list as-is.

Example

Run it at 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            )
  .
user_4674730
Related