I have this code in GNU Prolog, and I don't know why it is slow with a 50-element paired list:
pairwise_min( [X], X ) :- !.
pairwise_min( [(A,B)|T], (A,B) ) :-
pairwise_min( T, (_,B1) ),
B1 > B,
!.
pairwise_min( [(_,B)|T], (A1,B1) ) :-
pairwise_min( T, (A1,B1) ),
B1 =< B,
!.
The following query takes 10 seconds:
?- pairwise_min( [(25,25),(24,24),(23,23),(22,22),(21,21),(20,20),(19,19),(18,18),(17,17),(16,16),(15,15),(14,14),(13,13),(12,12),(11,11),(10,10),(9,9),(8,8),(7,7),(6,6),(5,5),(4,4),(3,3),(2,2),(1,1)], X ).
What can I do to quickly find this minimum?
You can quickly see the problem when you trace:
?- trace, pairwise_min( [(25,25),(24,24),(23,23),(22,22),(21,21),(20,20),(19,19),(18,18),(17,17),(16,16),(15,15),(14,14),(13,13),(12,12),(11,11),(10,10),(9,9),(8,8),(7,7),(6,6),(5,5),(4,4),(3,3),(2,2),(1,1)], X ).
Call: (7) pairwise_min([ (25, 25), (24, 24), (23, 23), (22, 22), (21, 21), (20, 20), (19, 19), (..., ...)|...], _G737) ?
... snip ...
Call: (30) pairwise_min([ (2, 2), (1, 1)], (_G1065, _G1066)) ?
Call: (31) pairwise_min([ (1, 1)], (_G1068, _G1069)) ?
Exit: (31) pairwise_min([ (1, 1)], (1, 1)) ?
Call: (31) 1>2 ?
Fail: (31) 1>2 ?
Redo: (30) pairwise_min([ (2, 2), (1, 1)], (_G1065, _G1066)) ?
Call: (31) pairwise_min([ (1, 1)], (_G1065, _G1066)) ?
Exit: (31) pairwise_min([ (1, 1)], (1, 1)) ?
Call: (31) 1=<2 ?
Exit: (31) 1=<2 ?
Exit: (30) pairwise_min([ (2, 2), (1, 1)], (1, 1)) ?
Call: (30) 1>3 ?
Fail: (30) 1>3 ?
Redo: (29) pairwise_min([ (3, 3), (2, 2), (1, 1)], (_G1062, _G1063)) ?
Call: (30) pairwise_min([ (2, 2), (1, 1)], (_G1062, _G1063)) ?
Call: (31) pairwise_min([ (1, 1)], (_G1068, _G1069)) ?
Exit: (31) pairwise_min([ (1, 1)], (1, 1)) ?
Call: (31) 1>2 ?
Fail: (31) 1>2 ?
Redo: (30) pairwise_min([ (2, 2), (1, 1)], (_G1062, _G1063)) ?
Call: (31) pairwise_min([ (1, 1)], (_G1062, _G1063)) ?
Exit: (31) pairwise_min([ (1, 1)], (1, 1)) ?
Call: (31) 1=<2 ?
Exit: (31) 1=<2 ?
Basically, the problem is that you wind up calling pairwise_min(T, ...) in both cases, even though it won't be different in the second case. The pairwise minimum of the tail is the pairwise minimum of the tail, regardless of how the current element checks out against it.
A good solution would be to eliminate the second rule by using an explicit conditional, something like this:
pairwise_min( [X], X ) :- !.
pairwise_min( [(A,B)|T], (RA,RB) ) :-
pairwise_min(T, (A1,B1)), !,
(B1 > B -> (RA = A, RB = B)
; (RA = A1, RB = B1)).
A significant impediment to readability for me is that I don't really grok what kind of ordering you're trying to achieve with your pairwise minimum. But it would be a good idea for the future to extract that into its own predicate anyway. I have zero confidence I've gotten your minimum right; is it not true that @</2 will do what you want? If that is the case, you can do this with a very tight, tail-recursive fold:
minimum([X|Xs], Min) :- minimum(Xs, X, Min).
minimum([], Min, Min).
minimum([X|Xs], MinSoFar, Min) :-
(X @< MinSoFar -> minimum(Xs, X, Min)
; minimum(Xs, MinSoFar, Min)).
If that isn't the case, you can write your own predicate min_pair/2 that compares two pairs, and use that instead of @</2 and gain the benefit. Or call it from the revised pairwise_min/2 above and see the benefit of tail call optimization.
I think you'll have some trouble improving on the performance of this version.