prologswi-prolog

Problem With a Predicate to Check if X Occurs Exactly Four Times in a List


I'm trying to write a predicate fourExactly(X, List) which checks whether the variable X appears in the List exactly four times. The predicate shoud be true if that is the case and false if not. Here is my current implementation:

fourExactly(X, List) :-
    count_occurrences(X, List, 4).
% Base case: An empty list has zero occurrences of any element.
count_occurrences(_, [], 0).
% Recursive case: If the head of the list is X, increment the count.
count_occurrences(H, [H|T], Count) :-
    count_occurrences(H, T, RestCount),
    Count is RestCount + 1.
% Recursive case: If the head of the list is not X, do not increment the count.
count_occurrences(H, [_|T], Count) :-
    count_occurrences(H, T, Count).

My current implementation works correctly if there is less than four Xs in the List(false), and if there is exactly four (true). If there is more than four, it stops functioning correctly and the output looks like this:

?- fourExactly(n, [n, n, n, n, n, a]).
Yes (0.00s cpu, solution 1, maybe more)
Yes (0.00s cpu, solution 2, maybe more)
Yes (0.00s cpu, solution 3, maybe more)
Yes (0.00s cpu, solution 4, maybe more)
Yes (0.00s cpu, solution 5, maybe more)
No (0.00s cpu)

I think this has something to do with Prolog's backchaining, but I'm not sure how to fix it. I'd appreciate any help.

Thanks in advance for your help


Solution

  • Use dif, and counting from zero, and prevent counting past the maximum (if the maximum was specified):

    select_eq_count(L, E, C) :- 
        % Start counting at 0
        select_eq_count_(L, E, 0, C).
    
    % End of list, so unify the count
    select_eq_count_([], _, C, C).
    select_eq_count_([E|T], E, U, C) :-
        % The head of the list is equal to the element
        % Prevent exceeding the count if specified
        (   nonvar(C)
        ->  C > U
        ;   true
        ),
        U1 is U + 1,
        select_eq_count_(T, E, U1, C).
    select_eq_count_([H|T], E, U, C) :-
        % Different
        dif(H, E),
        select_eq_count_(T, E, U, C).
    

    This is perfectly general, e.g. no need to specify the count:

    ?- length(L, 2), select_eq_count(L, E, C).
    L = [E, E],
    C = 2 ;
    L = [E, _A],
    C = 1,
    dif(_A, E) ;
    L = [_A, E],
    C = 1,
    dif(_A, E) ;
    L = [_A, _B],
    C = 0,
    dif(_A, E),
    dif(_B, E).
    

    ... so can then count to 4, e.g.:

    ?- length(L, 5), select_eq_count(L, E, 4).
    L = [E, E, E, E, _A],
    dif(_A, E) ;
    L = [E, E, E, _A, E],
    dif(_A, E) ;
    L = [E, E, _A, E, E],
    dif(_A, E) ;
    L = [E, _A, E, E, E],
    dif(_A, E) ;
    L = [_A, E, E, E, E],
    dif(_A, E) ;
    false.