counting the number of a particular element in a prolog list

Question

I am trying to count how many times a element appears in a list, so far I have came up with

rate(X,[H|T],N):-
  X == H,
  N is N+1,
  rate(X,T,N).
rate(X,[_|T],N) :-
  rate(X,T,N).  
rate(_,[],N) :-
  N is 0.

I've covered when the a match is found, when there isn't a match and when it reaches the end of the list. But when i test i get

43 ?- rate(4,[4,2,3,4,4,2],X).
ERROR: is/2: Arguments are not sufficiently instantiated
Exception: (6) frequency(4, [4, 2, 3, 4, 4, 2], _G393) ?     

What arguments am i missing exactly?

Solution 1

You can use is/2 (like in N is X) if and only if X is a number. You can't use is/2 if X is a free variable. In your first clause you have: N is N+1. This is bad, since N is a free variable (it has not a value at this point, and so is for N+1).

There's another error. In:

rate(X,[_|T],N) :-
  rate(X,T,N).

since you use this ONLY when X is not the first element in the list, you should check for this to be true! Here's the code:

count(_, [], 0) :- !. /* empty list, base case */

count(X, [X|T], N) :- /* if X is in the head of the list */
    count(X, T, N2), /* count on the tail (let this N2) */
    N is N2 + 1.     /* and N is N2 + 1  */

count(X, [Y|T], N) :- 
    X \= Y,          /* if X is not in the head */
    count(X, T, N).  /* just count the rest */

Solution 2

You need to make your clauses mutually exclusive, the second clause will succeed wherever the first will.

As to your error, it is about the flow of information. You need to exchange the lines in your first clause like so:

rate(X,[H|T],N):-
  X == H,
  rate(X,T,N1),
  N is N1+1.

This change will make your predicate to be not tail recursive though. To be tail recursive, it needs to pass information down the call chain, not to receive it back on the way up like it does now:

rate(X,[H|T],N):-
  X == H,
  N1 is N+1,
  rate(X,T,N1).

Now you see that you don't receive the final value here, but specify the initial value. When we reach the base case we have our result:

rate(X, [], N).

here N is the result. How to get it back? Use additional argument, an uninstantiated variable, to be unified with this result when we've reached the bottom:

rate(X, [], N, V) :- V is N.

Now the recursive clause must accommodate for this variable, passing it along unchanged down the call chain.

Solution 3

If you like functional style, you can write that with SWI Prolog :

:- use_module(library(lambda)).


rate(X,L,N) :-
    foldl(\Y^V0^V1^((X = Y->V1 is V0+1; V1 = V0)), L, 0, N).

Comments

[rex]

I understand now, thanks alot for the explaination on handling free variables!

[Will Ness]

you have the power to upvote now, in case you didn't know that. Any answer that you think is good, you can upvote. :)

[Will Ness]

@rex btw N is N+1 is bad, but not because N is a "free variable" (more commonly known as uninstantiated variable). I mean, even if N were instantiated first, N is N+1 would still be bad.

[Ash]

You don't need the step X \= Y. Just put a cut in the previous predicate, which is when they do equal.