Can anybody help me understanding this prolog program? (Maximum Number in list)

Help!
1

So the output of the program is 8, which is correct, but I don’t understand how it works. Can anybody just shortly explain each step of the program? Would be much appreciated :slight_smile:

maxi([X],X).

maxi([K|R],X):- maxi(R,X), X > K.

maxi([K|R],K):- maxi(R,X), X =< K.

?- maxi([4,5,3,8,2],X), write(X).
2

Remember that Prolog is a logic programming language, which means every clause in the code is a logical rule, listing in its body all facts that must be true for its head to be true. It’s useful to read the implementation using natural language. The three clauses in your code read:

  • the maximum of a list that constains only X is X
  • X is the maxumum of a list that starts with K if X is the maximum of the remaining tail ® of this list and X is bigger than K
  • K is the maximum of a list that starts with K if X is the maximum of the rest of this list and X is not bigger than K

For a more operational look: when you query maxi([4,5,3,8,2],X) the prolog interpreter will try to match this against your rules. It will fail rule 1 because the list is longer than one, then try rule number 2 and recursively find that max of [5,3,8,2] is X = 8 and seeing that 4 = K < X = 8 it will succeed. You can run trace. in the interpreter and see the whole execution sequence.

Also you don’t need write(X) if you’re using the interactive interpreter. It will automatically show you final bindings of all free variables in your query.

3

I am interested in where in the real world you would benefit from such code for what you are trying to achive. I mean the example will in my opnion result in slow performance, and for me it is code which is difficult to understand. So when the next programmer reuses your / my code maybe he wouldnt understand the code either.

I would write the maxi function in prolog as follows.

maxi([], Res, Res).

maxi([K|R], X, Rsu):- X > K, !, maxi(R, X, Rsu) .

maxi([K|R], X, Rsu):- X =< K,!, maxi(R, K, Rsu) .

% call as

?- maxi([4,5,3,8,2], 0, X), write(X).
4

This is homework assignment, so these considerations do not apply. I have typed a lot of words on the topic, but very briefly:

Lectures and exercises have certain goals. Even if you are using a programming language, the goal is often not learning that language. So, Prolog gets picked for topics like “AI” (back in the day) or maybe “logical programming”. C++ used to be “OOP” (then Java, then Python). I had an “Intro to Algorithms and Data Structures” which used Borland Delphi, and “Numerical Mathematics” using the same :slight_smile: it is surprisingly easy to draw the curve which that duck followed when it crossed the laminar flow river, so I guess Delphi wasn’t a bad choice after all.

What does annoy me, as a former student and now as a software professional, is that students, by-and-large, don’t seem to be aware of the subtleties. As for the professors, too often they take the role of gate-keepers. Some have to do it (in Germany, for example, depending on the university and the major, it is very easy to start, and you expect most to give up before the 3rd semester). But not every lecture is just a filter; still, many professors act as gate-keepers.

It is of course possible to fall into the other extreme, esp. if the university has financial incentives to “graduate” their students.

You could also take a look at the library implementation of the same functionality, available as max_list/2 in library(lists), here.

1 Like