Prolog list question

Question

I have a database consisting of the following rules;

speaks(fred [german, english, dutch]).
speaks(mary [spanish, arabic, dutch]).
speaks(jim [norwegian, italian, english]).
speaks(sam [polish, swedish, danish]).

etc

As part of a much larger program, how would I find out 3 people who speak the same language?

Jen

Answer 1

It's been a while, so there might be some syntax glitches, but I hope you get the idea...

% Find out whether an element is contained in a list
in_list(X,[X|_]).
in_list(X,[First|Rest]) :- in_list(X,Rest).

% Find out 3 people who speak the same language
findspeakers(Language, X1, X2, X3) :- speaks(X1, L1), speaks(X2, L2), speaks(X3, L3), in_list(Language, L1), in_list(Language, L2), in_list(Language, L3).

Pretty simple solution using list operators (I didn't remember whether there was a built-in rule for finding out whether a variable is contained in a list, so I rewrote it).

You can find out groups of three people speaking English with the following command:

findspeakers('English', X1, X2, X3).

You can find all groups of three people speaking a common language with the following command:

findspeakers(Language, X1, X2, X3).

NOTE: These commands will give you all possible combinations of groups of three people, so if you have four people speaking English, the first command will give you four result sets.

Answer 2

As it is, Franz' solution will not work: it returns triples of prople which speak the same language, but these triples may contain duplicates. Thus one would still have to resort to e.g. sort/2 and length/2 to find the answer to the original question:

?- findspeakers(Language, X1, X2, X3), sort([X1, X2, X3], Y), length(Y, 3).
false.

(So the answer is no, there are no three people speaking the same language.) Anyway, I think a more elegant solution exists:

spoken(L, S) :-
  speaks(S, LL), member(L, LL).

same_language(N, L, SS) :-
  bagof(S, spoken(L, S), SS), length(SS, N).

The predicate spoken/2 uses member/2 and succeeds if language L is spoken by person S. same_language/3 succeeds if the list SS contains N distinct people, all of which speak language L. This predicate uses bagof/3; if the definition of the speak/2 predicate contains duplicate data, then you should use setof/3 instead.

Observe that this nicely generalises the problem: we can now answer the question for any n, not just 3. Demonstration:

?- same_language(3, L, SS).
false.

?- same_language(2, L, SS).
L = dutch,
SS = [fred, mary] ;
L = english,
SS = [fred, jim] ;
false.