Resolved: Prolog prefix sum of a list

In this post, we will see how to resolve Prolog prefix sum of a list

Question:

I want to implement the prolog predicate prefixSum(L, R) that calculates the prefix sum of a list i.e:

?- prefixSum([1,2,3,4],R).
R=[1,3,6,10].

Here is my solution so far:

prefixSum([],[]).
prefixSum([X], [X])
prefixSum([X|Xs], [R, Rs|T]):- 
    Rs is X + R,  prefixSum(Xs, T).

What can I try next?

Best Answer:

Your original code,

prefixSum( []     , []       ) .
prefixSum( [X]    , [X]      )
prefixSum( [X|Xs] , [R,Rs|T] ) :- Rs is X+R, prefixSum(Xs,T) .

Has these problems:

The code is syntactically incorrect, as the 2nd clause is not terminated by ..
In the 3rd clause, the variable R will always be unbound unless you’ve provided a bound list as the 2nd argument to prefixSum/3, meaning Rs is X+R will fail.

The key to what you are trying to accomplish is that as you traverse the list, you need to track the sum previously computed as you go.
That leads to an implementation like this:

prefix_sum( []     , []     ) .  % the empty list is a special case
prefix_sum( [X|Xs] , [X|Ys] ) :- % for a non-empty list, we add the first item to the result , and
  prefix_sum(Xs,X,Ys) .          % invoke our helper, seeding the previous sum with the first element.

prefix_sum( []     , _ , []     ) .  % once the source list is exhausted, we're done.
prefix_sum( [X|Xs] , P , [Y|Ys] ) :- % otherwise...
  Y is P+X,                          % compute the sum of the current element and the previous sum
  prefix_sum(Xs,Y,Ys) .              % and recurse down on the tails.

If you have better answer, please add a comment about this, thank you!

Source: Stackoverflow.com

Question:

Best Answer:

Related