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

Atlantes

Typo-alert: Once you write nXlist and then nXList. – Mistake

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! – Jointly

Answer 1

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.

Programmer

Hmnm, does so much operationalization help? Before, beafter and all that command oriented stuff. – Mistake

@Mistake I thought about it as more like equational stuff. the LHS expresses recursion; the RHS -- iteration with accumulator, what the OP asks about. – Programmer

But in the presence of moded arithmetics, there is not much space for equational reasoning. – Mistake

@Mistake there should be though. we should be able to assume that summing up a ground list always takes O(1) additional space. – Programmer

What is a better starting point: a program that describes the actual relation adequately but is not O(1) for your case, or a program that does not work at all - be it in O(1) or whatever? – Mistake

@Mistake for some, a relation is easier to understand as being built of several processes, each for each direction. – Programmer

To take this very example: I cannot see how your (moded) approach is able to get any intermediary definition in between. – Mistake

@Mistake all I know is, I don't want to choose between declarativeness and efficiency; and when I intend to use a predicate as a function, it is OK for me to write it that way to be used in appropriate circumstances - precisely because the general version gives no efficiency guarantees. – Programmer

That's a false dilemma: The same efficiency considerations apply to any version, also to the less general one! The less general one only makes testing and reasoning about efficiency a lot harder since it errors out so easily. – Jointly

@Jointly If accumulation can be written with constraints, all the better. all I said in the answer is that associativity enables iteration with accumulation. What's so operationalized in that? I never said anything about arithmetic, + was used as an abstract symbol. "before" or "after" is just positional: in A, B, A is placed before B. – Programmer

I was referring to OP's version in comparison to false's more general one since I assumed you referred to it too with "the general version". – Jointly

@Jointly I don't know what are we talking about anymore. I know I don't want to not think about such stuff (as in the answer), and instead write everything with constraints in some random form and rely on them magically sorting everything out for me somehow. Whether it is "operationalized" or not, I don't know. – Programmer

@Mistake I edited, to stress the positionality of "before" and "after" and its relation to tail recursion. – Programmer

Not sure that my version can be considered tail recursive: Currently, constraints do use quite some non-constant space for the cases (here in this very example) you expect to run in constant space. (I hope that will go away some time.) – Mistake

@Mistake perhaps it can, as it doesn't grow the stack. constraints are a black box / magic, as far as regular Prolog user is concerned. – Programmer

Answer 2

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

Mistake

Answer 3

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

Reality