Recursion for going through a family tree and selecting cousins

gman002 · October 19, 2021, 5:43pm

I’m using: SWI-Prolog version(SWISH)

I want the code to:

all_cousins(Person, Degree, ListOfCousins) that takes as arguments (1) the reference person, (2) the degree of cousin relationship (first cousin, second cousin,…) given as an integer and returns the corresponding list of cousins in ListOfCousins.
Ex: all_cousins(john, 1, ListOfCousins) unifies ListOfCousins with a list of all of John’s first cousins.

But what I’m getting is code that infinitely adds the same cousin to an empty list. I’m having trouble recursively gathering all of the cousins I believe. Also, I’m having trouble understanding how I build a list through another rule as I understand lists only have local scope and are emptied with every recursive call.

My code looks like this:

/* Facts */
male(shawn).
male(geo).
male(mark).
male(jake).
female(tia).
female(sussane).
female(derue).
female(debbie).
female(ashley).
female(phadra).
female(naveah).

 /*1 is child of 2*/
child(jake, debbie).
child(geo, shawn).
child(deshaw, shawn).
child(shawn, debbie).
child(naveah, deshaw).
child(mark, derue).
child(debbie, derue).
child(derue, sussane).
child(phadra, ashley).
child(ashley, mark).
child(tia, jake).
child(sean,tia).
child(sarah, jake).
child(john, sean).
child(greatgrandaunt, sussane).
child(jessica, greatgrandaunt).
child(chad, jessica).
child(ned,chad).
child(stanley,ned).
child(hector,stanley).
child(seth,phadra).
child(angelina, seth).

/* Rules */
/*first cousin must share the same grandparent also checks if the parents 
 *  are siblings.*/
firstCousin_of(X,Y):-
    child(X,Z),
    child(Z,C),
    child(Z1,C),
    child(Y,Z1),X \= Y,
    sibling_of(Z1,Z).

firstCousin_of(X,Y):-
    child(X,Z),
    child(Z,C),
    child(Z1,C),
    child(Y,Z1),
	sibling_of(Z1,Z),
    firstCousin_of(Y,X).
firstCousin1_of(X,Y):-
    child(X,Z),
    child(Z,C),
    child(C,P),
    child(Z1,P),
    child(Y,Z1),X \= Y,
    sibling_of(Z1,C).

firstCousin1_of(X,Y):-
    child(X,Z),
    child(Z,C),
    child(C,P),
    child(Z1,P),
    child(Y,Z1),
    sibling_of(Z1,C),
    secondCousin_of(Y,X).

firstCousin2_of(X,Y):-
    child(X,Z),
    child(Z,C),
    child(C,T),
    child(T,H),
    child(S,H),
    child(Y,S),X \= Y,
    sibling_of(T,S).

firstCousin2_of(X,Y):-
    child(X,Z),
    child(Z,C),
    child(C,T),
    child(T,P),
    child(E,P),
    child(Y,E),
	sibling_of(T,P),
    firstCousin_of(Y,X).

firstCousin1d_of(X,Y):-
    child(X,Z),
    child(Z,C),
    child(Z1,C),
    child(H,Z1),
    child(Y,H),X \= Y,
    sibling_of(Z1,Z).

firstCousin1d_of(X,Y):-
    child(X,Z),
    child(Z,C),
    child(Z1,C),
    child(H,Z1),
    child(Y,H),
	sibling_of(Z1,Z),
    firstCousin_of(Y,X).

firstCousin2d_of(X,Y):-
    child(X,Z),
    child(Z,C),
    child(Z1,C),
    child(H,Z1),
    child(T,H),
    child(Y,T),X \= Y,
    sibling_of(Z1,Z).

firstCousin2d_of(X,Y):-
     child(X,Z),
    child(Z,C),
    child(Z1,C),
    child(H,Z1),
    child(T,H),
    child(Y,T),
	sibling_of(Z1,Z),
    firstCousin_of(Y,X).

/*second cousin once removed up*/
secondCousin1_of(X,Y):-
    child(X,Z),
    child(Z,C),
    child(C,T),
    child(T,H),
    child(S,H),
    child(W,S),
    child(Y,W),X \= Y,
    sibling_of(T,S).

secondCousin1_of(X,Y):-
    child(X,Z),
    child(Z,C),
    child(C,T),
    child(T,P),
    child(E,P),
    child(W,E),
    child(Y,W),
	sibling_of(T,P),
    firstCousin_of(Y,X).
    
/*must have the same great grand parent*/

secondCousin_of(X,Y):-
     child(X,Z),
    child(Z,C),
    child(C,P),
    child(Z1,P),
    child(F,Z1),
    child(Y,F),X \= Y,
    sibling_of(Z1,C).

secondCousin_of(X,Y):-
    child(X,Z),
    child(Z,C),
    child(C,P),
    child(Z1,P),
    child(F,Z1),
    child(Y,F),
    sibling_of(Z1,C),
    secondCousin_of(Y,X).

/*must have the same great great grand parent*/

thirdCousin_of(X,Y):-
    child(X,Z),
    child(Z,C),
    child(C,P),
    child(P,G),
    child(Z1,G),
    child(Z2,Z1),
    child(Z3,Z2),
    child(Y,Z3),X \= Y,
	sibling_of(P,Z1).

thirdCousin_of(X,Y):-
    child(X,Z),
    child(Z,C),
    child(C,P),
    child(P,G),
    child(Z1,G),
    child(Z2,Z1),
    child(Z3,Z2),
    child(Z4,Z3),
    sibling_of(P,Z1),
   thirdCousin_of(Z4,Y).

thirdCousin1_of(X,Y):-
    child(X,Z),
    child(Z,C),
    child(C,P),
    child(P,G),
    child(Z1,G),
    child(Z2,Z1),
    child(Z3,Z2),
    child(Z4,Z3),
    child(Y,Z4),X \= Y,
	sibling_of(P,Z1).

thirdCousin1_of(X,Y):-
    child(X,Z),
    child(Z,C),
    child(C,P),
    child(P,G),
    child(Z1,G),
    child(Z2,Z1),
    child(Z3,Z2),
    child(Z4,Z3),
    child(Y,Z4),
    sibling_of(P,Z1),
   thirdCousin_of(Z4,Y).


thirdCousin2_of(X,Y):-
    child(X,Z),
    child(Z,C),
    child(C,P),
    child(P,G),
    child(Z1,G),
    child(Z2,Z1),
    child(Z3,Z2),
    child(Z4,Z3),
    child(Z5,Z4),
    child(Y,Z5),X \= Y,
	sibling_of(P,Z1).

thirdCousin2_of(X,Y):-
    child(X,Z),
    child(Z,C),
    child(C,P),
    child(P,G),
    child(Z1,G),
    child(Z2,Z1),
    child(Z3,Z2),
    child(Z4,Z3),
    child(Z5,Z4),
    child(Y,Z5),
    sibling_of(P,Z1),
   thirdCousin_of(Z4,Y).
/*must have the same great grand parent*/

secondCousin1d_of(X,Y):-
    child(X,Z),
    child(Z,C),
    child(C,P),
    child(Z1,P),
    child(F,Z1),
    child(F1,F),
    child(Y,F1),X \= Y,
    sibling_of(Z1,C).

secondCousin1d_of(X,Y):-
    child(X,Z),
    child(Z,C),
    child(C,P),
    child(Z1,P),
    child(F,Z1),
    child(F1,F),
    child(Y,F1),
    sibling_of(Z1,C),
    secondCousin_of(Y,X).

secondCousin2d_of(X,Y):-
     child(X,Z),
    child(Z,C),
    child(C,P),
    child(Z1,P),
    child(F,Z1),
    child(F1,F),
    child(F2,F1),
    child(Y,F2),X \= Y,
    sibling_of(Z1,C).

secondCousin2d_of(X,Y):-
    child(X,Z),
    child(Z,C),
    child(C,P),
    child(Z1,P),
    child(F,Z1),
    child(F1,F),
    child(F2,F1),
    child(Y,F2),
    sibling_of(Z1,C),
    secondCousin_of(Y,X).




list_append(A,T,T) :- list_member(A,T),!.
list_append(A,T,[A|T]).
list_member(X,[X|_]).
list_member(X,[_|TAIL]) :- list_member(X,TAIL).


sibling_of(Y,Z):-Y \= Z,
child(Y,D),child(Z,D).



all_cousins(Person, 1, ListOfCousins):-
    firstCousin_of(Person,Cousin),
    list_append(Cousin,[],ListOfCousins).

all_cousins(Person, 2, ListOfCousins):-
    secondCousin_of(Person,Cousin),
    list_append(Cousin,[],ListOfCousins).
    
    
all_cousins(Person, 3, ListOfCousins):-
    thirdCousin_of(Person,Cousin),
    list_append(Cousin,[],ListOfCousins).
    
    
    
    all_cousinsRemoved(Person, 1, removed(1, up), ListOfCousins):-
    firstCousin1_of(Person,Cousin),
    list_append(Cousin,[],ListOfCousins).
    all_cousinsRemoved(Person, 1, removed(2, up), ListOfCousins):-
    firstCousin2_of(Person,Cousin),
    list_append(Cousin,[],ListOfCousins).
    all_cousinsRemoved(Person, 1, removed(1, down), ListOfCousins):-
    firstCousin1d_of(Person,Cousin),
    list_append(Cousin,[],ListOfCousins).
    all_cousinsRemoved(Person, 1, removed(2, down), ListOfCousins):-
    firstCousin2d_of(Person,Cousin),
    list_append(Cousin,[],ListOfCousins).

    all_cousinsRemoved(Person, 2, removed(1, up), ListOfCousins):-
   secondCousin1_of(Person,Cousin),
    list_append(Cousin,[],ListOfCousins).
    all_cousinsRemoved(Person, 2, removed(1, down), ListOfCousins):-
   secondCousin1d_of(Person,Cousin),
    list_append(Cousin,[],ListOfCousins).
    all_cousinsRemoved(Person, 2, removed(2, down), ListOfCousins):-
    secondCousin2d_of(Person,Cousin),
    list_append(Cousin,[],ListOfCousins).

   
    all_cousinsRemoved(Person, 3, removed(1, down), ListOfCousins):-
   thirdCousin1_of(Person,Cousin),
    list_append(Cousin,[],ListOfCousins).
  
    all_cousinsRemoved(Person, 3, removed(2, down), ListOfCousins):-
   thirdCousin2_of(Person,Cousin),
    list_append(Cousin,[],ListOfCousins).
    
isSingleChild(Person):-
    
    child(Person,Parent),
    child(Unknownchild , Parent),
    sibling_of(Unknownchild, Person),
     !, fail ; true.

EricGT · October 19, 2021, 5:46pm

This is cross posted on StackOverflow.

prolog family tree locating cousins

gman002 · October 19, 2021, 5:47pm

Is that a problem? The people on stack overflow told me this would be a better place to ask it.

EricGT · October 19, 2021, 5:49pm

No.

You can ask. It may or may not get an answer.

Also if you cross-post a question you should note that, thus my reply.

gman002 · October 19, 2021, 5:50pm

My apologies, I’m new to both stack overflow and SWI-prolog. Thank you for letting me know though ill keep that in mind for future posts.

Boris · October 20, 2021, 4:52am

It is perfectly fine to cross-post, I assume @EricGT is doing the linking only as a way to increase visibility to both this post here and the question on Stackoverflow.

A couple of questions. Why you are reimplementing append/3 and member/2? Both are available in every Prolog implementation and are Prolog folklore. Is there a requirement (by your professor?) to avoid using standard Prolog? Where are the limits? If this is homework, what are the constraints for your solution? In other words, what is allowed and are there artificial requirements (“you must use recursion” or “you must not use library predicates” and such).

EricGT · October 20, 2021, 9:15am

Nope.

Some of the problems with cross posting is that others answering one of the post may not know about the other post and the poster is getting information from one post and using it in the other post. The problem is those trying to help don’t know that someone else may be providing information. It is like the poster is playing a game and there are two opponents on two different sites with the opponents not knowing they are not playing against the poster but someone else.

EricGT · October 20, 2021, 9:52am

@gman002

The need to find cousins is a common question for the Prolog tag on StackOverflow.

See the search results for [prolog] cousin is:answer

Boris · October 20, 2021, 11:42am

Slightly off-topic but I feel strange about this gamification of everything trend. If someone needs help and asks a question, it isn’t exactly an adversarial relationship between them and those who would like to help. Stackoverflow has really poisoned the atmosphere in that respect.

EricGT · October 20, 2021, 11:55am

In this case I don’t see that. The OP just did not know the etiquette.

However, those that note they are cross posting are more likely to seek genuine help, those that knowingly don’t might be trolling.

I only replied earlier because you made an assumption and noted me by name. I just wanted to clarify the reason.

Stackoverflow has not become what I hoped it would. Now that it has been sold, it seems to be moving further away from what I liked about it at the start.

gman002 · October 20, 2021, 4:05pm

I have looked at all of the other cousin prolog questions on stack overflow and here. My school decided to complicate it so it’s a lot different in my opinion. I’ll add the requirements below:

For your basic facts you are not allowed to use any other predicate than male/1, female/1 and child/2. This means that everything else has to be deduced through Prolog rules.
For performance reasons, we want the rule implemented in #3 (isSingleChild/1) to be mostly efficient and only check if the person has at least one sibling: we don’t want Prolog to go through all of the actual siblings beyond the first one. To achieve that, you may use the cut “!” (!/0)
You must provide screenshots displaying how you ran your program and the entire output of your program.

As for reimplementing append/3 and member/2, I think the issue is I don’t really understand list functions all of the examples I’ve read and found online are a lot simpler. Are these functions pre-implemented in the ide? There are no rules against using library predicates. Lastly, I figured recursion would help but it is not a requirement.

gman002 · October 20, 2021, 4:10pm

Another thing I updated the code to what I have now. My issues now are I cannot figure out how to build a list of cousins in the same list because even with recursion the list seems to reset every time we leave the scope. Second, all of my rules to find specific cousins seem very inefficient.

This post(Recursion for going through a family tree and selecting cousins - #12 by gman002) was actually meant for you I tagged the wrong person.

peter.ludemann · October 20, 2021, 5:10pm

I think you need to use setof/3 to get the result into a list.

(In addition to male/1, female/1, child/2, you probably also need not/1 or (\=)/2, and maybe a few other builtins)

Boris · October 20, 2021, 6:39pm

How about setof/3 and bagof/3 or maybe findall/3? Given a set of facts, it is very difficult to make a list without using one of these three predicates.

But this is getting a bit weird, if you have a Prolog lecture at your school you’d hope that the materials you have gotten there have roughly enough information to allow you to solve your homework. Unless the goal of the lecture is to teach you how to get help online; or maybe you are supposed to have been reading a textbook as part of this?

I am bringing this up because getting this kind of unauthorized help can be harmful to your chances of passing the exam for a number of reasons.

gman002 · October 20, 2021, 7:50pm

Thank you for the suggestions ill try them out.

Regarding you concerns, the class is principles of Programming languages. It’s an online course at my school I have to take because they aren’t offering the course in person this semester. Being that it’s online there are no lectures but we do have a book which was not very helpful regarding lists. In the class we write a program in a new language every week as we explore the different languages paradigms and types. Another thing is the class was an accelerated 8 week course. You’ll be happy to hear that the class ended on Sunday October 17th and the prolog program was my last assignment. Anything we’ve been discussing since is just so I can strengthen my understanding of prolog and won’t be used for any grades.

Thank you again for your suggestions I’ll attempt to implement them later.

peter.ludemann · October 21, 2021, 12:15am

One other “trick” (not limited to Prolog) is that when you have a symmetric relationship such as “cousin” or “sibling”, you’ll get duplicates if you’re not careful. One way of avoiding this is to put the two items into a canonical order. So, assuming you have a symmetric_cousin/2 predicate that computes both symmetric_cousin(fred,jane) and symmetric_cousin(jane,fred) by using the rule “two people are cousins if they have the same grandparent”, then you can define

cousin(P1, P2) :-
    symmetric_cousin(P1, P2),
    P1 @< P2. % canonical ordering

(This also prevents you being your own cousin, which you’d get form the naïve definition “has same grandparent”.)

Once you have cousin/2 defined, you can use setof/3 to find all the cousins:

all_cousins(Person, ListOfCousins) :-
    setof(Cousin, cousin(Person,Cousin), ListOfCousins).

Topic		Replies	Views
I need help prolog recursion problem Help! how-to	26	1500	August 18, 2021
Game tree tutorial on Swish (Discussion) Discussion	2	337	July 26, 2019
Beginner: how to generate a list by recursion Help!	3	345	October 10, 2020
Package or something to pretty print a tree? Help!	2	967	July 11, 2019
Listing/1 predicate Predicate	4	424	September 12, 2021

Recursion for going through a family tree and selecting cousins

Related topics