How to does this Prolog example work?

Question

The question Reads, "Write a Prolog program that finds the maximum of a list of numbers."

I have used the power of the internet to help find a solution that works but, I want to have an understanding of the program itself.

max_num([X],X).
max_num([X|Y],X):- max_num(Y,Z), X >= Z.
max_num([X|Y],A):- max_num(Y,A), A > X.

Line1:

max_num([X],X).

I understand that Line1 is defining the basic template of the question. The [X] defines the list and the other X represents the maximum value within that list.

Line2:

max_num([X|Y],X):- max_num(Y,Z), X >= Z.

This is where I lose track of things. I understand the first part, "max_num([X|Y],X)" and that it split the list into two parts, "A first half" and the "Second half" separated by the vertical line. and the X is just the Max Number? I am unsure at this point.

Line3: Well its just not even worth trying to comprehend now. Please comment below to help me understand the current logic of this program.

Best Regards.

Answer 1

If you are somewhat familiar with first order logic you might find it helpful to replace :- with logical implacation and , with conjunction. Then the second line of the program looks like:

max_num([X|Y],X) ← max_num(Y,Z) ∧ X >= Z

Note that the implication arrow goes to the left, towards the head of the rule. You can flip that around to see the implication arrow point in a more familiar direction:

max_num(Y,Z) ∧ X >= Z → max_num([X|Y],X)

The line reads: If (Z is the maximum of list Y and X >= Z) then X is the maximum of the list that has X as first element (head) and Y as the rest of the list (tail).

The same goes for the third line:

max_num([X|Y],A) ← max_num(Y,A) ∧ A > X

If (A is the maximum of list Y and A > X) then A is the maximum of the list that has X as head and Y as tail.

I am not sure what you mean by template regarding the first rule. The first line of this program is a fact. This is a way to say in prolog: This is always true. You could alternatively write it:

max_num([X],X) :- true.

Declaratively it says: The maximum number in a list with exactly one element X is that very element.

Procedurally you need this fact in order to let the program terminate (at least for lists with fixed lengths). Just think about it:

if the first argument is:

• [X]: The first rule matches and succeeds. The second and third rules also match because [X] = [X|[]] but fail in their recursive goal because max_num/2 has no rule where the empty list matches the first argument.

• [X|Y] with Y not being []: The first rule does not match. But the other two do and they will recurse because Y is not the empty list and thus will match the first argument of max_num/2.

Answer 2

The :- operator is used to define a predicate clause or rule in terms of other queries. You have a predicate, max_num/2 (which has two arguments) that consists of three predicate clauses or rules, the first of which is a very simple rule: max_num([X], X). which you already noted means:

X is the maximum number in the list [X].

Generally, you can read :- as "if" for a rule:

max_num([X|Y],X) :- max_num(Y,Z), X >= Z.

Would be read:

X is the maximum number of list [X|Y] (list with head X and tail Y) if Z is the maximum number of the tail Y and X >= Z (X, the head, is greater than or equal to Z).

Note that the "vertical line" you're referring to separates the head and tail of a list. If you do a basic Prolog tutorial or read some introductory Prolog material, this would be explained. The head is the first element, and the tail is a list that constitutes the remainder of the list. Thus, the list [H|T] has first element H and the rest of the list is list T.

If you understand this, then reading line 3 should be simple.