Prolog - How to count the number of elements in a list that satisfy a specific condition?

Question

for example, if I have a list [1,1,2,3,5,1], I want to count the number of 1's in this list, how would I do that?

I wrote something like:

count([], 0).
count([H|T], N) :-
   count(T, X),
   (  H =:= 1
   -> N is X+1
   ;  N is X
   ),
   N > 0.

In this recursion, I want to do if Head equals 1, then the counting + 1, if Head is not 1, then counting stays the same. However, it returns false if I have things that are not 1 in the list. I know the problem is that it'd fail as soon as an element does not satisfy the if statement; and it can never reach the else statement. How do I fix this? Please help!!!!

Answer 1

Since you've already opted to use (;)/2 - if-then-else, you might find the following variant with if_/3 interesting:

list_1s(L,X) :-
   length(L,Len),
   list_1s_(L,X,0,Len).

list_1s_([],X,X,0).
list_1s_([Y|Ys],X,Acc0,Len1) :-
   if_(Y=1, Acc1 is Acc0+1, Acc1 is Acc0),
   Len0 is Len1-1,
   list_1s_(Ys,X,Acc1,Len0).

The goal length/2 in the calling predicate list_1s/2 together with the 4th argument of the actual relation list_1s_/4 is used to make sure the result lists are listed in a fair manner if the predicate is called with the first argument being variable. The 3rd argument of list_1s_/4 is an accumulator that's used to count the number of 1s up from zero, in order to make the predicate tail recursive. Consequently the 2nd and 3rd arguments of list_1s_/4 are equal if the list is empty. Now let's see some example queries. In the list to number direction the predicate yields the desired results and succeeds deterministically (it doesn't leave unnecessary choice points open, no need to press ; after the single answer) in doing so:

?- list_1s([],X).
X = 0.

?- list_1s([1,2,3],X).
X = 1.

?- list_1s([1,2,3,1],X).
X = 2.

?- list_1s([0,2,3,0],X).
X = 0.

In the number to list direction there are infinitely many lists for any given number and, as mentioned above, they are listed in a fair manner, that is, all possibilities of lists of length n are listed before moving on to length n+1:

?- list_1s(L,0).
L = [] ;                            % <- empty list
L = [_G386],                        % <- length 1
dif(_G386, 1) ;
L = [_G442, _G445],                 % <- length 2
dif(_G442, 1),
dif(_G445, 1) ;
L = [_G498, _G501, _G504],          % <- length 3
dif(_G498, 1),
dif(_G501, 1),
dif(_G504, 1) ;
.
.
.

?- list_1s(L,1).
L = [1] ;                           % <- length 1
L = [1, _G404],                     % <- length 2
dif(_G404, 1) ;
L = [_G401, 1],                     % <- length 2
dif(_G401, 1) ;
L = [1, _G460, _G463],              % <- length 3
dif(_G460, 1),
dif(_G463, 1) ;
L = [_G457, 1, _G463],              % <- length 3
dif(_G457, 1),
dif(_G463, 1) ;
L = [_G457, _G460, 1],              % <- length 3
dif(_G457, 1),
dif(_G460, 1) ;
.
.
.

And the most general query is listing the results in a fair manner as well:

?- list_1s(L,X).
L = [],                             % <- empty list
X = 0 ;
L = [1],                            % <- length 1
X = 1 ;
L = [_G413],                        % <- length 1
X = 0,
dif(_G413, 1) ;
L = [1, 1],                         % <- length 2
X = 2 ;
L = [1, _G431],                     % <- length 2
X = 1,
dif(_G431, 1) ;
L = [_G428, 1],                     % <- length 2
X = 1,
dif(_G428, 1) ;
.
.
.

Answer 2

Let’s start with your code and ask some queries!

I added comments on the side showing the result I would have expected...

?- count([0,2,3,0], Count).
false                                 % bad: expected Count = 0
?- count([1,2,3,1], Count).
Count = 2                             % ok
?- count([1,2,3], Count).
false                                 % bad: expected Count = 1

If my expectation matches yours, the minimal fix for your code is tiny: just remove the goal N > 0!

count([], 0).
count([H|T], N) :-
   count(T, X),
   (  H =:= 1
   -> N is X+1
   ;  N is X
   ).

Let’s run above queries again:

?- count([0,2,3,0], Count).
Count = 0                             % was “false”, now ok
?- count([1,2,3,1], Count).
Count = 2                             % was ok, still is ok
?- count([1,2,3], Count).
Count = 1.                            % was “false”, now ok

The bottom line: your original code failed whenever the last list item was not equal to 1.

Answer 3

Alternative solution, which uses foldl/4 and defines higher order predicate (the one which takes another predicate as a parameter):

count_step(Condition, Item, CurrentCount, NewCount) :-
    call(Condition, Item) ->
        NewCount is CurrentCount + 1 ;
        NewCount = CurrentCount.

count(List, Condition, Count) :-
    foldl(count_step(Condition), List, 0, Count).

is_one(Expr) :-
    Expr =:= 1.

Usage example:

?- count([0, 2, 3, 0], is_one, Count).
Count = 0.

?- count([1, 2, 3, 1], is_one, Count).
Count = 2.

Another (rather dirty) approach is to use include/3 combined with length/2:

count(List, Condition, Count) :-
    include(Condition, List, Filtered),
    length(Filtered, Count).

Answer 4

Try this:

count([],0).
count([1|T],N) :- count(T,N1), N is N1 + 1.
count([X|T],N) :- X \= 1, count(T,N).