Prolog accumulator reversing

Question

I'm having a problem where my answer for every Prolog problem I'm posed ends up with the answer list being reversed. It's because I was shown how to use an accumulator to reverse a list, and now the only way I seem to be able to solve a problem is to use a similar program, which gives the answer, but also reverses the list.

For example, when asked to write a program which replaces all instances of the second argument inside the first argument with the third argument, and gives the resulting list as it's fourth argument, I wrote this code:

replace(L, A, B, X):-  
    accrep(L, [], A, B, X).   

accrep([H | T], Y, A, B, X):-
    H = A,  
    accrep(T, [B | Y], A, B, X). 

accrep([H | T], Y, A, B, X):-  
    H \= A,  
    accrep(T, [H | Y], A, B, X). 

accrep([], X, _, _, X).

This does indeed technically solve the problem, but also reverses the list, which wasn't asked for, and I doubt anyone would be impressed when I hand them the correct answer backwards. But I can't think of a way to avert this, and it seems ridiculous to add in code that unreverses the list, when I should never have reversed it in the first place.

Can anyone tell me how to use accumulators without running into this problem? I've had the same issue with multiple other simple programs too.

Thanks, Alex.

jschimpf jschimpf · Accepted Answer · 2014-03-14T01:50:53

Here is one way of looking at it: When you have a recursion with accumulator (usually implemented as an argument pair), it typically looks like this:

generic(..., Final, Final, ...).
generic(..., Previous, Final, ...) :-
    ...
    generic(..., Next, Final, ...).

The recursive clause

receives the Previous value of the accumulator
computes the Next accumulator value
and returns the Final accumulator value from the recursive call to the caller.

This is most obvious when implementing a counter, where all the accumulator arguments are integers. Previous is the old counter value, Next is one more, and Total is the final result:

counter(..., Total, Total, ...).
counter(..., Previous, Total, ...) :-
    ...
    Next is Previous+1,
    counter(..., Next, Total, ...).

What you have done is very similar: Each of your accumulator arguments is a proper list: Previous is the list you have built so far, Next is Previous with an extra element prefixed in front, and Final is the final list.

revlist(..., Final, Final, ...).
revlist(..., Previous, Final, ...) :-
    ...
    Next = [New|Previous],
    revlist(..., Next, Final, ...).

So far, so good. Now, remember that Prolog is pretty relaxed about the construction of data structures. You can leave holes in them (in the form of free variables), and fill them in later (by instantiating the variables). For lists, that means you can have a list with an uninstantiated tail, and provide the rest later. Put that together with the accumulator idea, and let all accumulator arguments be list tails: Previous is the end of the list so far, and you extend the list by instantiating Previous to another list element. This gives you a new tail, Next, which you pass into the recursion. You see that the only difference to the previous schema is the way the list element is constructed:

fwdlist(..., Final, Final, ...).
fwdlist(..., Previous, Final, ...) :-
    ...
    Previous = [New|Next],
    fwdlist(..., Next, Final, ...).

On success, the caller of this predicate will find the beginning of the list in the first accumulator argument, and the tail in the second. The list is in the same order the elements were created, and can be terminated by setting Final to [].

Notes: (1) the Final argument in the last case can be eliminated - I've just left it there to show the symmetry. (2) this whole explanation is very procedural and in terms of input/output arguments - in reality the list examples will work in multiple modes.

Prolog accumulator reversing

2 Answers