Recursion in Prolog Query

Question

I have a database like this:

traject(departure,arrive,transport).

traject(London,Paris,train).
traject(Paris,Madrid,train).
traject(Madrid,Lisbon,bus).
traject(Madrid,Berlin,plane).
traject(Berlin,Prague,bus).

I have the rule:

connection(Departure,Arrrive):-traject(Departure,Arrive,Transport).
connection(Departure,Arrrive):-traject(Departure,X,Transport),traject(X,Arrive).

With that rule I can know if I ask the query connection(Paris,Lisbon) for example that the answer will be YES.

How can I made a rule and/or a query where I can answer this questions:

A) transport(Paris,Lisbon)

and the answer should come: train and bus

B) traject_between(Paris,Lisbon)

and the answer should come: Madrid

Prolog atoms need to start in a lower-case letter. traject(London,Paris,train). is the same as traject(_,_,train). — Sergey Kalinichenko
You should attempt solving this problem independently, it's not too hard. — Sergey Kalinichenko

Will Ness Will Ness · Accepted Answer · 2015-10-15T00:40:20

To have atom's name starting with upper case letter, use single quotes: traject( 'London', 'Paris', train).

I prefer to use short, suggestive variable names in the code, making it easier to track mentally and visually (YMMV of course):

connect(D,A):- traject(D,A,T).

Later you say you want to see the transport, so why are you ignoring it here? Change this to

connect(D,A,T):- traject(D,A,T).
connect(D,A,T):- traject(D,X,T1), traject(X,A,T2).

you have two transports now, in the second case. Combine them together somehow! A hint: what type of data can hold both two and one entry in it? You will have to change the first clause, too, to be consistent.

Now the new problem is, you ignore the waypoint, X. Another, related one is that you only make two legs in your journey, but what if you need three, or more?

Recursion will help solve both of these problems:

connect(D,A, Xs,Ts):- traject(D,A,T), Xs = ... , Ts = ... .
connect(D,A, Xs,Ts):- traject(D,X,T), 
                      connect(X,A, Xs2,Ts2),  % <---- recursion!
                      Xs = ... ,
                      Ts = ... .

Instead of ..., something sensible must appear. connect(D,A, Xs,Ts) means, Departure and Arrival are connected by a list of waypoints Xs, using transport types Ts. So if D and A are directly connected by just one traject(D,A,Transport) arc, what is the list of waypoints? What is the list of transport types? --- Otherwise, if we can go from D to X in one step using a type of transport T, and X and A are connected with a list of waypoints Xs2 using transport types Ts2, what is the complete list of waypoints? What is the complete list of transport types?

When you finish this, you will be able to define the two predicates that you ask for, quite easily, because the information is already there, in this connect/4 predicate (.../4 means, it has 4 arguments).

Recursion in Prolog Query

1 Answers