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
?- 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.