I just started in prolog and I have a question regarding recursion.
I basically want to count the number of time a certain value is in a list, so I have for example:
count( a, [ a, s, d, f, g, a, s, d, a, s ], W ). W = 3.
Where I want to count the number of time "a" is in the list and store the number in "W".
The correct answer is
count( _, [], 0 ).
count( A, [B|S], X ) :- A==B, count( A, S, Y ), X is Y + 1.
count( A, [B|S], X ) :- \+ A == B, count( A, S, X ).
Howhever, I do not understand why in line 2, the is a "X is Y+1" at the end. Shouldn't the line rather be
count( A, [A|S], X ) :- Y is X + 1, count( A, S, Y ).
In that case, we first set Y to 1, then we send it to "count" again with the recursion.
If anyone can help me I'd appreciate it very much!
Consider that when you call:
?- count(a,[a,s,d,f,g,a,s,d,a,s],W).
...then first predicate that matches is count(A,[B|S],X). So that means that it sees it like count(a,[a|S],X) where S & X are variables. X is just W from the original call so it is still a variable.
Suggesting that Y is X + 1 is then evaluated doesn't make sense as X is a variable.
The original predicate, however, does make sense.
count(A,[B|S],X) :- A==B, count(A,S,Y), X is Y + 1.
When it recurses it sends in a new variable Y into the 2nd count/3 predicate (or just passes the same variable in the 3nd predicate). And it keeps doing that until it hits the base case when it finally unifies the variable to 0. At that point it unwinds the recursion and now it can finally do X is Y + 1 (because Y is a value) and hence X is now a value.
Prolog is a fun language because it almost has a sense of time travel in the way you have to think forwards and backwards to understand how a program works.