printOrAdd(IntegerList, Sum)which binds the even numbers from its input list
IntegerListto a list
EvensList, and at the same time adds up the odd numbers in
IntegerListand binds them to
Sum. Here are two versions of the code,
% printOrAdd is an inefficient solution to the task posed above: printOrAdd(, , 0). % even numbers printOrAdd([First | Rest], [First | RestOfEvens], Sum) :- printOrAdd(Rest, RestOfEvens, Sum), 0 is First mod 2. % odd numbers printOrAdd([First | Rest], RestOfEvens, Sum) :- printOrAdd(Rest, RestOfEvens, SumOfRest), 1 is First mod 2, Sum is SumOfRest + First. % printOrAdd1 is a corrected version of printOrAdd which % avoids the unnecessary recursive calls. printOrAdd1(, , 0). printOrAdd1([First | Rest], [First | RestOfEvens], Sum) :- 0 is First mod 2, printOrAdd1(Rest, RestOfEvens, Sum). printOrAdd1([First | Rest], RestOfEvens, Sum) :- 1 is First mod 2, printOrAdd1(Rest, RestOfEvens, SumOfRest), Sum is SumOfRest + First.
?- printOrAdd([1,2,3,4,5,6], Evens, SumOfOdds). Evens = [2, 4, 6], SumOfOdds = 9 ; false.
The first version makes the recursive call in the two recursive rules
before it tests to see if
First is even or odd.
If half the numbers are even and half odd, then clearly half of
the recursive calls will be wasted. However, the situation is actually
much worse than that, because of Prolog's automatic backtracking.
The backtracking means that Prolog will eventually try all three rules
for printOrAdd, and two of them will cause recursive calls, each of
which will in turn generate two recursive calls, each of which ...
Thus for a list of length 100, say, there will be more than 2100
recursive calls. If Prolog could manage a billion recursive calls per
second, 2100 recursive calls would take about 270 seconds,
or about 30 trillion years.
The solution, of course, is to test before you make a recursive call,
as is done in
Always test before you make a recursive call;
never call before you test.