Ggtcf

Exercise 3.17 “ Prolog Programming for Artificial Intelligence” by
Ivan Btrako

I understand the max predicate, but I'm having trouble tracing the maxList one. I'm trying to write the logic in pseudocode to help me out

1. Take first and second elements and compare them and get the
   maximum


2. Take that maximum and compare it with third element in
   list and if it's bigger overwrite the maximum and repeat again till
   list is empty.

I don't understand the solution given however, and I tried tracing it and failed. I'm having trouble mapping the MaxRest to the Max & with the base case. Also, I don't understand why prolog doesn't give an error when unifying [X,Y|Rest] with [Y|T]. Example [1,3,[7,2]] with [3|[7,2]].

max(X,Y,X):-
 X>=Y.
max(X,Y,Y):-
 X<Y.

maxlist( [X], X). %what does this line do?
maxlist( [X,Y|Rest], Max):- 
 maxlist( [Y|Rest], MaxRest),
 max(X, MaxRest,Max).

Any help tracing would be greatly appreciated.

Since you understand max/3 this won't explain it.

maxlist( [X], X). %what does this line do?
maxlist( [X,Y|Rest], Max):- 
 maxlist( [Y|Rest], MaxRest),
 max(X, MaxRest,Max).

This is a classic recursive list pattern that does the recursion before processing the item. The normal recursive list pattern with a tail-call is

process_list([H|T],R) :-
 process_item(H,R),
 process_list(T,R).
process_list([],R).

but here it is

process_list([H|T],R) :-
 process_list(T,R),
 process_item(H,R).
process_list([],R).

where the item is processed after recursing through the list.

Also this processes two items at a time, i.e.

 [H1,H2|T]

because the compare needs two items.

This

maxlist( [X,Y|Rest], Max):- 
 maxlist( [Y|Rest], MaxRest),

is just taking the values off of the list and pushing them onto the stack so that when it backtracks it will have one value for the comparison, i.e. MaxRest which is the max of all the values that were in Rest and the current value which is X. You might think it should be Y, but when there is just one item in the list, the list is actually [Y|[]] which is really [Y] with matches with the pattern in this clause maxlist( [X], X)..

So what does maxlist( [X], X). do? A common base case for a list is just predicate([],R). for returning a list, but in this case the last value alone needs to be returned as a value, so this takes X out of the list in the first parameter and returns it as a value in the second parameter so that it becomes MaxRest which is the max value when there is only one item in the list. When max(X, MaxRest,Max) is executed it has a value for MaxRest return from backtracking, and X on the stack when deconstructing the list. The result is Max which is returned as the third parameter in maxlist( [X,Y|Rest], Max) which becomes the value for MaxRest upon backtracking again.

Ask questions if that doesn't make sense.

I don't understand why Prolog doesn't give an error when unifying
[X,Y|Rest] with [Y|Rest].

Example [1,3,[7,2]] with [3|[7,2]]

Actually

?- [1,3,[7,2]] = [3|[7,2]].
false.

so while your example does give an error, it is not what is being done with

[X,Y|Rest] and [Y|Rest]

Start with the list [1,2,3,4] and unify it with[X,Y|Rest]

?- [1,2,3,4] = [X,Y|Rest].
X = 1,
Y = 2,
Rest = [3, 4].

Notice that [Y|Rest] would then be [2|[3,4]].

?- [1,2,3,4] = [X,Y|Rest],A = [Y|Rest].
X = 1,
Y = 2,
Rest = [3, 4],
A = [2, 3, 4].

Don't try an unify [X,Y|Rest] with [Y|Rest] but instead unify Rest with Rest and Y with Y, X is stored on the stack but not passed to next level of the stackframe.

If you really want to understand list then use this to see them

?- write_term([1,2,3,4],[dotlists(true)]).
.(1,.(2,.(3,.(4,[]))))
true.

If you have Version 4 of the book see Figure 3.1 on page 61.

Prolog predicates define relations in terms of logic that says that the head of the clause is true if (:-) the body is true. This helps you properly read a predicate:

max(X,Y,X):-
 X>=Y.

This says that:

X is the maximum of X and Y if X >= Y is true.

You can similarly read the clause for max(X,Y,Y).

Now look at:

maxlist( [X], X).

Here, we're defining maxlist to mean the maximum value of a list. This particular clause says that:

X is the maximum value of the list [X].

There are no if conditions (:-) in this case since no other conditions are necessary to establish this rule.

Then there is the recursive clause:

maxlist( [X,Y|Rest], Max):- 
 maxlist( [Y|Rest], MaxRest),
 max(X, MaxRest,Max).

This says that:

Max is the maximum value of list [X,Y|Rest] if MaxRest is the maximum of list [Y|Rest] and Max is the maximum value of X and MaxRest.

This recursive clause and the prior base case clause completely define maxlist. If you read through that carefully, it should seem completely logical.

I don't understand why prolog doesn't give an error when unifying [X,Y|Rest] with [Y|T]

I don't understand this comment. Nowhere in your code does Prolog attempt to unify these two terms. Your example terms of [1,3,[7,2]] and [3|[7,2]] would not unify because the first is a list of three elements: 1, 3, and [7,2], whereas the other is a list of 3 elements: 3, 7, and 2. For two lists to be unifiable, it not only needs to be the same length, but each corresponding term in the list must be unifiable.

What would then make [X,Y|Rest] and [Y|T] unifiable? You can write [X,Y|Rest] as [X|[Y|Rest]], which makes it easy to see that these are unifiable if the following are true:

X = Y,
[Y|Rest] = T

In other words, the lists have to have (a) at least two elements, and (b) the first two elements are the same.