Prolog finding the largest integer in a list from the tail

Question

I need to find the largest integer in a list from the head of a list and alternatively from the tail. I have already written a program that can find the largest from the head now I need some help to do it from the tail.

Here is what I have so far:

largest([X],X).
largest([X|Xs],X) :- largest(Xs,Y), X>=Y.
largest([X|Xs],N) :- largest(Xs,N), N>X.

Keep in mind that this finds the largest integer from the head, and I need it to work from the tail. Thanks for the help.

Answer 1

Hold on for a second! Before you continue, first measure the time your predicate takes!

?- length(J,I), I>10, append(J,[2],L),maplist(=(1),J),  time(largest(L,N)).
% 12,282 inferences, 0.006 CPU in 0.006 seconds (99% CPU, 1977389 Lips)
J = [1, 1, 1, 1, 1, 1, 1, 1, 1|...],
I = 11,
L = [1, 1, 1, 1, 1, 1, 1, 1, 1|...],
N = 2 ;
% 4 inferences, 0.000 CPU in 0.000 seconds (84% CPU, 98697 Lips)
% 24,570 inferences, 0.011 CPU in 0.011 seconds (99% CPU, 2191568 Lips)
J = [1, 1, 1, 1, 1, 1, 1, 1, 1|...],
I = 12,
L = [1, 1, 1, 1, 1, 1, 1, 1, 1|...],
N = 2 ;
% 4 inferences, 0.000 CPU in 0.000 seconds (84% CPU, 98556 Lips)
% 49,146 inferences, 0.021 CPU in 0.021 seconds (100% CPU, 2365986 Lips)
J = [1, 1, 1, 1, 1, 1, 1, 1, 1|...],
I = 13,
L = [1, 1, 1, 1, 1, 1, 1, 1, 1|...],
N = 2 ...

The number of inferences clearly doubles each time the length increases by one! That's the way how Prolog gets its bad reputation for being extremely inefficient, nixing all progress in processor speed.

So what is happening in your program? There is no need to go into details, but lets consider a small fragment (failure-slice) of your program. While this resulting program is completely dysfunctional for your purpose it gives us a lower bound of the number of inferences in your program:

largest([X],X) :- false.
largest([X|Xs],X) :- largest(Xs,Y), false, X>=Y.
largest([X|Xs],N) :- largest(Xs,N), false, N>X.

For each element in the list, we have two equally applicable choices. So with a list of N elements, we have 2^N choices!

Here is a possible rewrite:

largest([X],X).
largest([X|Xs],R) :-
   largest(Xs,Y),
   (  X>=Y, R = X
   ;  Y > X, R = N
   ).

You can do even better by using if-then-else...

largest([X],X).
largest([X|Xs],R) :-
   largest(Xs,Y),
   (  X>=Y -> R = X
   ;  Y > X, R = N
   ).

or max/2

largest([X],X).
largest([X|Xs],R) :-
   largest(Xs,Y),
   R is max(X,Y).

This program still requires space proportional to the length of the list. And that is what you can reduce to a constant, by using a tail-recursive version. But at least this version runs now in linear time.

And for the actual optimization you want to perform, read

SWI-Prolog: Sum-List