Currently playing around in Prolog... I'm having trouble groking the count list rule. I haven't been able to find a good explanation anywhere. Can someone give me a break down of it at each recursion?
count(0, []).
count(Count, [Head|Tail]) :-
count(TailCount, Tail),
Count is TailCount + 1.
One place says that it is recursive (which makes sense to me) and another that says it isn't.
The procedure it's recursive, but not tail recursive. Writing tail recursive procedures is an optimization that allows the system to transform recursion into iteration, avoiding useless stack usage for deterministics computations (like the one we are speaking of). In this case (that BTW it's the same of the builtin length/2, just with arguments swapped), we can use an accumulator, and rewrite the procedure in this way:
count(C, L) :- count(0, C, L).
count(Total, Total, []).
count(SoFar, Count, [_Head|Tail]) :-
Count1 is SoFar + 1,
count(Count1, Count, Tail).
Some system older required a cut before the recursive call, to make the optimization effective:
...,
!, count(Count1, Count, Tail).
The definition of the inference rule is recursive. This program tries to count the quantity of elements inside the list.
count(0, []). This is an axiom, a fact, something that its true because you said so. Here you are stating that every empty list has a count of zero.
count(Count, [Head|Tail]) :-
count(TailCount, Tail),
Count is TailCount + 1.
This is an inference rule, that it a rule that dictates that the left part of :- is true if the right part is true. This inference rule also uses pattern matching, wicth matchs non empty lists ([Head|Tail]).
Specifically, the count rule says that the Count variable of a non empty list is the count of the Tail part of the list, plus 1 (the plus 1 is for counting the Head element of the list).
trace., thencount(N, [1,2,3]).to see what the predicate does. – Fred Foo