agregado/3 en swi-prolog

Question

Necesito contar todos X, que some_predicate(X) y realmente hay un montón de tales X. ¿Cuál es la mejor manera de hacerlo?

La primera pista es encontrarlo todo, acumularlo en una lista y devolverlo.

countAllStuff(X) :- 
    findall(Y 
      , permutation([1,2,3,4,5,6,7,8,9,10], Y) 
      , List 
      ), 
    length(List, X). 

(permutation/2 es único ejemplo que muestra que hay muchas variantes y es mala manera de recolectar todo)

Obviamente, he apilar-desbordamiento.

?- countAllStuff(X). 
ERROR: Out of global stack 

Than, estoy tratando de reemplazar a findallsetof y nada cambia.

Por fin, he fundado los predicados aggregate (clics) y trato de usarlo.

?- aggregate(count, permutation([1,2,3,4], X), Y). 
X = [1, 2, 3, 4], 
Y = 1 . 

?- aggregate(count, [1,2,3,4], permutation([1,2,3,4], X), Y). 
X = [1, 2, 3, 4], 
Y = 1 ; 
X = [1, 2, 4, 3], 
Y = 1 ; 

Todo está mal, creo. Prefiero obtener algo como

?- aggregate(count, permutation([1,2,3,4], X), Y). 
Y = 24 . 

1) ¿Qué estoy haciendo mal?

2) ¿Cómo puedo declarar el predicado para obtener la respuesta correcta?

Answer 1

utilizar una variable cuantificada existencialmente, como lo haría con setof:

?- aggregate(count, X^permutation([1,2,3,4], X), N). 
N = 24. 

Answer 2

Existe también aggregate_all/3:

?- aggregate_all(count, permutation([1, 2, 3, 4], _), Total). 
Total = 24. 

Sin embargo, en cuanto a tiempo de ejecución y desbordamientos de pila están preocupados que parece funcionar igualmente bien a su findall + length solución:

?- N is 10^7, time(aggregate_all(count, between(1, N, _), Total)). 
% 10,000,022 inferences, 5.075 CPU in 5.089 seconds (100% CPU, 1970306 Lips) 
N = Total, Total = 10000000. 

?- N is 10^7, time((findall(X, between(1, N, _), L), length(L, Total))). 
% 10,000,013 inferences, 4.489 CPU in 4.501 seconds (100% CPU, 2227879 Lips) 
N = 10000000, 
L = [_G30000569, _G30000566, _G30000545|...], 
Total = 10000000. 

?- N is 10^8, aggregate_all(count, between(1, N, _), Total). 
ERROR: Out of global stack 

?- N is 10^8, findall(X, between(1, N, _), L), length(L, Total). 
ERROR: Out of global stack 

Puede contar las soluciones utilizando assert/retract, esto es bastante lento, pero sí evitar la "de pila" problema:

?- assert(counter(0)), N is 10^8, between(1, N, _), 
    retract(counter(C)), C1 is C + 1, assert(counter(C1)), fail 
    ; retract(counter(C)). 
C = 100000000. 

Answer 3

En SWI-Prolog existe una versión mucho más eficiente, que también evitar bloqueando la tienda global. Así que simplemente usando nb_setval y nb_getval se gana al menos 3 veces el rendimiento (más en multihilo). Hace poco tiempo, otra pregunta era sobre las soluciones de conteo. Al ser la base de la agregación, es un punto de parada obvio al aprender Prolog. Para evaluar la ganancia de eficiencia conseguimos el uso de estas llamadas monofilamento semánticamente equivalentes:

count_solutions(Goal, N) :- 
assert(count_solutions_store(0)), 
repeat, 
( call(Goal), 
    retract(count_solutions_store(SoFar)), 
    Updated is SoFar + 1, 
    assert(count_solutions_store(Updated)), 
    fail 
; retract(count_solutions_store(N)) 
), !. 
:- dynamic count_solutions_store/1. 

% no declaration required here 
count_solutions_nb(Goal, N) :- 
    nb_setval(count_solutions_store, 0), 
    repeat, 
    ( call(Goal), 
     nb_getval(count_solutions_store, SoFar), 
     Updated is SoFar + 1, 
     nb_setval(count_solutions_store, Updated), 
     fail 
    ; nb_getval(count_solutions_store, N) 
    ), !. 

parent(jane,dick). 
parent(michael,dick). 
parent(michael,asd). 

numberofchildren(Parent, N) :- 
    count_solutions_nb(parent(Parent, _), N). 

many_solutions :- 
    between(1, 500000, _). 

time_iso :- 
    time(count_solutions(many_solutions, N)), 
    write(N), nl. 

time_swi :- 
    time(count_solutions_nb(many_solutions, N)), 
    writeln(N). 

En mi sistema, me sale

?- [count_sol]. 
% count_sol compiled 0,00 sec, 244 bytes 
true. 

?- time_iso. 
tim% 1,000,006 inferences, 2,805 CPU in 2,805 seconds (100% CPU, 356510 Lips) 
500000 
true. 

?- time_swi. 
% 2,000,010 inferences, 0,768 CPU in 0,768 seconds (100% CPU, 2603693 Lips) 
500000 
true.