More and more Prolog systems support the built-in
term_singletons/2 which gives a list of the singleton
variables of a Prolog term. Unfortunately because of
term sharing in a Prolog term, many algorithms are not linear in the number of nodes of the Prolog term. One can observe a kind of explosion:
/* SWI-Prolog 9.1.16 */
bomb(0, 1) :- !.
bomb(N, (X+X)) :- M is N-1, bomb(M, X)
?- between(23,27,N), bomb(N,X),
time(term_singletons(X,_)), fail; true.
% -1 inferences, 0.078 CPU in 0.074 seconds (106% CPU, -13 Lips)
% -1 inferences, 0.141 CPU in 0.153 seconds (92% CPU, -7 Lips)
% -1 inferences, 0.328 CPU in 0.322 seconds (102% CPU, -3 Lips)
% -1 inferences, 0.672 CPU in 0.667 seconds (101% CPU, -1 Lips)
% -1 inferences, 1.344 CPU in 1.350 seconds (100% CPU, -1 Lips)
true.
How would one implement term_singletons/2 that stays
linear in the above case?