I'm stuck with this recursion which doesn't work as I expect.
Where is my mistake?
#!/usr/bin/prolog
% Facts
mother( jeanne , michel ). % great-grandmother, grandfather
mother( genevieve, aubin ). % grandmother, father
mother( irene , alain ). % great-grandmother, grandfather
mother( emilie , colette ). % great-grandmother, grandmother
mother( colette , muriel ). % grandmother, mother
mother( muriel , eve ). % mother, daughter
father( joseph , michel ). % great-grandfather, grandfather
father( michel , aubin ). % grandfather, father
father( xxx , alain ). % great-grandfather, grandfather
father( marcel , colette ). % great-grandfather, grandmother
father( alain , muriel ). % grandfather, mother
father( aubin , eve ). % father, daughter
% Rules
parent( Mother, Child ) :- mother( Mother, Child ).
parent( Father, Child ) :- father( Father, Child ).
ancestors( [Parent|Ancestors], Child ) :-
parent( Parent, Child ),
ancestors( Ancestors, Parent ).
% Queries
:-
ancestors( Ancestor, eve ),
format( 'Eve ancestors: ~w~n', Ancestor ).
% expected answer is [muriel, colette, alain, emilie, marcel, irene, xxx, aubin, michel, genevieve, joseph, jeanne]
EDIT here is the final solution, thank you all.
#!/usr/bin/prolog
/*##- Facts -##*/
mother( jeanne , michel ).
mother( genevieve, sylvie ).
mother( genevieve, brigitte ).
mother( genevieve, aubin ).
mother( irène , alain ).
mother( émilie , colette ).
mother( colette , muriel ).
mother( colette , olivier ).
mother( colette , audrey ).
mother( colette , stéphane ).
mother( muriel , eve ).
father( joseph , michel ).
father( michel , sylvie ).
father( michel , brigitte ).
father( michel , aubin ).
father( séraphin, alain ).
father( marcel , colette ).
father( alain , muriel ).
father( alain , olivier ).
father( yves , audrey ).
father( yves , stéphane ).
father( aubin , eve ).
/*##- Rules -##*/
parent( Mother, Child ) :- mother( Mother, Child ).
parent( Father, Child ) :- father( Father, Child ).
ancestor( Parent, Child ) :- parent( Parent, Child ).
ancestor( GrandParent, Child ) :-
parent( GrandParent, Parent ),
ancestor( Parent, Child ).
grandMothers( GrandMother, Child ) :-
mother( GrandMother, FatherOrMother ),
parent( FatherOrMother, Child ).
grandsFathers( GrandsFather, Child ) :-
father( GrandsFather, FatherOrMother ),
parent( FatherOrMother, Child ).
parents( Mother, Father, Child ) :-
father( Father, Child ),
mother( Mother, Child ).
strictSiblings( SisterOrBrother, Child ) :-
parents( Mother, Father, Child ),
parents( Mother, Father, SisterOrBrother ),
SisterOrBrother \= Child.
siblings( SisterOrBrother, Child ) :-
mother( Mother, Child ), mother( Mother, SisterOrBrother ), SisterOrBrother \= Child ;
father( Father, Child ), father( Father, SisterOrBrother ), SisterOrBrother \= Child .
/*##- Queries -##*/
theMother :-
mother( Mother, eve ),
format( 'Ève\'s mother: ~w~n', [Mother] ).
theFather :-
father( Father, eve ),
format( 'Ève\'s father: ~w~n', [Father] ).
theParents :-
setof( MotherOrFather, parent( MotherOrFather, eve ), MotherAndFather ),
format( 'Ève\'s parents: ~w~n', [MotherAndFather] ).
theGrandMothers :-
setof( GrandMother, grandMothers( GrandMother , eve ), GrandMothers ),
format( 'Ève\'s grand-mothers: ~w~n', [GrandMothers] ).
theGrandFathers :-
setof( GrandsFather, grandsFathers( GrandsFather , eve ), GrandsPères ),
format( 'Ève\'s grand-fathers: ~w~n', [GrandsPères] ).
lesEnfants :-
setof( Child, parents( genevieve, michel, Child ), Children ),
format( 'Geneviève and Michel children: ~w~n', [Children] ).
theTwoParents :-
parents( Mother, Father, eve ),
format( 'Ève\'s mother and father: ~w, ~w~n', [Mother, Father] ).
theStrictSiblings :-
setof( SisterOrBrother, strictSiblings( SisterOrBrother, muriel ), SistersAndBrothers ),
format( 'Muriel\'s strict siblings: ~w~n', [SistersAndBrothers] ).
theSiblings :-
setof( SisterOrBrother, siblings( SisterOrBrother, muriel ), SistersAndBrothers ),
format( 'Muriel\'s siblings: ~w~n', [SistersAndBrothers] ).
theAncestors :-
setof( Ancestor, ancestor( Ancestor, eve ), Ancestors ),
format( 'Ève\'s ancestors: ~w~n', [Ancestors] ).
:-
theMother,
theFather,
theParents,
theGrandMothers,
theGrandFathers,
lesEnfants,
theTwoParents,
theStrictSiblings,
theSiblings,
theAncestors,
halt( 0 ).
And the output is:
Ève's mother: muriel
Ève's father: aubin
Ève's parents: [aubin,muriel]
Ève's grand-mothers: [colette,genevieve]
Ève's grand-fathers: [alain,michel]
Geneviève and Michel children: [aubin,brigitte,sylvie]
Ève's mother and father: muriel, aubin
Muriel's strict siblings: [olivier]
Muriel's siblings: [audrey,olivier,stéphane]
Ève's ancestors: [alain,aubin,colette,genevieve,irène,jeanne,joseph,marcel,michel,muriel,séraphin,émilie]
Let's do this interactively (in SWI Prolog) instead of in a script which prints the answers at the end using format/2.
We want all possible ancestors of eve in a list.
So we have to
ancestor(A,eve)This is done using one of the predicates bagof/3, setof/3 or findall/3, which backtrack over answers to a goal and unify a variable with a list containing all the answers (with duplicate answers for bagof/3, without duplicate answers for setof/3, and with "no possible answer" yielding [] instead of failure for findall/3).
So we just need to make sure the goal to find any ancestor is correct.
We can state that A is an ancestor of C if
A is a parent of C orA is a parent of some D, and D is an ancestor of C(Note: just 'if', not 'if an only if'. However, it is assumed there are no other ways in which A could possibly be an ancestor of C ... a reasonable "closed world assumption")
The above formulation is well adapted to the search strategy of Prolog, which attempts to resolve a leftmost sub-goal in the body first:
ancestor(A,C) :- parent(A,C).
ancestor(A,C) :- parent(A,D),ancestor(D,C).
Doing it in the way "check for ancestor on the left":
ancestor(A,C) :- parent(A,C).
ancestor(A,C) :- ancestor(A,D),parent(D,C).
should lead to the same result but actually does not: After initially giving good answer, the Prolog Processor will eventually enter an infinite loop, where ancestor(A,C) calls ancestor(A,D). (This would work in the simpler "Datalog" language).
Anyway, are we done?
?- ancestor(X,eve).
X = muriel ;
X = aubin ;
X = jeanne ;
X = genevieve ;
X = irene ;
X = emilie ;
X = colette ;
X = joseph ;
X = michel ;
X = xxx ;
X = marcel ;
X = alain ;
false.
Now collect everything into a list:
(In SWI-Prolog, you have to say that you want long lists printed, not replaced by ellipses, so):
?- set_prolog_flag(answer_write_options,[max_depth(0)]).
true.
And then:
?- bagof(X,ancestor(X,eve),Out).
Out = [muriel,aubin,jeanne,genevieve,irene,emilie,
colette,joseph,michel,xxx,marcel,alain].