Count numbers in list

Question

I have a problem with calculating the occurences of the given number in list. For instance, if we have a list like L = [4,5,6,4,3,4,2,4,5,6,7,4] and I want to count how many 4s is in the list, then the answer is 5.

I tried to implement this in prolog, but gprolog shows me only no as an answer:

count_occ([], 0).
count_occ([H|T], L) :- count_occ(T, N), H =:= 4, L is N + 1.

And I do not know why.

@Alexander: I changed the second line to `count_oss([H|T], L) :- count_occ(T,N), (H =:= 4, L is N + 1), (H =\= 4, L is N + 0).` and no successs. — mirx, Jan 16 '17 at 18:46
That implies that H is both equal to 4, **and** not equal to 4, which is clearly a contradiction. I think you'll need to have 3 predicates. The base predicate, one for when H is 4, and one for when H is not 4 — Alexander, Jan 16 '17 at 18:47
Separate predicate clause for different case, as Alexander described. Note that `,` is an AND operator. So, alternatively, you could consider `;` (OR) or use `->` in conjunction with `;`. These are described in the Prolog documentation. — lurker, Jan 16 '17 at 18:53
This has already been asked and answered more than once, see [this answer](http://stackoverflow.com/a/34738970/1812457) and [this older answer](http://stackoverflow.com/a/9088528/1812457) — , Jan 17 '17 at 07:13

score 3 · Answer 1 · edited Jan 16 '17 at 19:20

3

I took a stab at this. I made it extra verbose so it's easy to follow along:

% count_occurences(+List, +DesiredElement, -NumOccurences)

count_occurences([], _, 0).

count_occurences([H|T], DesiredElement, NumOccurences) :-
    H =\= DesiredElement,
    count_occurences(T, DesiredElement, NumOccurences).

count_occurences([H|T], DesiredElement, NumOccurences) :-
    H =:= DesiredElement,
    count_occurences(T, DesiredElement, N),
    NumOccurences is N + 1.

Using a conditional expression, the last 2 predicates can be combined into one:

% count_occurences(+List, +DesiredElement, -NumOccurences)

count_occurences([], _, 0).

count_occurences([H|T], DesiredElement, NumOccurences) :-
    count_occurences(T, DesiredElement, N),
    (H =:= DesiredElement ->       /* if H is DesiredElement */
        NumOccurences is  N + 1;   /* "then" */
        NumOccurences is  N        /* "else" */
    ).

edited Jan 16 '17 at 19:20

lurker

56,987
9
69
103

answered Jan 16 '17 at 18:59

Alexander

59,041
12
98
151

Your first predicate clause can be simply, `count_occurences([], 0, _).` – lurker Jan 16 '17 at 19:00
@lurker: I think that Alexander aims to be as explicitly as possible such that the OP can follow the program even if he does not know about unifying in the head. – Willem Van Onsem Jan 16 '17 at 19:01
@lurker I purposely put in variable names so as to document what each of the parameters is. – Alexander Jan 16 '17 at 19:01
I think that's reasonable. You might want to state it since it's not desirable programming practice, although it's instructional. I also see a lot of beginners use `NumOccurences is N` and, although in this case you really are evaluating a trivial expression, it gets attempted use instead of unification. – lurker Jan 16 '17 at 19:02
@lurker I find one of the largest hurdles to learning prolog is the unnecessarily minified code. It's always `X`, `X1`, `X2`, `Y`, and never anything meaningful or easy to follow long. I'd rather write a few more words than spend several sentences in writing english docs. – Alexander Jan 16 '17 at 19:04
@Alexander perhaps. In this case, the OP seems to understand head unification already, as they have it in their attempted code. In this case, it is actually more efficient and standard convention. So I don't consider it "unnecessarily minified". I do agree with the long variable names. :) – lurker Jan 16 '17 at 19:06
@lurker Knowing about head unification won't help you determine what the second and third argument are :), especially in higher rarity predicates – Alexander Jan 16 '17 at 19:09
1

To be more complete showing what's going on with arguments, a common convention is to use a comment for that: `% count_occurences(InputList, NumOccurences, DesiredElement)` with suitable `+` and `-` inserted to show inputs/outputs, etc. – lurker Jan 16 '17 at 19:15
@lurker Could you please edit my answer in line with that convention? – Alexander Jan 16 '17 at 19:16
This is not going to count numbers, this is going to count arithmetic expressions that evaluate to the same number. Try these at the toplevel: `4 =:= 4`, `4 =:= 2+2`, `5-1 =:= 2^2`. – Jan 16 '17 at 19:46
@Boris those are the kinds of quirks of prolog I always forget. What's the correct operator then? – Alexander Jan 16 '17 at 20:02
@Alexander The correct operator really depends on what you actually want. BTW, I have [answered this very question before](http://stackoverflow.com/a/34738970/1812457), and the solution there is a bit more general. – Jan 17 '17 at 07:15

score 2 · Accepted Answer · answered Jan 16 '17 at 18:59

I think the problem is that you do not provide a clause Prolog can take when H is not 4. This one is however easy: you simply perform a recursive call:

count_occ([H|T],N) :-
    H \= 4,
    count_occ(T,N).

Or a full implementation:

count_occ([],0).
count_occ([4|T],N1) :-
    count_occ(T,N),
    N1 is N+1.
count_occ([H|T],N) :-
    H \= 4,
    count_occ(T,N).

Count numbers in list

2 Answers2