CODEWITHSUNDEEP
listrecursionprologtail-recursion
Cheesegraterr
Cheesegraterr

Reputation: 517

prolog - tail recursion issue

I am new to prolog and I am trying to create a predicate and am having some trouble.

I have a list of cities that are connected via train. They are connected via my links/2 clause.

links(toronto, ajax).
links(toronto, markham).
links(toronto, brampton).
links(brampton, markham).
links(markham, ajax).
links(brampton, mississauga).
links(mississauga, toronto).
links(mississuaga, oakville).
links(oakville, st.catharines).
links(oakville, hamilton).
links(hamilton, st.catharines).

I am writing a predicate called addnewcities which will take a list of cities and then return a new list containing the original list, plus all the cities that are directly connected to each of the cities in the original list.

Here is a (rough looking) visual representation of the links. enter image description here

If my input list was [toronto] I want my output to be (order doesnt matter) [ajax,markham,brampton,mississauga,toronto].

If input was [oakville,hamilton] I want the output to be [mississauga,st.catharines,oakville,hamilton].

Here is my predicate so far.

addnewcities([],_).
addnewcities([CitiesH|Tail],Ans):- directer(CitiesH,Ans2),  merger(Ans2,[CitiesH],Ans), addnewcities(Tail,Ans).

directer/2 takes a city and saves a list containing all the directly connected cities in the second arg.

merger/3 just merges two lists making sure there are no duplicates in the final list.

When my input is a list with one element ie [toronto] it works! But when I have a list with multiple elements [toronto,ajax] it says "false" every time.

I'm pretty sure my issue is that when it recurses for the second time, merge is what says its false. I just don't know how to get around this so that my list can keep being updated instead of being checked if true or false.

Any help is appreciated!

Upvotes: 0

Views: 275

Answers (2)

Guillermo Merino
Guillermo Merino

Reputation: 3257

This should work for what you want:

addcities(A,B):-
    addcitiesaux(A,[],B).

addcitiesaux([],X,X).

addcitiesaux([X|Xs],L,R):-
    link(X,A),
    \+ member(A,L),
    !,
    addcitiesaux([X|Xs],[A|L],R).

addcitiesaux([X|Xs],L,R):-
    link(A,X),
    \+ member(A,L),
    !,
    addcitiesaux([X|Xs],[A|L],R).

 addcitiesaux([X|Xs],L,R):-
    addcitiesaux(Xs,[X|L],R).

Upvotes: 1

CapelliC
CapelliC

Reputation: 60004

this query uses library support to solve the problem:

addcities(Cs, L) :-
  setof(D, C^(member(C,Cs), (C=D;link(C,D);link(D,C))), L).

Upvotes: 1

Related Questions