Prolog findall Implementation
I've been tasked to implement a version of findall in Prolog without using any Prolog built-ins except for not and cut - so basically in pure Prolog.
I'm trying to search a tree for all direct descendants and return the results in a list
parent(a, b).
parent(b, c).
parent(b, d).
parent(e, d).
What I have so far is:
find(X, L) :- find2(X, [], L).
find2(X, Acc, L) :- parent(Y, X), find2(Y, [Y|Acc], L).
find2(_, Acc, Acc).
What I want to be getting when I enter for example:
find(a,X).
would be:
X = [b, c, d]
(Order not important)
However instead I am getting:
X = [b, c] ;
X = [b, d] ;
X = [b] ;
X = [].
I'm new to Prolog so any help on this would be much appreciated.
Thanks
Besides asserting data as you go, you can also use an extra-logical predicate such as nb_setarg/3. Then once a parent is found, you fail back past nb_setarg and find another parent. All previously found solutions should stay in the term you did nb_setarg on, then after all results are exhausted, the nb_setarg term is the answer. The SWI-Prolog example is good, but its just a counter. Try doing it with a list (or better yet: difference list) that builds as you go.
Take a look at this solution. Note that this solution uses dynamic predicate named queue in order to cache all solutions until all possibilities are exhausted. Once no more solution exists, implementation retracts all facts and composes the list.
This is of course a bit simplified solution, imagine what would happen if two findall would be active at the same time. It is also a bit fragile on exact semantics of assert and retract if particular prolog implementation
Thanks for you help everyone. I managed to sovle it in the end by adding a predicate which checked each item against the current list, and failed if it was already present:
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].
上一篇: 绝对需要ASP.NET MVC 3教程
下一篇: Prolog findall实现