Error counting occurrences in a list in Prolog

Question

I trying to develop a small program in Prolog. Currently, I'm starting with Prolog and therefore there are issues that I do not understand well.

My program pretend to count the number of occurrences of an element in a list. In the end, it must to show next message: "Element X occurrs N times."

The code is as given below:

count_occur(X, [], N) :- format("Element ~d occurrs ~d times. ~n", [X,N]).
count_occur(X, [X|T], N) :- 
    count_occur(X, T, N2), 
    N is N2 + 1.    
count_occur(X, [Y|T], N) :- 
    X \= Y,          
    count_occur(X, T, N).

Consulting with an example I always get following error:

?- count_occur(5,[2, 5, 5, 5, 6, 6, 8, 9, 9, 9], 0).
Element 5 ocurrs 
ERROR: Arguments are not sufficiently instantiated
ERROR: In:
ERROR:   [19] format("Element ~d ocurrs ~d times. ~n",[5,_8398])
ERROR:   [18] count_occur(5,[],_8428) at /Users/serrodcal/Repositories/PLExercises1/ex1.pl:1
ERROR:   [11] count_occur(5,[5,6|...],_8456) at /Users/serrodcal/Repositories/PLExercises1/ex1.pl:3
ERROR:   [10] count_occur(5,[5,5|...],_8496) at /Users/serrodcal/Repositories/PLExercises1/ex1.pl:3
ERROR:    [9] count_occur(5,[5,5|...],0) at /Users/serrodcal/Repositories/PLExercises1/ex1.pl:3
ERROR:    [7] <user>
ERROR: 
ERROR: Note: some frames are missing due to last-call optimization.
ERROR: Re-run your program in debug mode (:- debug.) to get more detail.

I am using third params like counter but in the case base Prolog does not know the value of N.

score 3 · Accepted Answer · answered May 24 '17 at 21:10

If you insist on having that message printed, I would suggest to at least separate the output from the predicate describing the actual relation. Consider something along this pattern:

calling_predicate(...) :-
   other_predicate(...),   % <- predicate describing the actual relation
   format(...).            % <- output

You could, for instance, substitute count_occur/3 for calling_predicate and count_occur_/3 from @User9213's post for other_predicate. Alternatively you could opt for using CLP(FD) as suggested by @mat. Consider for example the following version using if_/3:

:- use_module(library(clpfd)).

count_occur(X, L, N) :-
   list_x_count_(L,X,N,0),                             % <- actual relation
   format("Element ~w occurs ~d times. ~n", [X,N]).    % <- output

list_x_count_([],_X,N,N).
list_x_count_([Y|Ys],X,N,N0) :-
   if_(Y=X,(N0 #< N, N1 #= N0+1), N1 #= N0),
   list_x_count_(Ys,X,N,N1).

Since the elements in the list are not necessarily numbers, it is opportune to use the escape sequence ~w for the argument X instead of ~d (see the documentation of format/2 for more detail). If you query that with your given example, you get the desired result:

?- count_occur(5,[2,5,5,5,6,6,8,9,9,9], N).
Element 5 occurs 3 times. 
N = 3.

Note that this query succeeds deterministically. That is, there are no superfluous choicepoints left, hence you don't need to enter ; after Prolog tells you the only answer. The example queries provided by @mat and @lambda.xy.x in the comments work as well:

?- count_occur(1,[2,X],0).
Element 1 occurs 0 times. 
dif(X, 1).

?- count_occur(a, [a,b,c], N).
Element a occurs 1 times. 
N = 1.

?- count_occur(X, [a,b,c], N).
Element a occurs 1 times. 
X = a,
N = 1 ;
Element b occurs 1 times. 
X = b,
N = 1 ;
Element c occurs 1 times. 
X = c,
N = 1 ;
Element _G210 occurs 0 times. 
N = 0,
dif(X, c),
dif(X, b),
dif(X, a).

I am going to try that. I am working on other alternative, writing auxiliary predicate with 2 parameters. As I mentioned I am starting in prolog. Thanks for your help, I appreciate it a lot. — Sergio Rodríguez Calvo, May 25 '17 at 06:24

score 2 · Answer 2 · answered May 23 '17 at 09:48

2

I don't know how it can work like you have written it. Maybe write it like that:

count_occur(X, L, N) :- count_occur_(L, X, N).

count_occur_([], _, 0). % the 0 here is important (why?)
count_occur_([X|Xs], X, N) :-
    count_occur_(Xs, X, N0),
    succ(N0, N).
count_occur_([Y|Ys], X, N) :-
    dif(Y, X),
    count_occur_(Ys, X, N).

answered May 23 '17 at 09:48

I will try your solution. In my solution, we get the message that I want, but the queries must have 0 in third param (count). – Sergio Rodríguez Calvo May 23 '17 at 11:48

score -1 · Answer 3 · answered May 22 '17 at 09:50

-1

I found the error. The solution is:

count_occur(X, [], N) :- format("Element ~d occurrs ~d times. ~n", [X,N]).
count_occur(X, [X|T], N) :- 
    N2 is N + 1,
    count_occur(X, T, N2).    
count_occur(X, [Y|T], N) :- 
    X \= Y,          
    count_occur(X, T, N).

Second count_occur statement was wrong and it was not incrementing adequately.

answered May 22 '17 at 09:50

Sergio Rodríguez Calvo

1,183
2
16
32

3

That's still not a solution. Try for example: `?- count_occur(X, [a,b,c], N).` or even `?- count_occur(a, [a,b,c], N).` Ideally, we can use a relation in *multiple* directions, not just in very specific special cases. You can achieve this generality for example by using `dif/2` and the CLP(FD) constraint `(#=)/2` instead of `(is)/2`. – mat May 22 '17 at 09:53
My purpose is to show `Element 5 occurrs 3 times.`and I got this message with this code. But, you are right and I'll try that. Thanks. – Sergio Rodríguez Calvo May 22 '17 at 09:59
2

You might also want to look into the (incomplete) results of the queries ```count_occur(1,[2,X],0).``` and ```length(Xs,_), count_occur(1,[1|Xs],0).```. – lambda.xy.x May 22 '17 at 14:17

Error counting occurrences in a list in Prolog

3 Answers3