It's great that you got it working now, by using declarative arithmetic!
I have a few minor additional comments about the solution you obtained, i.e.:
count(_, [], 0) :- !.
count(El, [El|T], N) :-
count(El, T, N1),
N #= N1 + 1.
count(El, [Y|T], N) :-
El \= Y,
count(El, T, N).
check(List1, List2) :-
count(3, List1, M),
count(2, List2, N),
M #= N.
First, note that check/2 is nowhere used in the code, so I omit its definition in the following.
Most general query
When I review Prolog code I know nothing about, I always try the most general query first, where all arguments are variables. Ideally, the answers show me what solutions look like in general.
For example, in your case:
?- count(E, Ls, C).
Ls = [],
C = 0.
This—erroneously—suggests that there is only a single solution of your predicate! This is obviously not intended.
Therefore, as a first step, I recommend you remove the !/0 and change this code to:
count(_, [], 0).
count(El, [El|T], N) :-
count(El, T, N1),
N #= N1 + 1.
count(El, [Y|T], N) :-
El \= Y,
count(El, T, N).
With this change applied, we get:
?- count(E, Ls, C).
Ls = [],
C = 0 ;
Ls = [E],
C = 1 ;
Ls = [E, E],
C = 2 ;
Ls = [E, E, E],
C = 3 .
This looks much better: We now get several valid answers.
Termination
How many answers might this predicate yield? In particular, are there only finitely many answers? If so, we would expect the following query to terminate:
?- count(E, Ls, C), false.
You can try it, and see that it in fact doesn't terminate (at least not very soon). That's a good sign, because from a correct implementation of count/3, we expect nontermination in the most general case!
Completeness
Ideally, we would like the predicate to be complete: It should not omit valid answers.
For example:
?- count(E, [X,Y,Z], C).
E = X, X = Y, Y = Z,
C = 3 ;
false.
Are these really all solutions? I don't think so! Certainly there are lists of length 3 that are different from [E,E,E].
And, in fact, your program also "knows" about them in a sense:
?- count(E, [1,2,3], C).
E = C, C = 1 ;
false.
But again, these are certainly not all cases! Where are the answers in which E is different from 1?
You are facing these issues because you are using the non-monotonic (\=)/2 predicate. This has a few very hard to understand properties, especially if you are currently only beginning to learn Prolog. For example:
?- X \= Y, X-Y = a-b.
false.
?- X-Y = a-b, X \= Y.
X = a,
Y = b.
I recommend to use dif/2 instead to denote that two terms are different, obtaining the following version:
count(_, [], 0).
count(El, [El|T], N) :-
count(El, T, N1),
N #= N1 + 1.
count(El, [Y|T], N) :-
dif(El, Y),
count(El, T, N).
Wit this version, we get:
?- count(E, [X,Y,Z], C).
E = X, X = Y, Y = Z,
C = 3 ;
E = X, X = Y,
C = 2,
dif(Y, Z) ;
E = X, X = Z,
C = 2,
dif(Z, Y) ;
etc.
And, in particular:
?- count(E, [1,2,3], C).
E = C, C = 1 ;
E = 2,
C = 1 ;
E = 3,
C = 1 ;
C = 0,
dif(E, 3),
dif(E, 2),
dif(E, 1).
This covers all cases that can arise!
Fair enumeration
Since the predicate is pure and monotonic, we can use it to fairly enumerate answers by iterative deepening.
For example:
?- length(Ls, _), count(E, Ls, C).
Ls = [],
C = 0 ;
Ls = [E],
C = 1 ;
Ls = [_G588],
C = 0,
dif(E, _G588) ;
Ls = [E, E],
C = 2 ;
Ls = [E, _G597],
C = 1,
dif(E, _G597) .
C = 2 ;
etc.
That's pretty nice, and shows that we can use this as a true relation, not only for counting, but also for generating.
Hence, you may consider a predicate name that more appropriately describes what this predicate means in general. I leave this as an exercise.
Tail recursive version
Note that since you are using pure predicates, you can freely reorder your goals, and make your predicate tail recursive, yielding:
count(_, [], 0).
count(El, [El|T], N) :-
N #= N1 + 1,
count(El, T, N1).
count(El, [Y|T], N) :-
dif(El, Y),
count(El, T, N).
Determinism
We currently still have for example:
?- count(a, [a,a,a], Cs).
Cs = 3 ;
false.
Using if_/3, you can improve determinism of this predicate:
:- use_module(library(reif)).
count(_, [], 0).
count(E, [L|Ls], N) :-
if_(E=L, N #= N1 + 1, N #= N1),
count(E, Ls, N1).
This makes your predicate at least amenable to indexing. Whether you improve determinism in such cases depends on your Prolog system's indexing mechanism.
