Recursion in· Prolog

Question

I am trying to understand recursion in Prolog, but it is certainly different than how it is in other languages like PHP, Java and C. I have been reading all the tutorials about it, but I still don't get specific, rather complicated cases.

For instance, in order to get the number of occurrences of an element in a list we have:

occurrence([], _, 0).
occurrence([H | T], H, N) :- !, occurrence(T, H, N1), N is N1 + 1.
occurrence([_ | T], H, N) :- occurrence(T, H, N).

which can be called using:

occurrence([1,4,9,1,2],1,R).

and it should result:

?- R=2

Why is line 3 even happening? What is it doing? I wrote this program without looking at the answer and I was done after the 2nd line. Of course it wasn't working though.

On the other hand, why is the "cut" occurring in there? I have been trying to print out the result after every call and I just get more and more confused.

Daniel Lyons Daniel Lyons · Accepted Answer · 2014-04-29T21:16:31

Line 3 handles the case where the head of the list doesn't match the item you're looking for. Suppose you've passed the first element, you wind up in the recursive call to occurrence/3 which looks like:

occurrence([4,9,1,2], 1, 1).

Which rule matches? Rule 1 doesn't match because we don't have the empty list. Rule 2 doesn't match because 4 \= 1. The third rule is for this case, and it just says, you didn't find a 1 here, so keep looking with the tail of the list ([9,1,2]).

The cut is there because the third rule will match any list. The cut commits you to the choice. What choice? That you have the same value in the head of the list and as the element you're seeking, because that's the pattern that must be matched to enter the body of this rule. If you omit the cut, you're permitting a choice point after unifying the head of the list with the element being sought, which means you'll get more than one solution with unifications for R = 2, then R = 1, then R = 0. This is because each 1 could also just be ignored as in the third rule.

You can get rid of the cut by making the third rule conditional:

occurrence([H1|T], H2, N) :- H1 \= H2, occurrence(T, H2, N).

You could also use a conditional expression and have one rule combine rules 2 and 3:

occurrence([H|T], S, N) :- 
  (H = S 
     -> occurrence(T, S, N1), N is N1 + 1 
      ; occurrence(T, S, N)
  ).

This is likely to be somewhat more efficient; the conditional expression doesn't create choice points the way additional rule bodies do. Prolog isn't psychic, so it can't detect that rules are mutually exclusive. I would prefer the logical formulation with multiple rules for readability though.

Hope this helps.

Recursion in· Prolog

1 Answers