Prolog - Check number of occurences doesn't work as expected

Question

In Prolog: I have the following function that counts the occurences of a certain element in a list:

%count(L:list,E:int,N:int) (i,i,o)
count([],_,0).
count([H|T],E,C):-H == E,count(T,E,C1),C is C1+1.
count([_|T],E,C):-count(T,E,C).

I tested it and it works well. But here comes the problem, I have another function that has to check if "1" occurs less than 2 times in a list.

check(L):-count(L,1,C),C<2.

Whenever I try to check the list [1,1,1,1] for example, the result I get is "true", which is wrong, and I have no idea why. I tried to make some changes, but the function just won't work.

Look at the following answer http://stackoverflow.com/a/28971616/4609915 to the *very* related question here on SO http://stackoverflow.com/q/28951199/4609915 ! — repeat, Nov 20 '15 at 18:30

score 3 · Answer 1 · edited May 23 '17 at 12:16

Improve your testing habits!

When testing Prolog code don't only look at the first answer to some query and conclude "it works".

Non-determinism is central to Prolog.

Quite often, some code appears to be working correctly at first sight (when looking at the first answer) but exhibits problems (mainly wrong answers and/or non-termination) upon backtracking.

Coming back to your original question... If you want / need to preserve logical-purity, consider using the following minimal variation of the code @Ruben presented in his answer:

count([],_,0).
count([E|T],E,C) :-
   count(T,E,C1),
   C is C1+1.
count([H|T],E,C) :- 
   dif(H,E),
   count(T,E,C).

dif/2 expresses syntactic term inequality in a logical sound way. For info on it look at prolog-dif!

score 1 · Accepted Answer · answered Nov 19 '15 at 13:15

1

It happens because count([1,1,1,1],1,1) is also true! In your last count it can also be matched when H does equal E. To illustrate this, use ; to make prolog look for more answers to count([1,1,1,1],1,R). You'll see what happens.

count([],_,0).
count([E|T],E,C):-
    count(T,E,C1),
    C is C1+1.
count([H|T],E,C):-
    H \= E,
    count(T,E,C).

check(L) :- 
    count(L,1,C),
    C < 2.

?- check([1,1,1,1,1]).
false
?- check([1]).
true

answered Nov 19 '15 at 13:15

Noxeus

567
4
17

beware the semantic is different, maybe unintentionally, OP' original test cannot be replaced by unification – CapelliC Nov 19 '15 at 13:22
Thank you so much, I just figured out I forgot to insert "the cut" in the second clause, but due to your answer I saw what went wrong, and both versions work as well. – Marina Popa Nov 19 '15 at 13:23

score 0 · Answer 3 · answered Nov 19 '15 at 13:19

0

second and third clauses heads match both the same sequence. As a minimal correction, I would commit the test

count([],_,0).
count([H|T],E,C):-H == E,!,count(T,E,C1),C is C1+1.
count([_|T],E,C):-count(T,E,C).

answered Nov 19 '15 at 13:19

CapelliC

59,646
5
47
90

Prolog - Check number of occurences doesn't work as expected

3 Answers3