Geek Answers Handbook

Counting the number of a specific item in the prolog list

I try to count how many times an item appears in the list, so far I 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 examined when a match is found, when there is no 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 for sure?

+4
source share
3 answers

You can use is/2 (for example, in N is X ) if and only if X is a number. You cannot use is/2 if X is a free variable. In the first paragraph, you have: N is N+1 . This is bad, since N is a free variable (it does not matter at this point, as well as for N + 1).

There is another mistake. IN:

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

since you use it ONLY when X is not the first item in the list, you should check that this is true! Here is 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 */
+4
source

You need to make your proposals mutually exclusive; the second sentence will be executed wherever the first one is.

As for your mistake, we are talking about the flow of information. You need to exchange the lines in the first sentence like this:

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

This change will make your predicate non-recursive. To be recursive, it must transmit information through the call chain, and not receive it back on the way up, as it is now:

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

Now you see that here you have not received the final value, but indicate the initial value. When we reach the base case, we get our result:

 rate(X, [], N).

here N is the result. How to return it? Use an additional argument, an indispensable variable that will be combined with this result when we reach the bottom:

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

Now the recursive clause should match this variable, passing it unchanged along the call chain.

+2
source

If you like the functional style, you can write this using 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).
+1
source

More articles:


All Articles