How can I prevent prolog from backtracking and deleting my list?

Question

I am working on a homework question and I think that I have gotten very close but I can't quite figure out how to get my program to return the list instead of recursively deleting it on the return.

The code is meant to check through the given met facts and try to determine if the goal person is sick because of a related sickness that happened in the office. Each person is infectious for 7 days once they are in contact with a sick person and we want to return a list that contains the possible infection pathway to the final person from the given start person.

mymember in the code has the same functionality as member

My code is

mymember(X, [X|_]).
mymember(X, [_|Z]) :- 
mymember(X,Z).

met(john,28,mary).
met(john,3,mary).
met(peter,21,john).
met(mary,23,mark).
met(anne,19,peter).
met(anne,29,john).
met(anne,24,mary).
met(mark,17,paul).

%%% Question 7
contact(infect(StartPerson,StartTime),infect(GoalPerson,Goaltime),ZS) :-
    contact4(infect(StartPerson,StartTime),infect(GoalPerson,Goaltime),[],ZS).

contact4(infect(StartPerson,StartTime),infect(GoalPerson,Goaltime),MetHistory,InfectionPath) :-
    StartPerson == GoalPerson,
    StartTime >= Goaltime.
contact4(infect(StartPerson,StartTime),infect(GoalPerson,Goaltime),MetHistory,InfectionPath) :-
    (met(StartPerson,MetTime,MidPerson);met(MidPerson,MetTime,StartPerson)),
    StartTime >= MetTime,
    StartTime - MetTime < 7,
    \+ (mymember(met(StartPerson,MetTime,MidPerson),MetHistory);mymember(met(MidPerson,MetTime,StartPerson),MetHistory)),
    contact4(infect(MidPerson,MetTime),infect(GoalPerson,Goaltime),[(met(StartPerson,MetTime,MidPerson)),(met(MidPerson,MetTime,StartPerson))|MetHistory],[infect(MidPerson,MetTime)|InfectionPath]).

The code that I have above correctly follows the path and I have confirmed it is correct with trace. The issue is, at the end of the trace when it reaches the goal person, it is deleting all of the entries before it returns. This can be seen clearly in the last 5 Exit calls that are made by the program. I have provided the trace below using the call.

contact(infect(john,31),infect(paul,11),ZS).

[trace]  ?- contact(infect(john,31),infect(paul,11),ZS).
   Call: (10) ex3:contact(infect(john, 31), infect(paul, 11), _28656) ? creep
   Call: (11) ex3:contact4(infect(john, 31), infect(paul, 11), [], _28656) ? creep
   Call: (12) john==paul ? creep
   Fail: (12) john==paul ? creep
   Redo: (11) ex3:contact4(infect(john, 31), infect(paul, 11), [], _28656) ? creep
   Call: (12) ex3:met(john, _32982, _32984) ? creep
   Exit: (12) ex3:met(john, 28, mary) ? creep
   Call: (12) 31>=28 ? creep
   Exit: (12) 31>=28 ? creep
   Call: (12) 31-28<7 ? creep
   Exit: (12) 31-28<7 ? creep
   Call: (12) ex3:mymember(met(john, 28, mary), []) ? creep
   Fail: (12) ex3:mymember(met(john, 28, mary), []) ? creep
   Redo: (11) ex3:contact4(infect(john, 31), infect(paul, 11), [], _28656) ? creep
   Call: (12) ex3:mymember(met(mary, 28, john), []) ? creep
   Fail: (12) ex3:mymember(met(mary, 28, john), []) ? creep
   Redo: (11) ex3:contact4(infect(john, 31), infect(paul, 11), [], _28656) ? creep
   Call: (12) ex3:contact4(infect(mary, 28), infect(paul, 11), [met(john, 28, mary), met(mary, 28, john)], [infect(mary, 28)|_28656]) ? creep
   Call: (13) mary==paul ? creep
   Fail: (13) mary==paul ? creep
   Redo: (12) ex3:contact4(infect(mary, 28), infect(paul, 11), [met(john, 28, mary), met(mary, 28, john)], [infect(mary, 28)|_28656]) ? creep
   Call: (13) ex3:met(mary, _45284, _45286) ? creep
   Exit: (13) ex3:met(mary, 23, mark) ? creep
   Call: (13) 28>=23 ? creep
   Exit: (13) 28>=23 ? creep
   Call: (13) 28-23<7 ? creep
   Exit: (13) 28-23<7 ? creep
   Call: (13) ex3:mymember(met(mary, 23, mark), [met(john, 28, mary), met(mary, 28, john)]) ? creep
   Call: (14) ex3:mymember(met(mary, 23, mark), [met(mary, 28, john)]) ? creep
   Call: (15) ex3:mymember(met(mary, 23, mark), []) ? creep
   Fail: (15) ex3:mymember(met(mary, 23, mark), []) ? creep
   Fail: (14) ex3:mymember(met(mary, 23, mark), [met(mary, 28, john)]) ? creep
   Fail: (13) ex3:mymember(met(mary, 23, mark), [met(john, 28, mary), met(mary, 28, john)]) ? creep
   Redo: (12) ex3:contact4(infect(mary, 28), infect(paul, 11), [met(john, 28, mary), met(mary, 28, john)], [infect(mary, 28)|_28656]) ? creep
   Call: (13) ex3:mymember(met(mark, 23, mary), [met(john, 28, mary), met(mary, 28, john)]) ? creep
   Call: (14) ex3:mymember(met(mark, 23, mary), [met(mary, 28, john)]) ? creep
   Call: (15) ex3:mymember(met(mark, 23, mary), []) ? creep
   Fail: (15) ex3:mymember(met(mark, 23, mary), []) ? creep
   Fail: (14) ex3:mymember(met(mark, 23, mary), [met(mary, 28, john)]) ? creep
   Fail: (13) ex3:mymember(met(mark, 23, mary), [met(john, 28, mary), met(mary, 28, john)]) ? creep
   Redo: (12) ex3:contact4(infect(mary, 28), infect(paul, 11), [met(john, 28, mary), met(mary, 28, john)], [infect(mary, 28)|_28656]) ? creep
   Call: (13) ex3:contact4(infect(mark, 23), infect(paul, 11), [met(mary, 23, mark), met(mark, 23, mary), met(john, 28, mary), met(mary, 28, john)], [infect(mark, 23), infect(mary, 28)|_28656]) ? creep
   Call: (14) mark==paul ? creep
   Fail: (14) mark==paul ? creep
   Redo: (13) ex3:contact4(infect(mark, 23), infect(paul, 11), [met(mary, 23, mark), met(mark, 23, mary), met(john, 28, mary), met(mary, 28, john)], [infect(mark, 23), infect(mary, 28)|_28656]) ? creep
   Call: (14) ex3:met(mark, _63714, _63716) ? creep
   Exit: (14) ex3:met(mark, 17, paul) ? creep
   Call: (14) 23>=17 ? creep
   Exit: (14) 23>=17 ? creep
   Call: (14) 23-17<7 ? creep
   Exit: (14) 23-17<7 ? creep
   Call: (14) ex3:mymember(met(mark, 17, paul), [met(mary, 23, mark), met(mark, 23, mary), met(john, 28, mary), met(mary, 28, john)]) ? creep
   Call: (15) ex3:mymember(met(mark, 17, paul), [met(mark, 23, mary), met(john, 28, mary), met(mary, 28, john)]) ? creep
   Call: (16) ex3:mymember(met(mark, 17, paul), [met(john, 28, mary), met(mary, 28, john)]) ? creep
   Call: (17) ex3:mymember(met(mark, 17, paul), [met(mary, 28, john)]) ? creep
   Call: (18) ex3:mymember(met(mark, 17, paul), []) ? creep
   Fail: (18) ex3:mymember(met(mark, 17, paul), []) ? creep
   Fail: (17) ex3:mymember(met(mark, 17, paul), [met(mary, 28, john)]) ? creep
   Fail: (16) ex3:mymember(met(mark, 17, paul), [met(john, 28, mary), met(mary, 28, john)]) ? creep
   Fail: (15) ex3:mymember(met(mark, 17, paul), [met(mark, 23, mary), met(john, 28, mary), met(mary, 28, john)]) ? creep
   Fail: (14) ex3:mymember(met(mark, 17, paul), [met(mary, 23, mark), met(mark, 23, mary), met(john, 28, mary), met(mary, 28, john)]) ? creep
   Redo: (13) ex3:contact4(infect(mark, 23), infect(paul, 11), [met(mary, 23, mark), met(mark, 23, mary), met(john, 28, mary), met(mary, 28, john)], [infect(mark, 23), infect(mary, 28)|_18]) ? creep
   Call: (14) ex3:mymember(met(paul, 17, mark), [met(mary, 23, mark), met(mark, 23, mary), met(john, 28, mary), met(mary, 28, john)]) ? creep
   Call: (15) ex3:mymember(met(paul, 17, mark), [met(mark, 23, mary), met(john, 28, mary), met(mary, 28, john)]) ? creep
   Call: (16) ex3:mymember(met(paul, 17, mark), [met(john, 28, mary), met(mary, 28, john)]) ? creep
   Call: (17) ex3:mymember(met(paul, 17, mark), [met(mary, 28, john)]) ? creep
   Call: (18) ex3:mymember(met(paul, 17, mark), []) ? creep
   Fail: (18) ex3:mymember(met(paul, 17, mark), []) ? creep
   Fail: (17) ex3:mymember(met(paul, 17, mark), [met(mary, 28, john)]) ? creep
   Fail: (16) ex3:mymember(met(paul, 17, mark), [met(john, 28, mary), met(mary, 28, john)]) ? creep
   Fail: (15) ex3:mymember(met(paul, 17, mark), [met(mark, 23, mary), met(john, 28, mary), met(mary, 28, john)]) ? creep
   Fail: (14) ex3:mymember(met(paul, 17, mark), [met(mary, 23, mark), met(mark, 23, mary), met(john, 28, mary), met(mary, 28, john)]) ? creep
   Redo: (13) ex3:contact4(infect(mark, 23), infect(paul, 11), [met(mary, 23, mark), met(mark, 23, mary), met(john, 28, mary), met(mary, 28, john)], [infect(mark, 23), infect(mary, 28)|_18]) ? creep
   Call: (14) ex3:contact4(infect(paul, 17), infect(paul, 11), [met(mark, 17, paul), met(paul, 17, mark), met(mary, 23, mark), met(mark, 23, mary), met(john, 28, mary), met(mary, 28, john)], [infect(paul, 17), infect(mark, 23), infect(mary, 28)|_18]) ? creep
   Call: (15) paul==paul ? creep
   Exit: (15) paul==paul ? creep
   Call: (15) 17>=11 ? creep
   Exit: (15) 17>=11 ? creep
   Exit: (14) ex3:contact4(infect(paul, 17), infect(paul, 11), [met(mark, 17, paul), met(paul, 17, mark), met(mary, 23, mark), met(mark, 23, mary), met(john, 28, mary), met(mary, 28, john)], [infect(paul, 17), infect(mark, 23), infect(mary, 28)|_18]) ? creep
   Exit: (13) ex3:contact4(infect(mark, 23), infect(paul, 11), [met(mary, 23, mark), met(mark, 23, mary), met(john, 28, mary), met(mary, 28, john)], [infect(mark, 23), infect(mary, 28)|_18]) ? creep
   Exit: (12) ex3:contact4(infect(mary, 28), infect(paul, 11), [met(john, 28, mary), met(mary, 28, john)], [infect(mary, 28)|_18]) ? creep
   Exit: (11) ex3:contact4(infect(john, 31), infect(paul, 11), [], _18) ? creep
   Exit: (10) ex3:contact(infect(john, 31), infect(paul, 11), _18) ? creep
true .

[trace]  ?-

I have also checked out the related questions but could not find a solution. here and here

Post your actual code please. What you posted cannot be your actual code since `met(anne,24,mary)).` will not be accepted by a Prolog. When I fix this, your query fails, and the trace is very different from what you posted. Include your definition of `mymember` as well. — Isabelle Newbie, Nov 30 '21 at 20:06
Also, you should **never** ignore "singleton variable" warnings from Prolog. These warnings usually indicate **actual errors** in your code. What's the relationship between `MetHistory` and `InfectionPath` in the first clause of `contact4`? — Isabelle Newbie, Nov 30 '21 at 20:08
That was a copy paste error on the met(anne,24,mary), sorry about that. I have also updated it to include the predicate for my-member. I'll work this afternoon at eliminating all of the singleton variable errors as well, thank you for the heads up! — Sean-McCreary, Nov 30 '21 at 20:32

score 2 · Accepted Answer · answered Nov 30 '21 at 20:46

Thanks for the updates, I can now run your program.

What you are trying to do is to compute an infection path from a Start to a Goal person. You are doing this correctly by looking for a connection from a Start to a Mid person, and then from Mid to Goal. The detail you're missing is that the Start to Goal path is longer than the Mid to Goal path.

Therefore your code cannot be of this shape:

path(Start, Goal, Path) :-
    step(Start, Mid),
    path(Mid, Goal, [Step | Path]).

This would say that the Mid to Goal path is one element longer than the Start to Goal path! That's the wrong way round.

What you need instead is something of this shape:

path(Start, Goal, [Step | Path]) :-
    step(Start, Mid),
    path(Mid, Goal, Path).

This says: There is some Path from Mid to Goal. The path from Start to Goal is the same Path extended with one Step.

So you want something like this:

contact4(infect(StartPerson,StartTime),infect(GoalPerson,Goaltime),_MetHistory,InfectionPath) :-
    StartPerson == GoalPerson,
    StartTime >= Goaltime,
    InfectionPath = [].
contact4(infect(StartPerson,StartTime),infect(GoalPerson,Goaltime),MetHistory,[infect(MidPerson,MetTime)|InfectionPath]) :-
    (met(StartPerson,MetTime,MidPerson);met(MidPerson,MetTime,StartPerson)),
    StartTime >= MetTime,
    StartTime - MetTime < 7,
    \+ (mymember(met(StartPerson,MetTime,MidPerson),MetHistory);mymember(met(MidPerson,MetTime,StartPerson),MetHistory)),
    contact4(infect(MidPerson,MetTime),infect(GoalPerson,Goaltime),[(met(StartPerson,MetTime,MidPerson)),(met(MidPerson,MetTime,StartPerson))|MetHistory],InfectionPath).

(BTW, your code is very hard to read if you don't use any spaces. It's a good idea to add a space after each , and around each ; and | and other operators.)

This behaves like this:

?- contact(infect(john,31),infect(paul,11),ZS).
ZS = [infect(mary, 28), infect(mark, 23), infect(paul, 17)] ;
ZS = [infect(anne, 29), infect(mary, 24), infect(mark, 23), infect(paul, 17)] ;
false.

Ahhh gotcha! ok I see where I had gone astray there. Thank you for taking the time to message back so comprehensively! I've gone through and added more whitespace as well and am getting rid of the singleton warnings from the rest of my code :) — Sean-McCreary, Dec 01 '21 at 01:47

How can I prevent prolog from backtracking and deleting my list?

1 Answers1