Prolog list recursion

1
votes

The goal of my predicate is: 

?- line_terminal_stations(east_london, StartsAt, EndsAt).
StartsAt = shoreditch
EndsAt = new_cross

Below is what I have so far, the recursion works as expected and progressively creates a list of stations on the line.

line_terminal_stations(LineName, StationX, StationY):-
    next_station(LineName, StationX, StationY, []).

next_station(LineName, StationX, StationY, V) :-

    link(StationX, StationY, LineName),
    next_station(LineName, StationY, _, [StationX | V]).

However once the final station has been found the predicate fails and begins to 'undo' the list. Whereas when link/3 fails, i want to end the recursion so i can extract the first and last station of the list.

Examples of link/3:

link(shoreditch, whitechapel, east_london).
link(whitechapel, shadwell, east_london).

Example of run-through: 

line_terminal_stations(east_london, StartsAt, EndsAt).

Redo: (9) link(_G3031, _G3032, east_london) ? creep
Exit: (9) link(whitechapel, shadwell, east_london) ? creep
Call: (9) next_station(east_london, shadwell, _G3128, [whitechapel]) ? creep
Call: (10) link(shadwell, _G3127, east_london) ? creep
Exit: (10) link(shadwell, wapping, east_london) ? creep
Call: (10) next_station(east_london, wapping, _G3131, [shadwell, whitechapel]) ? creep
Call: (11) link(wapping, _G3130, east_london) ? creep
Exit: (11) link(wapping, rotherhithe, east_london) ? creep
Call: (11) next_station(east_london, rotherhithe, _G3134, [wapping, shadwell, whitechapel]) ? creep
Call: (12) link(rotherhithe, _G3133, east_london) ? creep
Exit: (12) link(rotherhithe, surrey_docks, east_london) ? creep
Call: (12) next_station(east_london, surrey_docks, _G3137, [rotherhithe, wapping, shadwell, whitechapel]) ? creep
Call: (13) link(surrey_docks, _G3136, east_london) ? creep
Exit: (13) link(surrey_docks, new_cross_gate, east_london) ? creep
Call: (13) next_station(east_london, new_cross_gate, _G3140, [surrey_docks, rotherhithe, wapping, shadwell, whitechapel]) ? creep
Call: (14) link(new_cross_gate, _G3139, east_london) ? creep
Fail: (14) link(new_cross_gate, _G3139, east_london) ? creep
Fail: (13) next_station(east_london, new_cross_gate, _G3140, [surrey_docks, rotherhithe, wapping, shadwell, whitechapel]) ? creep
Redo: (13) link(surrey_docks, _G3136, east_london) ? creep
Exit: (13) link(surrey_docks, new_cross, east_london) ? creep
Call: (13) next_station(east_london, new_cross, _G3140, [surrey_docks, rotherhithe, wapping, shadwell, whitechapel]) ? creep
Call: (14) link(new_cross, _G3139, east_london) ? creep
Fail: (14) link(new_cross, _G3139, east_london) ? creep
Fail: (13) next_station(east_london, new_cross, _G3140, [surrey_docks, rotherhithe, wapping, shadwell, whitechapel]) ? creep
Fail: (12) next_station(east_london, surrey_docks, _G3137, [rotherhithe, wapping, shadwell, whitechapel]) ? creep
Fail: (11) next_station(east_london, rotherhithe, _G3134, [wapping, shadwell, whitechapel]) ? creep
Fail: (10) next_station(east_london, wapping, _G3131, [shadwell, whitechapel]) ? creep
Fail: (9) next_station(east_london, shadwell, _G3128, [whitechapel]) ? creep
2
prolog
Could you add the link/3 and some sample data also? – Limmen

2 Answers

0
votes

One approach with minimum code changes would be:

link(shoreditch, whitechapel, east_london).
link(whitechapel, shadwell, east_london).

line_terminal_stations(LineName, First, Last):-
    next_station(LineName, _, _, [], Stations),
    Stations = [Last|_],
    last(Stations, First).

next_station(LineName, StationX, StationY, V, [StationX|V]) :-
\+ link(StationX, StationY, LineName).

next_station(LineName, StationX, StationY, V, Stations) :-
    link(StationX, StationY, LineName),
    next_station(LineName, StationY, _, [StationX | V], Stations).

Test run:

[debug]  ?- line_terminal_stations(east_london, StartsAt, EndsAt).
StartsAt = shoreditch,
EndsAt = shadwell

But as it stands the link/3 requires to be in the right order to first find the true startstation. I.e you can backtrack and find different start-station:

[debug]  ?- line_terminal_stations(east_london, StartsAt, EndsAt).
StartsAt = shoreditch,
EndsAt = shadwell ;
StartsAt = whitechapel,
EndsAt = shadwell
0
votes

But you need recursion?

If the line isn't a ring, you can simply impose that StartAt is a starting point, but not an ending point, and that EndAt is a ending point, but not a starting point.

I mean 

line_terminal_stations(Line, StartsAt, EndsAt) :-
  link(StartsAt, _, Line),
  \+ link(_, StartsAt, Line),
  link(_, EndsAt, Line),
  \+ link(EndsAt, _, Line).