Prolog Assignment

Question

This is the question for one of my assignments:

Write repCount(L, X, N) which is true when N is the number of occurrences of X in list L.

Here's my code where I try to tackle the problem recursively:

repCount([], X, N) :-
   N is 0.
repCount([H|T], X, N) :-
   count([H|T], X, N).

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

And it works when I supply a list full of identical numbers like this:

?- repCount([2,2,2], 2, N).
N = 3.

But if I supply a list with at least one different value:

?- repCount([2,2,22], 2, N).
false.

It returns false. I cannot figure out why this happens or how to change it to 'skip' the non-matching value, rather than declare the whole thing false. Any input is appreciated.

score 4 · Accepted Answer · answered Feb 22 '12 at 19:31

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

here you declare that N should be N1+1 if X is H; however you do not define what should happen if X is not H (basically missing an else clause) this should work:

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

another way would be:

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

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

but this is inefficient since count(T,X,N1) will be called twice if X is not H. we can fix this by doing the check in the head of the clause:

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

count([H|T], X, N):- count(T, X, N1), N is N1.

or simply: count([H|T], H, N):- count(T, X, N1), N is N1 + 1.

count([H|T], X, N1):- X=\=H, count(T, X, N1).

You should click upvote instead of saying "thank you" without upvoting the guy who helped you! — Warren P, Feb 22 '12 at 20:46
Too short of rep at the moment, but will do once I have enough. Thanks for the note! — IDDQD, Feb 22 '12 at 21:36

score 2 · Answer 2 · edited May 23 '17 at 12:23

Preserve logical-purity—with a little help from meta-predicate tcount/3 and (=)/3!

The goal tcount(=(X),Es,N) reads "there are N items in list Es that are equal to X".

Sample query:

?- tcount(=(X), [a,b,c,a,b,c,a,b,a], N).
(  N = 4,     X=a
;  N = 3,               X=b
;  N = 2,                         X=c
;  N = 0, dif(X,a), dif(X,b), dif(X,c)
).                                        % terminates universally

score 2 · Answer 3 · answered Feb 23 '12 at 14:12

2

One maybe interesting addition to what @magus wrote: If you only care about the number of elements instead of the elements themselves, you can use findall/3 like this:

list_elem_num(Ls, E, N) :-
    findall(., member(E, Ls), Ds),
    length(Ds, N).

answered Feb 23 '12 at 14:12

mat

40,498
3
51
78

score 1 · Answer 4 · answered Feb 22 '12 at 21:43

1

But assuming you aren't allowed to 'cheat', if you want to use recursion, you don't need to do the '==' comparison.. you can use Prolog's variable unification to reach the same end:

% Job done all instances
repCount2([], _, 0).

% Head unifies with X/2nd parameter - ie X found
repCount2([H|T], H, N) :-
    repCount2(T, H, NewN),
    N is NewN + 1.

% We got here, so X not found, recurse around
repCount2([_|T], X, N) :-
    repCount2(T, X, N).

In the second predicate, H is mentioned twice, meaning that if the Head of the list is the same as X, then recurse down, then add 1 to the result of the rest of the recursion (which ends in adding 0 - the base case, which is how the accumulator is built).

answered Feb 22 '12 at 21:43

magus

1,347
7
13

True, but...If you're going to do that, you need to a cut (`!`) in the 2nd clause to eliminate the choicepoint on backtracking, lest you come up with multiple results. Further if search term is unbound or the list contains unbound items, unification is likely to yield...unexpected results. – Nicholas Carey Feb 22 '12 at 22:42
1

@magus: Better use dif/2 in the last clause without a `!/0`. A `!/0` makes your program unnecessarily impure. – false Feb 22 '12 at 23:04
@false/Nicholas maybe provide a 'best' solution for this, in case the original poster / me doesn't understand what you said there.. / taking into account Nicholas' comments ? thanks. – magus Feb 22 '12 at 23:19

score 0 · Answer 5 · answered Feb 22 '12 at 20:17

Almost there...you need to use an accumulator, thus:

repCount(Xs,Y,N) :-
  count(Xs,Y,0,N) % the 3rd argument is the accumulator for the count, which we seed as 0
  .

count([],_,N,N).       % if the list is empty, unify the accumulator with the result
count([X|Xs],Y,T,N) :- % if the list is non-empty,
  X == Y ,             %   and the head of the list (X) is the the desired value (Y),
  T1 is T+1 ,          %   then increment the count, and
  count(Xs,Y,T1,N)     %   recurse down, passing the incremented accumulator
  .                    %
count([X|Xs],Y,T,N) :- % if the list is non-empty,
  X \== Y ,            %   and the head of the list(X) is not the desired value (Y),
  count(Xs,Y,T,N)      %   simply recurse down
  .                    %

score 0 · Answer 6 · answered Feb 22 '12 at 20:45

The original question didn't say whether there were constraints on which predicates you could use.

If you are allowed to 'cheat' ie. use higher order predicates like 'findall' that recurse for you Vs you doing the recursion yourself, this can be done in a single predicate:

repCount(L, X, N) :-
    findall(X, member(X, L), ListOfX),
    length(ListOfX, N).

Prolog Assignment

6 Answers6