[monkey7]

I'm new to Prolog and I am having difficulty understanding it. I am supposed to take a list and reverse, which I would find easy enough to do in another language (like C), but with Prolog I am lost. I looked at the information on recursion, and I don't even understand that. Here is the code we were given:

member(X,[X|_]).
member(X,[_|Y]) :- member(X,Y).

I understand the idea of a head and a tail. I know that the first part of the code searches for a member in the head. That makes sense to me. The second part is recursive, and I don't really understand it. I know what it's doing (removing the head and making the next item in the list the new head) because that it stated for us, but I don't understand how that code accomplishes that.

Moreover, I have no idea how to actually reverse the list. Normally, I would try to determine how many items are in the list, store each one as a variable and output them in reverse, but in Prolog I don't know how to do most of that. This is homework, so I am not looking for someone to do it for me. Help understanding would be greatly appreciated, though. Thanks.

[sepp2k]

You shouldn't think of Prolog code as "doing" anything. Prolog code does not describe a set of actions - it describes the result. In this the code for member describes when something is a member of a list.

Specifically the first rule says that any value X is a member of the list [X|_], where [X|_] means any list that starts with X, i.e. if X is the first value of the list, X is a member of the list. That's logical enough. The second rule says that any value X is a member of the list [_|Y] if X is a member of Y. So since those two rules are alternatives, you can read the whole thing as "Any value X is a member of a given list if it is the head of the list or if it is a member of the tail of the list". This is clearly a correct description of when a value is a member of a list.

So what you need to do is to find a similar description of when a given list is the reverse of another list. If you can manage to write a predicate that checks whether a given value is the last element in a list, you can implement a rule that says "A list list1 is the reverse of another list list2 if list1's head is equal to list2's last element". Obviously that's not enough (clearly [1,2,3] is not the reverse of [5,6,1]), but it's a start. And if you get that far, maybe the rest will fall into place.

[monkey7]

Thank you for your help. The first part of what you wrote made sense to me, and I can understand how the second part is useful in what I am trying to accomplish. Does this code do that:

 reverse(X,Y)  :- X(H, [H|_]) is Y(H, [[]|T]). 

If not, what am I doing wrong? Thanks.

[sepp2k]

When you write X(H, [H|_]) you use X as if it was a predicate, which it is not. I think what you're going for was this:

reverse([H,_], [[],T]) :- H is T.

Or something like that. However that does not work. If you have a (proper) list of values, the head of such a list will always be a single value while the tail of the list will always be a list. So you can't use [] as the head of a list (unless it's a list of lists, which we are not considering here) and you can't check whether H is equal to T (well you can, but it will never be true because T is a list and H is not).

Basically when attacking a problem like this, you usually have a base case and a recursive case (or more than one of either for more complicated problems). The base case is one that is immediately solvable without recursion. In the example of member the base case was a list whose first element is the element you're looking for - if that's the case there's no need to look further into the list. The recursive case is the one that depends on the rest of the list.

So for our predicate that looks for the last element in a list, the base case would be a list with only one element. In that case clearly that one element is the last element in the list. The syntax to express this would be:

last_element(X, [X]).

Read: The last element of the list [X] is X (for any value X). Now we only need the recursive case. So we need to ask ourselves: For a list with head H and tail T, how does X (where X is the last element of the list) depend on T.

This post has been edited by sepp2k: 15 February 2012 - 07:45 PM