Prolog - counting a number
Why doesn't it work?
Prolog is a programming language that can often directly answer this question. See how I tried your definition, starting with your failed request:
?- count(1, [1,0,0,1,0], X). false. ?- count(1, Xs, X). Xs = [], X = 0 ; Xs = [1], X = 1 ; Xs = [1, 1], X = 2 ; Xs = [1, 1, 1], X = 3 ... ?- Xs = [_,_,_], count(1, Xs, X). Xs = [1, 1, 1], X = 3 ; false.
So first I realized that the query was not working at all, then I am a generalized query. I replaced the big list with a variable Xs
and said: Prolog, fill in the blanks for me! And Prolog did it and revealed to us exactly those cases when it will be successful.
In fact, it only does well on lists of only 1. It's weird. Your definition is too limited - it correctly counts 1s in lists where there are only one, but all other lists are rejected. @coder showed you how to expand your definition.
Here's another one using SICStuslibrary(reif)
for
| SWI . Alternatively cm. .tfilter/3
count(X, Xs, N) :-
tfilter(=(X), Xs, Ys),
length(Ys, N).
The definition is more in the style of other definitions:
count(_, [], 0).
count(E, [X|Xs], N0) :-
if_(E = X, C = 1, C = 0),
count(E, Xs, N1),
N0 is N1+C.
And now for some more general uses:
What does a list of four elements look like that has 3 times 1 in it?
| ?- length(L, 4), count(1, L, 3).
L = [1,1,1,_A],
dif(1,_A)
; L = [1,1,_A,1],
dif(1,_A)
; L = [1,_A,1,1],
dif(1,_A)
; L = [_A,1,1,1],
dif(1,_A)
; false.
So the remaining element must be something other than 1
.
This is what the wonderful Prolog community offers us.
source to share
The problem is, as @lurker pointed out, if the condition (or better unification) fails, the predicate will fail. You can make another suggestion for this purpose using diff / 2, which is clean and defined in iso:
count(_, [], 0).
count(Num, [H|T], X) :- dif(Num,H), count(Num, T, X).
count(Num, [H|T], X) :- Num = H, count(Num, T, X1), X is X1 + 1.
The above is not the most efficient solution as it leaves many points of choice, but it is a quick and correct solution.
source to share
You are simply discarding the predicate when joining Num = X
. Basically, it's like you don't accept terms that are different from the only one you think.
I offer you this simple solution that uses tail recursion and scans the list in linear time. Despite its length, it is very efficient and graceful, using declarative programming techniques and the Prolog backtrack.
count(C, L, R) :-
count(C, L, 0, R).
count(_, [], Acc, Acc).
count(C, [C|Xr], Acc, R) :-
IncAcc is Acc + 1,
count(C, Xr, IncAcc, R).
count(C, [X|Xr], Acc, R) :-
dif(X, C),
count(C, Xr, Acc, R).
count/3
is a launch predicate. It takes a term for counting, list, and gives you the meaning of the result. The first count/4
is the main case of recursion. The second count/4
is executed when the head of the list is merged with the term you are looking for. The third is count/4
achieved with backtracking: if the term doesn't match, unification fails, you don't need to increment the counter.
Acc
allows you to scan the entire list, propagating the partial result of recursive processing. In the end, you just need to bring it back.
source to share