Prolog query to find largest element in database?

Question

If I have defined all the digits in a prolog database, such as dig(0),dig(1)...dig(9),

what query can I use for prolog to return the largest digit, so 9?

I tried something like dig(N),dig(M),N>M, but that just returns the first possibility, not the largest number.

Answer 1

To find out the largest number you should write an appropriate query, namely one that:

• Instantiate a digit

• Checks whether that digit is the largest (i.e. no other digit is larger)

So you might want to write something like:

largest(N):-
    dig(N),
    not((
        dig(M),
        M > N
    )).

Answer 2

While the shortest solution is probably:

?- dig(Max), \+((dig(X), X > Max)).

the conceptually simplest solution might be:

?- findall(X, dig(X), Digits), max_list(Digits, Max).

But check out http://stackoverflow.com/questions/1701693 for more solutions, with better and worse complexities.

You can test the speed of these two solutions by consulting this file:

:- between(1, 12345, X), assert(dig(X)), fail ; true.

:- time((findall(X, dig(X), Digits), max_list(Digits, Max))),
       write('Findall max: '), write(Max), nl.

:- time((dig(Max), \+((dig(X), X > Max)))), write('\\+ max: '), write(Max), nl.

On my 5 years old laptop it clearly shows that the findall-version is much faster if you have e.g. 12345 entries in your database.

% 37,085 inferences, 0.05 CPU in 0.06 seconds (87% CPU, 741700 Lips)
Findall max: 12345
% 76,230,375 inferences, 60.94 CPU in 72.30 seconds (84% CPU, 1250909 Lips)
\+ max: 12345