Cuts in recursion of Prolog

1
votes

I am learning Prolog myself and recently came across a piece of notes:-

Example: nth/3

  • for example, to find the nth element of a list we could use 
    nth([X|_],0,X). 

    nth([_|L],N,X) :- N1 is N - 1, nth(L,N1,X).

  • the 0th element of a list is the head of the list (first clause), otherwise we take the n-1th element of the tail of the list (second clause).

  • once we have found the nth element, we can’t find any more by backtracking.

 nth([X|_],0,X). 
 nth([_|L],N,X) :- N1 is N - 1, !, nth(L,N1,X).
  • adding a cut makes this clear and may be necessary for tail recursion optimisation.

However, when I use the trace function in Prolog, I found out that the calling sequences of these 2 pieces of codes are exactly the same.

Should I put the ! mark as follows instead?

 nth([X|_],0,X) :- !. 
 nth([_|L],N,X) :- N1 is N - 1, nth(L,N1,X).
1
prolog

1 Answers

2
votes

The cut in the second clause is redundant as there are no more clauses and the goal before it (the is/2 call) is deterministic. I also don't think that the cut plays any role on tail recursion optimization (which basically requires that you recursive call be the last goal in the clause body).

However, before worrying about cut placement, you should check what happens if you call the nth/3 predicate in a mode other than nth(+,+,-). For example, what happens in mode nth(+,+,+), i.e. when you call the predicate with all arguments instantiated, but the element is not in the list? Hint: moving the cut to the first clause will not solve the problem.