Comparing list element structures to each other in Prolog

Question

I am working through sample questions while studying, using SWI-Prolog. I have reached the last section of this question, where I have to recursively (I hope) compare elements of a list containing 'researcher' structures to determine whether or not the researchers have the same surname, and, if they do, return the Forename and Surname of the group leader for that list.

There is only one list that meets this criteria and it has four members, all with the same surname. However, the correct answer is returned FOUR times. I feel my solution is inelegant and is lacking. Here is the question:

The following Prolog database represents subject teaching teams.

% A research group structure takes the form
% group(Crew, Leader, Assistant_leader).
%
% Crew is a list of researcher structures,
% but excludes the researcher structures for Leader
% and Assistant_leader.
%
% researcher structures take the form
% researcher(Surname, First_name, expertise(Level, Area)).

group([researcher(giles,will,expertise(3,engineering)),
researcher(ford,bertha,expertise(2,computing))],
researcher(mcelvey,bob,expertise(5,biology)),
researcher(pike,michelle,expertise(4,physics))).

group([researcher(davis,owen,expertise(4,mathematics)),
researcher(raleigh,sophie,expertise(4,physics))],
researcher(beattie,katy,expertise(5,engineering)),
researcher(deane,fergus,expertise(4,chemistry))).

group([researcher(hardy,dan,expertise(4,biology))],
researcher(mellon,paul,expertise(4,computing)),
researcher(halls,antonia,expertise(3,physics))).

group([researcher(doone,pat,expertise(2,computing)),
researcher(doone,burt,expertise(5,computing)),
researcher(doone,celia,expertise(4,computing)),
researcher(doone,norma,expertise(2,computing))],
researcher(maine,jack,expertise(3,biology)),
researcher(havilland,olive,expertise(5,chemistry))).

Given this information, write Prolog rules (and any additional predicates required) that can be used to return the following:

the first name and surname of any leader whose crew members number more than one and who all have the same surname. [4 marks]

This is the solution I presently have using recursion, though it's unnecessarily inefficient as for every member of the list, it compares that member to every other member. So, as the correct list is four members long, it returns 'jack maine' four times.

surname(researcher(S,_,_),S).

checkSurname([],Surname):-
    Surname==Surname. % base case 

checkSurname([Researcher|List],Surname):-
    surname(Researcher,SameSurname),
    Surname == SameSurname,
    checkSurname(List,SameSurname).

q4(Forename,Surname):-
    group(Crew,researcher(Surname,Forename,_),_),
    length(Crew,Length),
    Length > 1,
    member(researcher(SameSurname,_,_),Crew),
    checkSurname(Crew,SameSurname).

How could I do this without the duplicate results and without redundantly comparing each member to every other member each time? For every approach I've taken I am snagged each time with 'SameSurname' being left as a singleton, hence having to force use of it twice in the q4 predicate.

Current output

    13 ?- q4(X,Y).
    X = jack,
    Y = maine ;  x4

Answer 1

You are doing it more complicated than it has to be. Your q4/2 could be even simpler:

q4(First_name, Surname) :-
    group(Crew, researcher(Surname, First_name, _E), _A),
    length(Crew, Len), Len > 1,
    all_same_surname(Crew).

Now you only need to define all_same_surname/1. The idea is simple: take the surname of the first crew member and compare it to the surnames of the rest:

all_same_surname([researcher(Surname, _FN, _E)|Rest]) :-
    rest_same_surname(Rest, Surname).

rest_same_surname([], _Surname).
rest_same_surname([researcher(Surname, _FN, _E)|Rest), Surname) :-
    rest_same_surname(Rest, Surname).

(Obviously, all_same_surname/1 fails immediately if there are no members of the crew)

This should be it, unless I misunderstood the problem statement.

?- q4(F, S).
F = jack,
S = maine.

How about that?

Note: The solution just takes the most straight-forward approach to answering the question and being easy to write and read. There is a lot of stuff that could be done otherwise. Since there is no reason not to, I used pattern matching and unification in the heads of the predicates, and not comparison in the body or extra predicates for extracting arguments from the compound terms.

P.S. Think about what member/2 does (look up its definition in the library, even), and you will see where all the extra choice points in your solution are coming from.

Answer 2

A compact and efficient solution:

q4(F, S) :-
    group([researcher(First,_,_), researcher(Second,_,_)| Crew], researcher(S, F, _), _),
    \+ (member(researcher(Surname, _, _), [researcher(Second,_,_)| Crew]), First \== Surname).

Example call (resulting in a single solution):

?- q4(X,Y).
X = jack,
Y = maine.

Answer 3

Boris did answer this question already, but I want to show the most concise solution I could come with. It's just for the educational purposes (promoting findall/3 and maplist/2):

q4(F, S) :-
    group(Crew, researcher(S, F, _), _),
    findall(Surname, member(researcher(Surname, _, _), Crew), Surnames),
    Surnames = [ First, Second | Rest ],
    maplist(=(First), [ Second | Rest ]).