Comment exprimer «ancêtre» de manière récursive
Je suis coincé avec cette récursivité qui ne fonctionne pas comme prévu.
Où est mon erreur?
#!/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 voici la solution finale, merci à tous.
#!/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 ).
Et le résultat est:
È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]
Réponses
Faisons cela de manière interactive (dans SWI Prolog) plutôt que dans un script qui imprime les réponses à la fin en utilisant format/2.
Nous voulons tous les ancêtres possibles de evedans une liste.
Alors nous devons
- interroger le programme Prolog pour toutes les solutions possibles à l'objectif
ancestor(A,eve) - puis rassemblez-les dans une liste
Cela se fait en utilisant l'un des prédicats bagof/3, setof/3ou findall/3, qui revient en arrière sur les réponses à un objectif et unifie une variable avec une liste contenant toutes les réponses ( avec des réponses en double pour bagof/3, sans réponses en double pour setof/3, et avec "pas de réponse possible" cédant []au lieu de échec pour findall/3).
Nous devons donc simplement nous assurer que l'objectif pour trouver un ancêtre est correct.
Nous pouvons affirmer que Ac'est un ancêtre de Cif
Aest parent deCouAest un parent de certainsD, etDest un ancêtre deC
(Remarque: juste 'si', pas 'si un seulement si'. Cependant, on suppose qu'il n'y a pas d' autres moyens qui Apourraient éventuellement être un ancêtre de C... une "hypothèse de monde fermé" raisonnable)
La formulation ci-dessus est bien adaptée à la stratégie de recherche de Prolog, qui tente d'abord de résoudre un sous-objectif le plus à gauche dans le corps:
ancestor(A,C) :- parent(A,C).
ancestor(A,C) :- parent(A,D),ancestor(D,C).
En procédant de la manière "vérifier l'ancêtre à gauche":
ancestor(A,C) :- parent(A,C).
ancestor(A,C) :- ancestor(A,D),parent(D,C).
devrait conduire au même résultat mais ne le fait pas: après avoir initialement donné une bonne réponse, le processeur Prolog entrera finalement dans une boucle infinie, où ancestor(A,C)appelle ancestor(A,D). (Cela fonctionnerait dans le langage plus simple "Datalog").
Bref, avons-nous fini?
?- 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.
Maintenant, rassemblez tout dans une liste:
(Dans SWI-Prolog, vous devez dire que vous voulez imprimer de longues listes, non remplacées par des ellipses, donc):
?- set_prolog_flag(answer_write_options,[max_depth(0)]).
true.
Et alors:
?- bagof(X,ancestor(X,eve),Out).
Out = [muriel,aubin,jeanne,genevieve,irene,emilie,
colette,joseph,michel,xxx,marcel,alain].