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

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

I have the start code:

accumalate([H],[H]).
accumalate([H1 | H2], [Hnew, H2]),
      开发者_JAVA百科 Hnew is H1 + H2.

....

I am looking for basic Prolog solution.

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

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.

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.

    ac([], 0, []).

    ac([H|T], ST, [ST|Res]) :-
        ac(T, X, Res),
        ST is H + X.

    accum(List, Res) :-
        ac(List, _, Res).

[trace]  ?- accum([1,2,3], X).
   Call: (6) accum([1, 2, 3], _G376) ? creep
   Call: (7) ac([1, 2, 3], _G458, _G376) ? creep
   Call: (8) ac([2, 3], _G461, _G454) ? creep
   Call: (9) ac([3], _G464, _G457) ? creep
   Call: (10) ac([], _G467, _G460) ? creep
   Exit: (10) ac([], 0, []) ? creep
   Call: (10) _G459 is 3+0 ? creep
   Exit: (10) 3 is 3+0 ? creep
   Exit: (9) ac([3], 3, [3]) ? creep
   Call: (9) _G456 is 2+3 ? creep
   Exit: (9) 5 is 2+3 ? creep
   Exit: (8) ac([2, 3], 5, [5, 3]) ? creep
   Call: (8) _G453 is 1+5 ? creep
   Exit: (8) 6 is 1+5 ? creep
   Exit: (7) ac([1, 2, 3], 6, [6, 5, 3]) ? creep
   Exit: (6) accum([1, 2, 3], [6, 5, 3]) ? creep
X = [6, 5, 3].