Prolog count list elements higher than n

Question

I'm kinda new to Prolog so I have a few problems with a certain task. The task is to write a tail recursive predicate count_elems(List,N,Count) condition List_Element > N, Count1 is Count+1.

My approach:

count_elems( L, N, Count ) :-
   count_elems(L,N,0).
count_elems( [H|T], N, Count ) :-
   H > N ,
   Count1 is Count+1 ,
   count_elems(T,N,Count1).
count_elems( [H|T], N, Count ) :-
   count_elems(T,N,Count).

Error-Msg:

ERROR: toplevel: Undefined procedure: count_elems/3 (DWIM could not correct goal)

I'm not quite sure where the problem is. thx for any help :)

lurker · Accepted Answer · 2013-12-02T14:39:43.870

If you want to make a tail-recursive version of your code, you need (as CapelliC points out) an extra parameter to act as an accumulator. You can see the issue in your first clause:

count_elems(L, N, Count) :- count_elems(L,N,0).

Here, Count is a singleton variable, not instantiated anywhere. Your recursive call to count_elems starts count at 0, but there's no longer a variable to be instantiated with the total. So, you need:

count_elems(L, N, Count) :-
    count_elems(L, N, 0, Count).

Then declare the count_elem/4 clauses:

count_elems([H|T], N, Acc, Count) :-
    H > N,                            % count this element if it's > N
    Acc1 is Acc + 1,                  % increment the accumulator
    count_elems(T, N, Acc1, Count).   % check the rest of the list
count_elems([H|T], N, Acc, Count) :-
    H =< N,                           % don't count this element if it's <= N
    count_elems(T, N, Acc, Count).    % check rest of list (w/out incrementing acc)
count_elems([], _, Count, Count).     % At the end, instantiate total with accumulator

You can also use an "if-else" structure for count_elems/4:

count_elems([H|T], N, Acc, Count) :-
    (H > N
    ->  Acc1 is Acc + 1
    ;   Acc1 = Acc
    ),
    count_elems(T, N, Acc1, Count).
count_elems([], _, Count, Count).

Also as CapelliC pointed out, your stated error message is probably due to not reading in your prolog source file.

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

Preserve logical-purity with clpfd!

Here's how:

:- use_module(library(clpfd)).

count_elems([],_,0).
count_elems([X|Xs],Z,Count) :-
   X #=< Z,
   count_elems(Xs,Z,Count).
count_elems([X|Xs],Z,Count) :-
   X #> Z,
   Count #= Count0 + 1,
   count_elems(Xs,Z,Count0).

Let's have a look at how versatile count_elems/3 is:

?- count_elems([1,2,3,4,5,4,3,2],2,Count).
Count = 5 ;                                   % leaves useless choicepoint behind
false.

?- count_elems([1,2,3,4,5,4,3,2],X,3).
X = 3 ;
false.

?- count_elems([1,2,3,4,5,4,3,2],X,Count).
Count = 0, X in 5..sup ;
Count = 1, X = 4       ;
Count = 3, X = Count   ;
Count = 5, X = 2       ;
Count = 7, X = 1       ;
Count = 8, X in inf..0 .

Edit 2015-05-05

We could also use meta-predicate tcount/3, in combination with a reified version of (#<)/2:

#<(X,Y,Truth) :- integer(X), integer(Y), !, ( X<Y -> Truth=true ; Truth=false ).
#<(X,Y,true)  :- X #<  Y.
#<(X,Y,false) :- X #>= Y.

Let's run above queries again!

?- tcount(#<(2),[1,2,3,4,5,4,3,2],Count).
Count = 5.                                           % succeeds deterministically

?- tcount(#<(X),[1,2,3,4,5,4,3,2],3).
X = 3 ;
false.

?- tcount(#<(X),[1,2,3,4,5,4,3,2],Count).
Count = 8, X in inf..0 ;
Count = 7, X = 1       ;
Count = 5, X = 2       ;
Count = 3, X = Count   ;
Count = 1, X = 4       ; 
Count = 0, X in 5..sup .

A note regarding efficiency:

count_elems([1,2,3,4,5,4,3,2],2,Count) left a useless choicepoint behind.
tcount(#<(2),[1,2,3,4,5,4,3,2],Count) succeeded deterministically.

You don't! `(=)/3` is about *syntactic equality* but you want equality modulo CLPFD — false, May 04 '15 at 17:24

score 2 · Answer 3 · answered Dec 02 '13 at 13:05

Seems you didn't consult your source file.

When you will fix this (you could save these rules in a file count_elems.pl, then issue a ?- consult(count_elems).), you'll face the actual problem that Count it's a singleton in first rule, indicating that you must pass the counter down to actual tail recursive clauses, and unify it with the accumulator (the Count that gets updated to Count1) when the list' visit is done.

You'll end with 3 count_elems/4 clauses. Don't forget the base case:

count_elems([],_,C,C).

Prolog count list elements higher than n

3 Answers3

Edit 2015-05-05

Linked