Recursive search & Accumulators & Counters in Prolog

5
votes

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...

3
recursionprologcounteraccumulator
Typo-alert: Once you write nXlist and then nXList. – false
These difficulties with low-level arithmetic predicates are extremely common among beginners, and almost unsurmountable for the vast majority of aspiring Prolog programmers. I highly recommend you go with @false's advice, and use constraints instead of such moded predicates. Constraints let you very freely place the goals at any place you like, before or after other goals. You will have enough time to worry about operational considerations later. Even better, using constraints, you can actually try it out yourself, and see how different goal orderings affect your program's performance! – mat

3 Answers

3
votes

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), ...
3
votes

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).

3
votes

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.