Prolog Findall Implementación

Question

Se me ha encomendado la implementación de una versión de Findall en Prolog sin usar ningún complemento de Prolog, excepto para no y cortado, básicamente en Prolog puro.

Estoy tratando de buscar un árbol para todos los descendientes directos y devolver los resultados en una lista

parent(a, b). 
parent(b, c). 
parent(b, d). 
parent(e, d). 

Lo que tengo hasta ahora es:

find(X, L) :- find2(X, [], L). 
find2(X, Acc, L) :- parent(Y, X), find2(Y, [Y|Acc], L). 
find2(_, Acc, Acc). 

lo que quiero ser cada vez cuando entro por ejemplo:

find(a,X). 

sería:

X = [b, c, d] 

(Orden no importante)

Sin embargo vez que estoy recibiendo:

X = [b, c] ; 
X = [b, d] ; 
X = [b] ; 
X = []. 

Soy nuevo en Prolog lo que cualquier ayuda en esto sería muy apreciado.

Gracias

Answer 1

Gracias por ayudar a todos. Logré sovle él en el extremo mediante la adición de un predicado que comprueba cada elemento en contra de la lista actual, y fallado si ya estaba presente:

find(X, Loa) :- find(X, [], Loa), !. 
find(X, Acc, Loa) :- dec(Y, X), uList(Y, Acc, AccNew), find(X, AccNew, Loa). 
find(_, Acc, Acc). 

dec(X,Y) :- parent(X,Y). 
dec(X,Y) :- parent(X,Z), dec(Z,Y). 

uList(X, [], [X]) :- !. 
uList(H, [H|_], _) :- !, fail. 
uList(X, [H|T], L) :- uList(X, T, Rtn), L = [H|Rtn]. 

Answer 2

Echa un vistazo a this solution. Tenga en cuenta que esta solución utiliza el predicado dinámico denominado cola para almacenar en caché todas las soluciones hasta que se hayan agotado todas las posibilidades. Una vez que no existe más solución, la implementación retracta todos los hechos y compone la lista.

Esto es, por supuesto, una solución un poco simplificada, imagine lo que sucedería si dos findall estuvieran activos al mismo tiempo. También es un poco frágil en la semántica exacta de afirmar y retraer si implementación de prólogo particular

Answer 3

Además de afirmar los datos sobre la marcha, también puede utilizar un predicado extra-lógico como nb_setarg/3. Luego, una vez que se encuentra uno de los padres, usted vuelve atrás de nb_setarg y encuentra otro padre. Todas las soluciones encontradas anteriormente deberían permanecer en el término en el que realizó nb_setarg, luego de que se hayan agotado todos los resultados, el término nb_setarg es la respuesta. El ejemplo de SWI-Prolog es bueno, pero es solo un contador. Intente hacerlo con una lista (o mejor aún: lista de diferencias) que se crea a medida que avanza.

Answer 4

Aquí es una solución que utiliza colas y los hilos de SWI-Prolog. Utiliza la antigua API existente y hace algo a lo largo de Tarau's Engines. Supongo que la creación del hilo copiará la plantilla y el objetivo. Y luego supongo que el envío de la cola volverá a hacer una copia de cada solución.

Por lo tanto, en comparación con el clasificador clásico, tendrá un excedente en una plantilla y una copia del objetivo, pero de lo contrario también copiará cada solución como el clasificador clásico. Fuente en la esencia here. Pero por modding threadall2, lo que hace la colección, se podría también aplicar todo tipo de agregados:

% threadall(+Term, +Goal, -List) 
threadall(T, G, L) :- 
    message_queue_create(J, [max_size(1)]), 
    thread_create(threadall3(T, G, J), _, [detached(true)]), 
    thread_get_message(J, A), 
    threadall2(J, A, L), 
    message_queue_destroy(J). 

% threadall3(+Term, +Goal, +Queue) 
threadall3(T, G, J) :- 
    G, thread_send_message(J, the(T)), fail. 
threadall3(_, _, J) :- 
    thread_send_message(J, no). 

% threadall2(+Queue, +Term, -List) 
threadall2(J, the(T), [T|L]) :- !, 
    thread_get_message(J, A), 
    threadall2(J, A, L). 
threadall2(_, no, []). 

Aquí se muestra un ejemplo de ejecución. Espero haber hecho la contabilidad correctamente. El subproceso se creó con detach (true), por lo que no necesitamos ningún identificador cuando finaliza el subproceso.La cola de mensajes se destruye explícitamente. Éstos son algunos ejemplo se ejecuta en SWI-Prolog, vemos que funciona como se esperaba:

Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 7.3.23) 
Copyright (c) 1990-2015 University of Amsterdam, VU Amsterdam 

?- threadall(X, between(0, 5, X), L). 
L = [0, 1, 2, 3, 4, 5]. 

?- threadall(X-Y, (between(0, 2, X), 
        threadall(Z, between(0, 2, Z), Y)), L). 
L = [0-[0, 1, 2], 1-[0, 1, 2], 2-[0, 1, 2]]. 

Nuestro código sólo implementa el camino habitual feliz: Sólo en práctica el mensaje y the/1no/0. Además, dado que no usamos setup_call_cleanup/3, tampoco es seguro utilizar la solución con interrupciones. Además, el último argumento no es firme. Todo esto queda como un ejercicio para que el lector implemente estos requisitos adicionales y las rutas alternativas correspondientes.