I can't figure out why this is constantly returning false. I can count the number of element "e" in a list in odd positions if I call another function, but I want to do it in a more clean and compact way. Here is the code:
count(_,[],0).
count(E,[E,_|T],C) :-
count(E,T,D),
C is D+1.
count(E,[H,_|T],C) :-
E\=H,
count(E,T,C).
@Sergey's answer is it. But you might want to know how you can find out such problem yourself. Prolog actually can help you to fully understand your Prolog programs. Much more than other languages are able to explain themselves. Here is how:
Your program is almost a pure, monotonic program. Except for the (\=)/2 which should be replaced by dif/2 or dif_si/2. See this answer why.
count(_,[],0).
count(E,[E,_|T],C) :-
count(E,T,D),
C is D+1.
count(E,[H,_|T],C) :-
dif(E,H), % replaces E \= H
count(E,T,C).
You have complained that your program is "constantly" returning false. Is this really the case? What test cases have you considered? Is there a way to prove this? In traditional, value oriented programming languages1 the answer would be that you need to resort to some analyzer. But there is no way to prove it within the language. Maybe you are lucky to find test cases that are true. Maybe not.
Not so in Prolog! Here, you can always give a query that will be true, provided there is some test case that is true2. And you don't need to do any thinking (OK, pretend you are thinking). Simply use for each argument a different new variable. So, given your predicate count/3, aah, let me think, please stop this noisy typing, I have to understand it (feign-fake-feign), .... it is:
?- count(E, Xs, M).
For, should there be any other query that succeeds, it would be an instance of this query. Thus, it would be more specific than this one. And thanks to monotonicity the more general query has to be true as well. And, we get now lavishly counterexample after counterexample served on a silver plate, er, top-level shell:
?- count(E, Xs, N).
Xs = [], N = 0
; Xs = [E,_A], N = 1
; Xs = [E,_A,E,_B], N = 2
; Xs = [E,_A,E,_B,E,_C], N = 3
; Xs = [E,_A,E,_B,E,_C,E,_D], N = 4
; ... .
So you complained that your predicate is false, but we have so far received 5 answers that are true. And those answer contain infinitely many solutions. To get all solutions, replace all remaining variables by whatever ground term you like. Like count(1,[1,1],1), count(hi,[hi,u],1) etc.
Are these all answers/solutions? Will Prolog enumerate all of them, provided our computing resources are not exhausted? Think how you can enumerate all integers:
0, 1, 2, 3, ... -3, -2, -1.
Well, for us finite beings, it does not work that way. We would have to start
0, 1, -1, 2, -2, 3, -3, ...
so it is fine to have one infinite sequence, but if we are unlucky we might have some values "behind" one.
But we are not out of luck! There are situations where we do get nice infinite sequences. Think of:
?- length(Xs, L).
Xs = [], L = 0
; Xs = [_A], L = 1
; Xs = [_A,_B], L = 2
; Xs = [_A,_B,_C], L = 3
; Xs = [_A,_B,_C,_D], L = 4
; Xs = [_A,_B,_C,_D,_E], L = 5
; ... .
And now, combined with our original query:
?- length(Xs, L), count(E, Xs, N).
Xs = [], L = 0, N = 0
; Xs = [E,_A], L = 2, N = 1
; Xs = [_A,_B], L = 2, N = 0, prolog:dif(E,_A)
; Xs = [E,_A,E,_B], L = 4, N = 2
; Xs = [E,_A,_B,_C], L = 4, N = 1, prolog:dif(E,_B)
; ... .
These are all answers, sorted by length of the list. Once we see an increase in value for L, we know that all lengths below it have been enumerated already!
Let's look at the values for L! They are 0, 2, 2, 4, 4, 4, 4, 6, ... Where are the odd lengths? Evidently they are missing. And thus your program is too specialized. Maybe start with the smallest possible example...
Another way to understand the problem is to read the arrows right-to-left, that is exactly in the direction the :- is pointing.
From the fact we know that Xs = [], from both rules we can conclude from this to Xs = [_,_] and then Xs = [_,_,_,_]. Thus, only even lengths are enumerated.
Finally, here is another way to write count/3:
count(_E, [], 0).
count(E, [E|Xs], N0) :-
count1(E, Xs, N1),
N0 is N1+1.
count(E, [X|Xs], N) :-
dif(E, X),
count1(E, Xs, N).
count1(_E, [], 0).
count1(E, [_|Xs], N) :-
count(E, Xs, N).
Ah, and I forgot to mention library(clpfd) which could be used as well. See clpfd
1 It is easy to spot value oriented programming languages: Their variables are at runtime always values!
2 Certain restrictions apply: Actually that is only the case in a pure monotonic program, that's why I insisted on that property in the first place. And then, the result might be overshadowed by non-termination or errors.
If your Prolog system supports clpfd, you can use the following
definition of count/3. The code shown here is both efficient (avoiding the creation of useless choicepoints) and logically pure.
count(E,Xs,C) :-
C #>= 0,
list_item_count(Xs,E,C).
list_item_count([],_,0).
list_item_count([X,_|Xs],E,C) :-
if_(E=X, C0+1 #= C, C0 = C),
list_item_count(Xs,E,C0).
Moving on to some queries:
?- count(1,[1,2,3,1,2],C). % fails: list has wrong length
false.
?- count(1,[1,2,3,1,2,1],C).
C = 1. % succeeds deterministically
?- count(E,[1,2,3,1,2,1],C). % now some more general query!
E = C, C = 1 ; % this must be non-deterministic ...
E = 3, C = 1 ; % ... lest we lose solutions!
E = 2, C = 1 ;
C = 0, dif(E,2), dif(E,3), dif(E,1).
?- length(Xs,_),count(X,Xs,C). % even more general; fair enumeration
C = 0, Xs = [] ;
C = 1, Xs = [X,_A] ;
C = 0, Xs = [_A,_B], dif(X,_A) ;
C = 2, Xs = [X,_A,X,_B] ;
C = 1, Xs = [X,__A,_B,_C], dif(X,_B) ;
C = 1, Xs = [_A,_B, X,_C], dif(X,_A) ;
C = 0, Xs = [_A,_B,_C,_D], dif(X,_A),dif(X,_B) ;
C = 3, Xs = [X,_A, X,_B, X,_C] ;
C = 2, Xs = [X,_A, X,_B,_C,_D], dif(X,_C) ...
Your current formulation is correct when the list has even number of elements:
?- count(x, [x, y, x, x], C).
C = 2
But it will fail if the number of elements is odd.
To correct this you can just add couple of rules for one-element lists:
count(E,[E],1).
count(E,[H], 0):-
E\=H.
Now it works for lists with odd number of elements:
?- count(x, [x, y, x, x, x], C).
C = 3
?- count(y, [x, y, x, x, x], C).
C = 0
?- count(x, [y, y, y, y, x], C).
C = 1
