CODEWITHSUNDEEP
lambdaprologlogic
rex
rex

Reputation: 339

counting the number of a particular element in a prolog list

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?

Upvotes: 4

Views: 15057

Answers (3)

Will Ness
Will Ness

Reputation: 71075

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.

Upvotes: 2

joel76
joel76

Reputation: 5675

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).

Upvotes: 1

Haile
Haile

Reputation: 3180

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 */

Upvotes: 4

Related Questions