StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POProlog falling into infinite loop
text
Body
copied!<p>I have two problems that have bugged me for hours. <code>connected/2</code> is supposed to judge whether two people are connected or not; <code>distance/3</code> is supposed to measure the kinship. But:</p> <ol> <li>I keep getting <code>true</code>s infinitely for the query <code>connected(x,y)</code>;</li> <li>and I'm getting infinitely increasing <code>N</code> for <code>distance(x,y,N)</code> query. Any suggestions?</li> </ol> <p>Here are my facts:</p> <pre><code>male(ted). male(barney). male(ranjit). male(marshall). male(tony). male(swarley). male(steve). male(chuck). male(john). male(devon). male(morgan). female(robin). female(lily). female(wendy). female(stellar). female(abby). female(victoria). female(carina). female(sarah). female(ellie). married(ted, robin). married(marshall, lily). married(ranjit, wendy). married(stellar, tony). married(steve, carina). married(sarah, chuck). married(ellie, devon). father(ted, barney). father(ted, ranjit). father(marshall, wendy). father(ranjit, stellar). father(tony, abby). father(tony, swarley). father(tony, victoria). father(steve, chuck). father(steve, ellie). father(chuck, john). father(devon, morgan). mother(robin, barney). mother(robin, ranjit). mother(lily, wendy). mother(wendy, stellar). mother(stellar, abby). mother(stellar, swarley). mother(stellar, victoria). mother(carina, chuck). mother(carina, ellie). mother(sarah, john). mother(ellie, morgan). </code></pre> <p>Now, my predicates:</p> <pre><code>parent(X,Y) :- father(X,Y). parent(X,Y) :- mother(X,Y). son(X,Y) :- male(X), parent(Y,X). daughter(X,Y) :- female(X), parent(Y,X). sibling(X,Y) :- parent(Z,X), parent(Z,Y). cousin(X,Y) :- parent(Z,X), parent(W,Y), parent(G,Z), parent(G,W). ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y). ancestor(X,Y) :- parent(X,Y). notmember(X,[]). notmember(X,[H|T]) :- X \= H, notmember(X,T). connected(X,Y,_) :- X == Y. connected(X,Y,Visited) :- ancestor(X,Z), notmember(Z,Visited), connected(Z,Y,[Z|Visited]). connected(X,Y,Visited) :- ancestor(Z,X), notmember(Z,Visited), connected(Z,Y,[Z|Visited]). connected(X,Y,Visited) :- sibling(X,Z), notmember(Z,Visited), connected(Z,Y,[Z|Visited]). connected(X,Y,Visited) :- married(X,Z), notmember(Z,Visited), connected(Z,Y,[Z|Visited]). connected(X,Y) :- connected(X,Y,[X]). minimum(X,[X]). minimum(X,[M,H|T]) :- M =< H, minimum(X,[M|T]). minimum(X,[M,H|T]) :- M > H, minimum(X,[H|T]). distance(X,X,_,0). distance(X,Y,Visited,N) :- parent(X,Z), notmember(Z,Visited), distance(Z,Y,[Z|Visited],N1), N is N1+1. distance(X,Y,Visited,N) :- parent(Z,X), notmember(Z,Visited), distance(Z,Y,[Z|Visited],N1), N is N1+1. distance(X,Y,N) :- distance(X,Y,[],N). </code></pre> <p>EDIT: Thank you, i think i've managed to solve half way through the problems now. Taking @twinterer's advice, I have fixed the predicates like this</p> <pre><code>connected(X,Y,_) :- X == Y. connected(X,Y,V) :- married(X,Z), notmember(Z,V), connected(Z,Y,[Z|V]),!. connected(X,Y,V) :- sibling(X,Z), notmember(Z,V), connected(Z,Y,[Z|V]),!. connected(X,Y,V) :- parent(X,Z), notmember(Z,V), connected(Z,Y,[Z|V]),!. connected(X,Y,V) :- parent(Z,X), notmember(Z,V), connected(Z,Y,[Z|V]),!. connected(X,Y) :- connected(X,Y,[X]). minimum(X,[X]). minimum(X,[M,H|T]) :- M =< H, minimum(X,[M|T]). minimum(X,[M,H|T]) :- M > H, minimum(X,[H|T]). count(X,[],0). count(X,[X|T],N) :- count(X,T,N1), N is N1+1. count(X,[H|T],N) :- X \== H, count(X,T,N1), N is N1. distance(X,X,Visited,0) :- count(X,Visited,N), N =< 1, !. distance(X,Y,Visited,N) :- parent(X,Z), (notmember(Z,Visited)-> distance(Z,Y,[Z|Visited],N1), N is N1+1 ; fail ),!. distance(X,Y,Visited,N) :- parent(Z,X), (notmember(Z,Visited)-> distance(Z,Y,[Z|Visited],N1), N is N1+1 ; fail ),!. distance(X,Y,N) :- findall(N1,distance(X,Y,[X],N1),L),!, minimum(N,L),!. </code></pre> <p>But there is a new set of problems now </p> <ol> <li>it can't take arbitrary queries like <code>distance(X,y,n)</code></li> <li>queries like <code>connected(X,y)</code> return duplicate results</li> </ol> <p>I think removing duplicate results can be achieved by using that <code>findall/3</code> predicate, but I am clueless as to how I can actually implement it.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload