如何递归表达"ancestor"

Question

我被这个递归困住了，它没有像我预期的那样工作。

我的错误在哪里？

#!/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]

编辑最后的解决方案，谢谢大家。

#!/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 ).

输出为：

È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]

Answer 1

让我们以交互方式（在 SWI Prolog 中）执行此操作，而不是在使用 format/2.

在末尾打印答案的脚本中

我们想要列表中 eve 的所有可能祖先。

所以我们必须

查询 Prolog 程序以获得目标的所有可能解决方案 ancestor(A,eve)
然后将它们收集到列表中

这是使用谓词 bagof/3、setof/3 或 findall/3 之一完成的，它回溯目标的答案并将变量与包含所有答案的列表统一 ( 有 bagof/3的重复答案，没有 setof/3的重复答案，并且“没有可能的答案”产生[] 而不是失败 findall/3).

所以我们只需要确保找到任何祖先的目标是正确的。

我们可以说 A 是 C 的祖先 if

A 是 C 或
A 是某些 D 的父代，D 是 C

（注意：只是 'if'，而不是 'if an only if'。但是，假设没有 其他方式 A可能是 C 的祖先......一个合理的“封闭世界假设”）

上面的公式很好地适应了 Prolog 的搜索策略，它首先尝试解析正文中最左边的 sub-goal：

ancestor(A,C) :- parent(A,C).
ancestor(A,C) :- parent(A,D),ancestor(D,C).

按照“在左侧检查祖先”的方式进行：

ancestor(A,C) :- parent(A,C).
ancestor(A,C) :- ancestor(A,D),parent(D,C).

应该导致相同的结果但实际上不会：在最初给出正确答案后，Prolog 处理器最终将进入无限循环，其中 ancestor(A,C) 调用 ancestor(A,D)。（这将适用于更简单的“Datalog”语言）。

无论如何，我们完成了吗？

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

现在将所有内容收集到一个列表中：

（在SWI-Prolog中，你必须说你想要打印长列表，而不是用省略号代替，所以）：

?- set_prolog_flag(answer_write_options,[max_depth(0)]).
true.

然后：

?- bagof(X,ancestor(X,eve),Out).
Out = [muriel,aubin,jeanne,genevieve,irene,emilie,
       colette,joseph,michel,xxx,marcel,alain].

如何递归表达"ancestor"

How to express "ancestor" recursively

recursion

prolog

transitive-closure