Prolog predicate without using lists

Question

I am required to write a prolog predicate count(X,Y,D,N) without using lists that should count the number of elements between two integers X and Y inclusive. However, it should only count those values that are divisible by D.

For example, count(3,6,2,N) should return N = 2 because 4 and 6 are divisible by 2, but 3 and 5 are not.

Nicholas Carey Nicholas Carey · Accepted Answer · 2021-04-23T20:58:01

Recursion is your friend here (as is the case with most things Prolog).

A helper predicate that takes an additional parameter that acts as an accumulator is useful here:

Something like this should do you:

count( X, Y, D, N ) :- count( X, Y, D, 0, N ) .

count( X , Y , D , T , N ) :- X =< Y,     % If X <= Y ...
  ( X rem D =:= 0                         % - and X is divisible by D
    -> T1 is T+1                          %   - then increment T
    ;  T1 = T                             %   - otherwise don't
  ),                                      % and
  X1 is X+1,                              % - increment X
  count( X1, Y, D, T1, N ).               % - recurse down
count( X , Y , _ , N , N ) :- X > Y.      % IF X > Y, we're done: unify the accumulator with the result.

The above is tail-recursive and is for all intents and purposes optimized into iteration. The more classic recursive solution is something like this:

count( X, Y, _, 0 ) :- X >  Y .
count( X, Y, D, N ) :- X =< Y ,
    X1 is X+1,
    count( X1, Y, D, T ),
    ( 0 =:= X rem D ->  N is T+1 ; N = T )
    .

Prolog predicate without using lists

1 Answers