Take the 2-minute tour ×

I know how to iterate over lists in Prolog to find the maximum, but what if each thing is a separate clause? For example if I had a bunch of felines and their ages, how would I find the oldest kitty?

cat(sassy, 5).
cat(misty, 3).
cat(princess, 2).

My first thought was "hmm, the oldest cat is the one for which no older exists". But I couldn't really translate that well to prolog.

oldest(X) :- cat(X, AgeX), cat(Y, AgeY), X \= Y, \+ AgeX < AgeY, print(Y).

This still errorenously matches "misty". What's the proper way to do this? Is there some way to more directly just iterate over the ages to choose max?

share|improve this question

5 Answers 5

up vote 3 down vote accepted

A cat is the oldest if it's a cat and there is not a cat older than it. Let's write that in Prolog:

oldest(X):- cat(X, _), not( thereAreOlders(X)), !.
thereAreOlders(X):- cat(X, N), cat(C, M), C\=X, M > N.

If you consult:

?- oldest(X).
X = sassy.
share|improve this answer

One way is

oldest(X) :- cat(X, AgeX), \+ Y^(cat(Y, AgeY), Y \= X, AgeX < AgeY).

You can also use setof/3 to get a list of all cats and get the maximum from that.

share|improve this answer

Here is a solution that loops through all the solutions, always recording the solution that is better than the previous best. In the end, the best solution is returned.

The recording is done using assert/1, you could also use a non-backtrackable global variable if your Prolog provides that (SWI-Prolog does).

The benefit of this approach is that is considers each solution only once, i.e. complexity O(n). So, even though it looks uglier than starblue's solution, it should run better.

% Data
cat(sassy, 5).
cat(misty, 3).
cat(miisu, 10).
cat(princess, 2).

% Interface
oldest_cat(Name) :-

loop_through_cats :-
    cat(Name, Age),
    record_cat_age(Name, Age),
    fail ; true.

:- dynamic current_oldest_cat/2.

record_cat_age(Name, Age) :-
    current_oldest_cat(_, CAge),
    Age > CAge,
    retract(current_oldest_cat(_, _)),
    assert(current_oldest_cat(Name, Age)).

record_cat_age(Name, Age) :-
    assert(current_oldest_cat(Name, Age)).

fetch_oldest_cat(Name) :-
    retract(current_oldest_cat(Name, _Age)).

Usage example:

?- oldest_cat(Name).

Name = miisu

Miisu is a typical Estonian cat name. ;)

share|improve this answer
That's too ugly, I'd rather use setof, bagof or findall to get O(n) complexity. (My one-liner and the solution by Juanjo are O(n^2).) –  starblue Nov 10 '09 at 10:28
Well, ugliness can be hidden behind an interface predicate. setof sorts the results so you won't get a O(n) complexity. With findall you walk through the solutions twice, once to build a list (which might not even fit into memory if you have billions of cats), and then to walk through the list. Actually, it would be cool to test the speed and memory consumption of all the proposed solutions. –  Kaarel Nov 10 '09 at 13:17

On a stylistic point- there are a few different approaches here (some are very elegant, others more 'readable'). If you're a beginner- chose your own, preferred, way of doing things- however inefficient.

You can learn techniques for efficiency later. Enjoy Prolog- its a beautiful language.

share|improve this answer
Should have added: SWI-prolog has an excellent profiler to help you focus on expensive clauses. try it- profile(my_goal). –  Chrissy Flangé Allen Mar 26 '13 at 17:18

I don't remember much Prolog, but I do know that you shouldn't think about solving problems as you would with an imperative programming language.

share|improve this answer

Your Answer


