# Recursion for going through a family tree and selecting cousins

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

I want the code to:

1. 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(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(ashley, mark).
child(tia, jake).
child(sean,tia).
child(sarah, jake).
child(john, sean).
child(greatgrandaunt, sussane).
child(jessica, greatgrandaunt).
child(stanley,ned).
child(hector,stanley).
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.

This is cross posted on StackOverflow.

prolog family tree locating cousins

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

No.

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

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.

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).

2 Likes

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.

@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

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.

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.

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.

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.

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)

2 Likes

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.

1 Like

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.

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).