Prolog check if list contains even number of an element

Question

I have to check if a list contains an even number of an element without built-ins.

Example:

containsEvenNumber([a,b,c,a,a], a).

returns false

containsEvenNumber([a,b,c,a], a).

returns true

Current state:

not(A) :-
    A, !,
    fail.
not(_).
equal([E|_], E).
containsEvenNumber([], _).
containsEvenNumber([E|Tail], E) :-
    unevenCount(Tail, E).

containsEvenNumber([Head|Tail], E) :-
    not(equal([Head|Tail], E)),
    evenCount(Tail, E).

evenCount([], _).
evenCount([E|Tail], E) :-
    unevenCount(Tail, E).

evenCount([Head, Tail], E) :-
    not(equal([Head|Tail], E)),
    unevenCount(Tail, E).

unevenCount([], _) :-
    fail.
unevenCount([E, Tail], E) :-
    evenCount(Tail, E).

unevenCount([Head, Tail], E) :-
    not(equal([Head|Tail], E)),
    unevenCount(Tail, E).

I try to switch between states upon the occurrence of the element. It doesn't work because I never go into the state, where the head is not the element or rather said, I also go into the state and return false when the head is the element.

How can I make it work/fix it?

Answer 1

The "switching between states" is actually a good way to solve this problem. The logic should follow these simple rules:

1. There are an even number of X elements in [X|Xs] if there are an odd number of X elements in Xs.

2. There are an even number of X elements in [Y|Xs] if X and Y are different, and there are an even number of X elements in Xs.

3. There are an odd number of X elements in [X|Xs] if there are an even number of X elements in Xs.

4. There are an odd number of X elements in [Y|Xs] if X and Y are different, and there are an odd number of X elements in Xs.

Then you have the base cases:

There are an even number of any element in [].

There are an odd number of X in [X].

You just need to write these rules as Prolog. However, your implementation has a few issues.

In a few cases, you are writing a list as [Head, Tail] instead of [Head|Tail]. [Head, Tail] is a list of exactly two elements. Also, your base case for unevenCount/2 (which I assume you mean odd count) is incorrect. If you have a base case that always fails, then your predicate will always fail. With few exceptions, you should write your predicate clauses to succeed, not fail. Failure will occur automatically when success cannot be achieved.

Let's try to write out the rules above. ISO Prologs already have \+, so you do not need to define not/1. Also, writing equal([E|_], E). is unnecessary. You can do this directly in your code with simplicity.

evenCount(_, []).          % base case for even
evenCount(X, [X|Xs]) :-    % rule #1
    oddCount(X, Xs).
evenCount(X, [Y|Xs]) :-    % rule #2
    dif(X, Y),
    evenCount(X, Xs).

oddCount(X, [X]).          % base case for odd
oddCount(X, [X|Xs]) :-     % rule #3
    evenCount(X, Xs).
oddCount(X, [Y|Xs]) :-     % rule #4
    dif(X, Y),
    oddCount(X, Xs).

SWI Prolog defines dif/2. You could also use \== but it's not purely defined (and so doesn't behave as generally) as dif/2.