Prolog recursion and building output from recursive calls

Question

I am learning Prolog via http://www.learnprolognow.org and I am having some trouble understanding how to recursively build up a variable with results from another recursive call, as per Practical Session 3.4, question 3. The initial problem is a straight-forward recursive call to determine if a route is feasible. But the follow-on problem asks you to show the actual path to get to the end of the route.

We are given the following knowledge base of travel information:

byCar(auckland,hamilton). 
byCar(hamilton,raglan). 
byCar(valmont,saarbruecken). 
byCar(valmont,metz).
byTrain(metz,frankfurt). 
byTrain(saarbruecken,frankfurt). 
byTrain(metz,paris). 
byTrain(saarbruecken,paris).
byPlane(frankfurt,bangkok). 
byPlane(frankfurt,singapore). 
byPlane(paris,losAngeles). 
byPlane(bangkok,auckland). 
byPlane(singapore,auckland). 
byPlane(losAngeles,auckland). 

Write a predicate travel/2 which determines whether it is possible to travel from one place to another by chaining together car, train, and plane journeys. For example, your program should answer yes to the query travel(valmont,raglan).

I solved this problem with the following code:

travel(From,To) :-
 byCar(From,To).

travel(From,To) :-
 byTrain(From,To).

travel(From,To) :-
 byPlane(From,To).

travel(From,To) :-
  byCar(From,NewTo),
  travel(NewTo,To).

travel(From,To) :-
  byTrain(From,NewTo),
  travel(NewTo,To).

travel(From,To) :-
  byPlane(From,NewTo),
  travel(NewTo,To).

The follow-on problem is:

So, by using travel/2 to query the above database, you can find out that it is possible to go from Valmont to Raglan. If you are planning such a voyage, that’s already something useful to know, but you would probably prefer to have the precise route from Valmont to Raglan. Write a predicate travel/3 which tells you which route to take when travelling from one place to another. For example, the program should respond

X  =  go(valmont,metz,go(metz,paris,go(paris,losAngeles)))

to the query travel(valmont,losAngeles,X)

I have been struggling to populate X with a series of go(From,To) that show the successive steps of the journey. It looks like a recursive problem but I do not know how one should go about tackling it. This technique seems fundamental to Prolog programming, and I am quite interested in the thinking process to solve this problem and I look forward to any insight you can provide.

Answer 1

I had a go at this. I made one change to your first solution, just to remove some redundancy. I used the predicate connected/2 to generalize the relationship common to all connections appearing in the by_car/2, by_train/2, and by_plane/2 facts:

connected(From, To) :- by_car(From, To).
connected(From, To) :- by_train(From, To).
connected(From, To) :- by_plane(From, To).

Then I defined travel/2 as a recursive relationship over connected/2:

travel(From, To) :-
    connected(From, To).
travel(From, To) :-
    connected(From, Through),
    travel(Through, To).

Turning to travel/3, notice that the final connection in the nested go... terms is a structure go/2, but the rest are go/3s. So we need to populate X with a series of nested go/3 structures that terminate in a go/2. This last is our base condition. Then it is simply a matter of repeating the second clause of travel/2, but including a go/3 in the third argument that will capture the values instantiated to From and Through on each iteration:

travel(From, To, go(From, To)) :-
    connected(From, To).
travel(From, To, go(From, Through, Route)) :-
    connected(From, Through),
    travel(Through, To, Route).