Problem with accumulators in prolog

Question

While learning Prolog, I'm trying to solve the following problem, using accumulators:

Write a predicate addone2/ whose first argument is a list of integers, and whose second argument is the list of integers obtained by adding 1 to each integer in the first list. For example, the query
       addone([1,2,7,2],X).
should give
       X = [2,3,8,3].

I created the following code:

addone([], _).
addone([E|Tail], [R|Rs]) :-
    NewE is E+1,
    append([R|Rs], [NewE], NewRs),
    addone(Tail, NewRs).

But it's not working. Can someone tell me why? So, how do I use accumulators in Prolog?

Thanks!

Frank Frank · Accepted Answer · 2010-11-22T08:55:01

anthares is correct in that you have to refine your base case. However, you are also making things very inefficiently with your append calls. In Prolog, it takes some time to get used to the power of unification, but for example, in this case it helps you to immediately set up your result list. Try the following:

addone([E|Tail], [E1|Rs]) :-
    E1 is E+1,
    addone(Tail, Rs).

That's really all there is to it. By immediately placing E1 in your second argument's pattern, you have already created the first element of your result list. The remaining elements Rs will be created during the recursion. A very typical Prolog pattern.

Problem with accumulators in prolog

2 Answers