Recursive search & Accumulators & Counters in Prolog

Question

After a long search on google I couldn't find a clear answer of this: In Prolog doing recursion by itself its easy. My main problem is understanding where to place accumulators and counters. Here is an example:

nXlist(N,X,[X|T]):-
    N \=0,
    N1 is N-1,
    nXList(N1,X,T).
nXList(0,_,[]).

media([X|L], N, Soma):-
   media(L, N1, Soma1),
   N is N1 + 1,
   Soma is Soma1 + X.
media([], 0, 0).

On the first example i used a counter BEFORE the recursion but in the second example I use it AFTER. The reason I have done that is the called try and see cause i really can't understand why sometimes is before and sometimes is after...

Answer 1

Short answer: you can place such arithmetical relations both before and thereafter. At least, if you are using constraints in place of (is)/2. The only difference may be in termination and errors.

So let's see how your predicates can be defined with constraints:

:- use_module(library(clpfd)).

nXList(0,_,[]).
nXList(N,X,[X|T]):-
    N #> 0,
    N1 #= N-1,
    nXList(N1,X,T).

media([], 0, 0).
media([X|L], N, Soma):-
   N #> 0,
   N #= N1 + 1,
   Soma #= Soma1 + X,
   media(L, N1, Soma1).

You can now use these definitions in a much more general way, say:

?- nXList(3, X, T).
   T = [X, X, X]
; false.
?- media(Xs, 3, S).
   Xs = [_A, _B, _C], _D+_A#=S, _C+_B#=_D
; false.

... nXList/3 can be more compactly expressed by:

..., length(T, N), maplist(=(X), T), ...

Answer 2

Maybe the central point of your question is in the preamble:

In Prolog doing recursion by itself its easy

It's not easy, it's mandatory. We don't have loops, because we don't have a way to control them. Variables are assign once.

So, I think the practical answer is rather simple: if the 'predicate' (like is/2) needs a variable value, you ground the variable before calling it.

To me, it helps to consider a Prolog program (a set of clauses) as grammar productions, and clause arguments as attributes, either inherited (values computed before the 'instruction pointer') or synthesized (values computed 'here', to be returned).

Answer 3

update: Most importantly, if the recursive call is not last, the predicate is not tail recursive. So, having anything after the recursive call should be avoided if possible. Notice that both definitions in the answer by user false are tail recursive, and that's precisely due to the fact that the arithmetic conditions there are placed before the recursive call, in both of them. That's so basic, that we have to make an effort to notice it explicitly.

---

Sometimes we count down, sometimes we count up. I discuss this in another answer at length. It talks of accumulators, befores and afters. :)

There's also this thing called "associativity" of an operation (say, +), where

a+(b+(c+....)) == (a+b)+(c+...)

that lets us regroup and (partially) calculate sooner rather than later. As soon as possible, but not sooner.