I am new to Prolog and am not that great when it comes to recursive algorithms as is, thus I am confused with the following two clauses:
size([], 0).
size([H|T], N) :- size(T, N1), N is N1+1.
I am having trouble tracing this problem for:
?- size([a,b,c,d], N).
This will unify with the second clause to form:
size([a,b,c,d], N) :- size([b,c,d], N1), N is N1+1.
But I am confused with the N is N1+1 as these variables are never unified. What values do these variables take?
Any help regarding this question, or a simple trace of this algorithm, would be greatly appreciated.
the N is N1+1 as these variables are never unified.
I think you mean that they are never instantiated i.e. they never get a value. Unifying two variables can instantiated them but it's not necessary. For example you could run this in a prolog REPL:
?- N = N1.
N = N1.
while N and N1 have no value (yet), they are unified; if N1 gets instantiated later, N will be instantiated with the same value as well. Another, less trivial, example:
?- [H|T] = L, L = [1|M], writeln(H).
1
H = 1,
T = M,
L = [1|M].
However, it is true that N is never unified with N1+1! is will evaluate N1+1 and that value will be unified with N. This will happen after the inner size([b,c,d],N1) has been evaluated so the N1 variable will have been instantiated.
Essentially, the execution will be like this:
size([a,b,c,d],N).
size([b,c,d],N1)
size([c,d],N1)
size([d],N1)
size([],0)
N is 0+1.
N is 1+1.
N is 2+1.
N is 3+1.
Which is a bit inefficient as we need to keep all the function calls in memory; look into tail-recursion and accumulators to fix this.
Also note that N1 needs to be instantiated only because is is going to evaluate the expression. You could write something like this:
size([],0).
size([_|T], 1+ N1):-size(T,N1).
and if you call it:
?- size([1,2],N).
N = 0+1+1.
Fun, isn't it? You might want to evaluate the last N, e.g. call it as size([1,2],N), Result is N. However, one problem is that we keep a chain of 0+1+1+1+1+...... in memory which can get big very fast. So it's best to use this trick for things that are not going to grow, e.g. expression templates.
