As a fun exercise I implemented a predicate to calculate the minimum and maximum element of a list.
min_and_max([A], A, A).
min_and_max([H|R], N, X):-
min_and_max(R, RN, RX),
N is min(H, RN),
X is max(H, RX).
Next I wrote a version with last-call optimization.
min_and_max_2([A], A, A).
min_and_max_2([H|R], N, X) :-
min_and_max_2_helper(R, H, H, N, X).
min_and_max_2_helper([], A, B, A, B).
min_and_max_2_helper([H|R], MinSoFar, MaxSoFar, FinalMin, FinalMax):-
MinSoFar1 is min(MinSoFar, H),
MaxSoFar1 is max(MaxSoFar, H),
min_and_max_2_helper(R, MinSoFar1, MaxSoFar1, FinalMin, FinalMax).
But how do we know our second version is optimized? Well I'm not the first to ask this. This handy thread includes a tip, you can print out the stack frame and check that it never changes.
prolog_current_frame(Frame),
format("~w~n", [Frame]),
With that in place we can try:
?- min_and_max([1,2,3,4,5,6,7,8], N, X).
142
158
174
190
206
222
238
N = 1,
X = 8
And for min_and_max_2
:
?- min_and_max_2([1,2,3,4,5,6,7,8], N, X).
142
142
142
142
142
142
142
N = 1,
X = 8.
I haven't yet managed the inverse modality, maybe that's the next exercise.