Prolog - Recursive List

Question

Here is my question: A small club decided to set up a telephone network for urgent messages amongst its members. The following arrangement was agreed: Anne can phone both Bill and Mary. Bill can phone both Tom and Sue. Tom can phone both Liz and Frank. Liz can also phone Frank if necessary.

Express this information as seven Prolog facts of the form can_phone(anne,bill). Now write recursive Prolog rules for a predicate message_route such that message_route(A,B,R) is true if A can pass a message to B routed via the people in list R, using the club’s telephone arrangements. For example, message_route(anne,frank,[anne,bill,tom,liz,frank]) would be true (because anne can phone bill, who can phone tom, who can phone liz, who can phone frank).

I have this so far:

can_phone(anne,bill).
can_phone(anne,mary).
can_phone(bill,tom).
can_phone(bill,sue).
can_phone(tom,liz).
can_phone(tom,frank).
can_phone(liz,frank).

For my message_route, I have experimented and have this working which allows me to complete the second part of the question without the requirement of restricting the list to a specified list of persons (R).

message_route(A,B) :- can_phone(A,B).
message_route(A,B) :- can_phone(A,X), message_route(X,B).

I don't understand how to implement this list in my answer.

Answer 1

Accumulating a list is relatively straightforward: first, observe that if A can call B directly, the list is simply [A, B]. Hence, we can rewrite your first rule as

message_route(A,B,[A,B]) :- can_phone(A,B).

The second rule is a bit trickier: you need to unify to a list produced by message_route, and insert A at its head. Note that you do not need to insert X or B, because they would be provided by the returned list:

message_route(A,B,[A|Tail]) :- can_phone(A,X), message_route(X,B,Tail).

Here is a small demo that uses your data.

Note that this code would be chasing its own tail if the data that you present represents a graph with loops, rather than a tree. To avoid this, you could avoid picking X if it is already part of the Tail list.