Editing a list in Prolog

Question

I finished my homework for my programming class. I had to create a Prolog program that changes the list. However, I do not understand why this is what works.

%1. reverse a list %[a,b,c]->[c,b,a] %reverse(list, rev_List). reverse([],[]). %reverse of empty is empty - base case reverse([H|T], RevList):- reverse(T, RevT), conc(RevT, [H], RevList). %concatenation 

What is RevT in this case? I know that it should represent the back of T or the rest of this list, but I don’t see how this could have any meaning, since I did not assign it to anything. Is this true for the same purpose as RevList, but for every recursive call?

Also, why should I use [H] instead of H only in calling the conc () function? Does H refer to the head of the list (for example: [H])? Or does this just apply to the item at the head of the list (just H)?

Please help me sort it out. I'm struggling to understand this type of programming logic.

Answer 1

Your decision is explained: If we cancel the empty list, we get an empty list. If we cancel the list [H | T], we get a list obtained by reversing T and concatenating with [H]. To verify that the recursive clause is correct, consider the list [a, b, c, d]. If we redraw the tail of this list, we get [d, c, b]. Combining this with [a] gives [d, c, b, a], which is the inverse of [a, b, c, d]

Another inverse solution:

  reverse([],Z,Z). reverse([H|T],Z,Acc) :- reverse(T,Z,[H|Acc]). 

call:

 ?- reverse([a,b,c],X,[]). 

For more information, please read: http://www.learnprolognow.org/lpnpage.php?pagetype=html&pageid=lpn-htmlse25

Answer 2

./2 lists are simple data structures: ./2

• An empty list is an atom [] .
• The list of one element [a] is actually this structure:. .(a,[]) .
• The list of two elements [a,b] is actually this structure:. .(a,.(b,[]))
• The list of three elements [a,b,c] is actually this structure:. .(a,.(b,.(c,[])))
• etc.

A square bracket designation is syntactic sugar to save you from wasting your life on parentheses. Not to mention that it is easier on the eyes.

From this we get the concept of the head of the list (the base point in the outermost structure ./2 ) and the tail of the list (the sublist contained in this outermost structure ./2 .

This is essentially the same data structure that you see for a classic, simply-linked list in C:

 struct list_node { char payload ; struct list_node *next ; } 

where the next pointer is either NULL or another list structure.

So, from this we get a simple [naive] implementation of the inverse / 2:

 reverse( [] , [] ) . % the empty list is already reversed. reverse[ [X] , [X] ) . % a list of 1 item is already reversed. This special case is, strictly speaking, optional, as it will be handled by the general case. reverse( [X|Xs] , R ) :- % The general case, a list of length >= 1 , is reversed by reverse(Xs,T) , % - reversing its tail, and append( T , [X] , R ) % - appending its head to the now-reversed tail . % 

The same algorithm will work in order to turn over a singly linked list in a more traditional programming language.

However, this algorithm is not very efficient: it shows the behavior of O (n ² ) for starters. It is also not tail recursive, which means that a list of sufficient length will cause a stack overflow.

It should be noted that adding an element to the prolog list requires moving the entire list, adding is a trivial operation due to the structure of the prolog list. We can add an item to an existing list in the same way as:

 prepend( X , Xs , [X|Xs] ) . 

A common idiom in a prolog is to use a working predicate with a battery. This makes reverse/2 implementation much more efficient and (perhaps) a little easier to understand. Here we cancel the list by unloading our battery as an empty list. We iterate over the original list. When we encounter an element in the original list, we add it to the reverse list, creating an inverse list.

 reverse(Xs,Ys) :- % to reverse a list of any length, simply invoke the reverse_worker(Xs,[],Ys) . % worker predicate with the accumulator seeded as the empty list reverse_worker( [] , R , R ). % if the list is empty, the accumulator contains the reversed list reverse_worker( [X|Xs] , T , R ) :- % if the list is non-empty, we reverse the list reverse_worker( Xs , [X|T] , R ) % by recursing down with the head of the list prepended to the accumulator . 

Now you have a reverse/2 implementation that runs in O (n) time. It is also tail recursive, which means that it can process a list of any length without blowing its stack.

Answer 3

Consider using DCG instead, which is much easier to understand:

 reverse([]) --> []. reverse([L|Ls]) --> reverse(Ls), [L]. 

Example:

 ?- phrase(reverse([a,b,c]), Ls). Ls = [c, b, a]. 

Answer 4

What is RevT in this case? I know that it should represent the back of T or the rest of this list, but I don’t see how this could have any meaning, since I did not assign it to anything. Does it use only the same purpose as RevList, but for each recursive call?

Variables in Prolog are 'placeholders' arguments for relationships. What we know after a successful call is that the specified arguments are saved for this relationship.

Then RevT will matter if the call RevT . In particular, it will be the final argument to calling conc(RevT, [H], RevList) when the list is not empty. Otherwise there will be an empty list.

Also, why should I use [H] instead of H only in calling the conc () function? Does H refer to the head of the list (for example: [H])? Or does this just apply to the item at the head of the list (just H)?

Yes, H refers to the first element (usually called an element) of the list, then we must "change" it as a list (only 1 element), as required conc / 3, which is another relationship between the lists.