CODEWITHSUNDEEP
listprologsumappend
Arnau Van Boschken ArnauB
Arnau Van Boschken ArnauB

Reputation: 121

Member of a list, sum previous members list prolog

I want to verify if a member of list, is the sum of the previous numbers.

Example: [0,1,3,4,18,19]. This is TRUE because 0+1+3 = 4

sum_([],0).
sum_([X|XS],R):- suma(XS,R1), R is X + R1.


existsSum(L,[X|C]):-append(A,[X|B],L),
                    append(A,B,C),
                    sum_(C,X).

I am stuck here. Any idea? Thanks.

Upvotes: 0

Views: 68

Answers (2)

Daniel Lyons
Daniel Lyons

Reputation: 22803

I think your problem is ill-stated (or your example should not start with zero) because I think you basically have two ways you can process the list: either you process the entire list every time (and your example fails because 0+1+3+4+18 != 19) or you stop as soon as your expected value matches the head of the list, in which case [0] is already successful.

In the end, there aren't that many ways to process a list. You have to make a decision when you have an element, and you have to make a decision when you are out of elements. Suppose we want to succeed as soon as we have reached a value that matches the sum-so-far. We can model that fairly simply like this:

exists_sum(List) :- exists_sum(0, List).

exists_sum(RunningTotal, [RunningTotal|_]).
exists_sum(RunningTotal, [H|T]) :- 
  NewRunningTotal is RunningTotal + H,
  exists_sum(NewRunningTotal, T).

Note that with this formulation, [0|_] is already successful. Also note that I have no empty list case: if I make it to the end of a list without having succeeded already, there is no solution there, so there's nothing to say about it.

The other formulation would be to require that the entire list is processed, which would basically be to replace the first exists_sum/2 clause with this:

exists_sum(Total, [Total]).

This will fail to unify exists_sum(4, [4|_]) which is the case you outline in the question where [0,1,3,4...] succeeds.

There may be other formulations that are more complex than these, but I don't see them. I really think there are only a couple ways to go with this that make sense.

Upvotes: 1

fferri
fferri

Reputation: 18950

Why append(A,[X|B],L),append(A,B,C),sum_(C,X)? In this way you want the sum of all elements except X to be equal to X.

It is not clear what the arguments of existsSum should be. Supposing existsSum(InputList, SubList, Element):

existsSum(L,A,X) :- append(A,[X|_B],L), sum_(A,X).

With your example produces these results:

?- existsSum([0,1,3,4,18,19], Sublist, Element).
Sublist = [],
Element = 0 ;
Sublist = [0, 1, 3],
Element = 4 ;
false.

Note: also [] and 0 is a solution because of how you defined the sum_ predicate, i.e. the sum of [] is 0.

If you change the sum_ predicate in this way:

sum_([X],X).
sum_([X|XS],R):- sum_(XS,R1),R is X + R1.

it is defined only for non-empty lists, and in this case you get only one result from your example:

?- existsSum([0,1,3,4,18,19], Sublist, Element).
Sublist = [0, 1, 3],
Element = 4 ;
false.

Upvotes: 1

Related Questions