1

I read Learn Prolog Now website and I try to do the following exercise:

6.5 Write a predicate swapfl(List1,List2) which checks whether List1 is identical to List2 , except that the first and last elements are exchanged. Here’s where append/3 could come in useful again, but it is also possible to write a recursive definition without appealing to append/3 (or any other) predicates.

I've written it and it works correctly, but it tries to find more than one solution.

swapfl([HL1|TL1],[HL2|TL2]):-
   swpfl(TL1,TL2,HL2,HL1).

swpfl([HL1|TL1],[HL2|TL2],AccEL1,AccEL2):-
   swpfl(TL1,TL2,AccEL1,AccEL2),
   HL1=HL2.
swpfl([H1],[H2],H1,H2).

I look at the code and the trace

[trace] [5]  ?- swapfl([1,2,3],[3,2,1]).
   Call: (51) swapfl([1, 2, 3], [3, 2, 1]) ? creep
   Call: (52) swpfl([2, 3], [2, 1], 3, 1) ? creep
   Call: (53) swpfl([3], [1], 3, 1) ? creep
   Exit: (53) swpfl([3], [1], 3, 1) ? creep
   Call: (53) 2=2 ? creep
   Exit: (53) 2=2 ? creep
   Exit: (52) swpfl([2, 3], [2, 1], 3, 1) ? creep
   Exit: (51) swapfl([1, 2, 3], [3, 2, 1]) ? creep
true ;
   Redo: (52) swpfl([2, 3], [2, 1], 3, 1) ? creep
   Fail: (52) swpfl([2, 3], [2, 1], 3, 1) ? creep
   Fail: (51) swapfl([1, 2, 3], [3, 2, 1]) ? creep
false.

and I cannot understand why prolog thinks that it may be worth to start Redo part.

Could someone explain why there is an unsearched branch of the solution tree?

false
  • 10,264
  • 13
  • 101
  • 209
SekstusEmpiryk
  • 143
  • 6
  • 1
    This is only an efficiency issue. Prolog cannot determine at once that `swpfl([2,3],...` does not fit the second clause which is for one-element lists only. So it needs to try the second clause and then fails. – false Oct 26 '19 at 14:45
  • Historical obsession with efficiency and elimination of choice points is the bane of logic programming – Kintalken Nov 12 '19 at 17:59

1 Answers1

1

Prolog will always explore all options, before making it's final decision.

Try looking at the following stack overflow question: Prolog: stop condition?

The false response can appear inconsistent to beginning Prolog programmers and "feel" like an error or warning, but it's actually a perfectly normal Prolog response. Prolog is quite consistent in its behavior of attempting to find solutions and, when no more choices exist, will return false. If Prolog has exhausted all the other choices before it finds the final solution, it displays the solution and doesn't return false.

Simon
  • 58
  • 5