Given [1,2,3] in prolog get back [6,5,3] by reverse accumalation

Question

Q. Given [1,2,3] in prolog get back [6,5,3] by reverse accumalation

I have the start code:

accumalate([H],[H]).

accumalate([H1 | H2], [Hnew, H2]), Hnew is H1 + H2.

....

I am looking for basic prolog solution. thanks guys

Answer 1

We are not here to do you homework for you. So the best we can do is provide you with some tips. So ask yourself these questions:

1. What are the base cases here (for which inputs is the output immediate)?
   • You have accumulate([N], [N])., but what about empty lists?
2. In what order must the additions be performed?
3. More specifically, which elements must be added first?

Other than that, I can tell you that you can solve this using three clauses. No other predicates required. Good luck!

Bonus: you may want to define the head of the recursive clause as follows:

accumulate([N|T], [N1,N2|T2]).

Answer 2

Once you are done with the basic implementation , Try solving this problem in O(n) time. The idea is to start from the first element and keep on adding it to a secondary list till your original list is empty. The secondary list is the reverse list which you need.

If you append the two lists in your recursive step, you will end up having a O(N^2) complexity.

Answer 3

Here is my take:

accumulate([],[]).
accumulate([H|T], [H1|T1]):-
    sum([H|T],H1),
    accumulate(T,T1).
sum([],0).
sum([H|T],Y):-
    sum(T,Y1),
    Y is H + Y1.

You can of course use a built-in sumlist/2 in place of the hand-crafted sum/2 if you prefer that.