% The given data

children(liz,phil,[chuck,anne,andy,ed]).
children(di,chuck,[bill,hank]).
children(queenie,rex,[liz,meg]).
children(sally,andy,[bea]).
children(fifi,rex,[igor]).

female(liz).
female(anne).
female(di).
female(queenie).
female(sally).
female(meg).
female(bea).
female(fifi).

male(phil).
male(chuck).
male(andy).
male(ed).
male(bill).
male(hank).
male(rex).
male(igor).

member(H,[H|_]).
member(H,[_|T]):-member(H,T).

append([],L,L).
append([H|T],L,[H|Y]):-append(T,L,Y).



% X is a mother of Y iff Y appears among the list L of children of
%    X and some male.
% X is a father of Y iff Y appears among the list L of children of 
%    some female and X.
% X is a parent of Y iff X is a father of Y or a mother of Y

mother(X,Y):-children(X,_,L),member(Y,L).
father(X,Y):-children(_,X,L),member(Y,L).
parent(X,Y):-mother(X,Y).
parent(X,Y):-father(X,Y).


% D is a daughter of P iff P is a parent of D and D is female

daughter(D,P):-parent(P,D),female(D).


% To find the list S of sons of X, get the list C of children of X
%   and determine which are sons.  To get the list of children of X,
%   find all lists Y of children by any man, and return the
%   result in a list Z.  If this list is nonempty, combine all of
%   its member lists.  If not, try the same thing for children by 
%   any woman.  Otherwise return the empty list.
% The predicate "appendall" tests whether Z is empty.

sons(X,S):-childlist(X,C),getsons(C,S).
childlist(X,C):-findall(Y,children(X,_,Y),Z),appendall(Z,C),!.
childlist(X,C):-findall(Y,children(_,X,Y),Z),appendall(Z,C),!.
childlist(_,[]).

appendall([H],H).
appendall([H|T],B):-
  appendall(T,W),
  append(H,W,B).
  
% The "getsons" predicate determine which of the members of a list of 
%   children (given as the 1st argument) are sons.  
% This requires only stepping through the
%   list and adding only the members who are male to the output).
% The "getdaughters" predicate works analogously, once a "daughters"
%   predicate has been defined.

getsons([],[]).
getsons([H|T],[H|C]):-male(H),getsons(T,C).
getsons([H|T],C):-female(H),getsons(T,C).

daughters(X,D):-childlist(X,C),getdaughters(C,D).
getdaughters([],[]).
getdaughters([H|T],[H|C]):-female(H),getdaughters(T,C).
getdaughters([H|T],C):-male(H),getdaughters(T,C).


% The descendants of X can be listed as Y in the traditional order
%   if the list of children (sons before daughters) is found to be
%   C, and all the descendants lists of the members of C are combined
%   (by "alldescendants") into Y.
% The predicate "alldescendants" essentially steps through a list and
%   collects the lists of descendants of each member.

descendants(X,Y):-sons(X,S),daughters(X,D),append(S,D,C),
                  alldescendants(C,Y).
alldescendants([],[]).
alldescendants([H|T],Y):-descendants(H,HH),alldescendants(T,TT),
                         append([H|HH],TT,Y).

% This predicate works just like "descendants" except that children
%   are listed in the given order (presumably birth order).

descendants2(X,Y):-childlist(X,C),alldescendants2(C,Y),!.
descendants2(_,[]).

alldescendants2([],[]).
alldescendants2([H|T],Y):-descendants2(H,HH),alldescendants2(T,TT),
                         append([H|HH],TT,Y).