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.

Sergey Kalinichenko · Accepted Answer · 2013-03-07 16:41:48Z

3

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.

edited Mar 7, 2013 at 16:41

answered Mar 7, 2013 at 16:36

Sergey Kalinichenko

729k85 gold badges1.2k silver badges1.6k bronze badges

Sign up to request clarification or add additional context in comments.

11 Comments

Vincent Ramdhanie Over a year ago

can_phone does not need the third variable.

Sergey Kalinichenko Over a year ago

@VincentRamdhanie Thanks! I tried the code, and found the same error.

Danny Rancher Over a year ago

Thank you, I am still confused as how to write message_route with the prototype message_route(A,B,R) as written in the question. Regards.

Sergey Kalinichenko Over a year ago

@DannyRancher You can unify R to [A|Tail] in the body of the rule, like this: message_route(A,B,R) :- can_phone(A,X), message_route(X,B,Tail), R = [A|Tail]. That's the same thing - my guess is that the question asked for R to avoid giving you an implementation hint.

Danny Rancher Over a year ago

@dasblinkenlight I attempted to unify R. Am I doing it correctly. message_route(A,B,[A,B]) :- can_phone(A,B). message_route(A,B,[A|Tail]) :- can_phone(A,X), message_route(X,B,Tail). % message_route(A,B,R) :- can_phone(A,B,R), R = [A,B]. % message_route(A,B,R) :- can_phone(A,B,R), can_phone(A,X), message_route(X,B,Tail), R = [A|Tail].

|

Collectives™ on Stack Overflow

Prolog - Recursive List

1 Answer 1

11 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

11 Comments

Your Answer

Sign up or log in

Post as a guest

Related