Prolog predicate that will check if a list A is a list of the prefix sums of a list D

Question

So I'm very new to prolog and have to write a predicate that is satisfiable when an integer list D is the list of prefix sums of a list A.

sums(A, D)

So for example,

sums([4,11,1,-3,8], [4,15,16,13,21]) is satisfiable

I have written this predicate over a dozen different ways to no avail. This is what I currently have written.

sums([], []).
sums([A], [A]).
sums([A|[B|C]], [A|[E|F]]) :- TOTAL is A + B, E = TOTAL, sums([C], [F]).

This somewhat works, in that it will check that the first values of each list are equal, and also check that the second element in the list is correct in that it should be 15. I understand why it works incorrectly in this way, but I am having trouble coming up with how to write it differently, in the correct way.

I have since changed the code to,

sumrunner(L, S) :- sumrunner(L, S, 0).
sumrunner([], [], _).
sumrunner([A], [A], _).
sumrunner([A|B], [C|D], TOTAL) :- TOTAL is TOTAL + A, TOTAL = C,sumrunner(B, D, TOTAL).

However, now it just says false for all cases except for when the two lists are empty, and when the lists both contain one element and they are both equal to each other.

You mean predicate not functor (I edited your question). If you wrote the term, foo(a, b), then foo is a term referred to as a functor with two arguments a and b. functor just refers to the foo part, which must be an atom. But it has no other assigned purpose as a functor. A predicate uses a functor as its head to implement a rule. A functor can also be used to declare facts or otherwise structure data. There are a few different Prolog glossaries online. — lurker
@lurker. The glossary you linked to somewhat low in quality. Consider the entry for functor: "A functor is the part of a goal or query that comes before the '('. Functors must obey exactly the same naming rules as atoms." OTOH look at this part of the SICStus Prolog documentation ... quite a difference, don't you agree? — repeat
@repeat yes, I agree in hindsight and wasn't totally happy with it, but had to start somewhere. To be honest I couldn't find two Prolog glossaries that matched. No definitive location for "the official Prolog glossary". Believe it or not, I found some that were even lower fidelity than that one. — lurker
@lurker. Anyway thx 4 getting the ball rolling! The "definitive" glossary (ISO/IEC 13211-1:1995) isn't available for free;( But here's the good news: The SICStus Prolog 4.3.5 manual (PDF, 1458 pages) can be downloaded for free without registration. Check it out even if you don't use SICStus Prolog—yet;) It's that good! — repeat
Thanks much @repeat! I shall download the free manual.The ISO doc is a bit pricey. — lurker

Fatalize Fatalize · Accepted Answer · 2017-12-12T08:19:17

You should learn more about list notation: [A|[B|C]] can be written as [A,B|C] for example. It is now clearer that C is the tail of the list, and thus, is a list itself! Therefore, when you write sums([C], [F]), you are wrapping C and F into a list, even though they are already lists, which is your problem.

If we fix this and run your predicate, we get this:

?- sums([4,11,1,-3,8],Z).
Z = [4, 15, 1, -2, 8]

It is still wrong as you can see. The main problem is that, the recursive call sums in the third rule expresses that the prefix sums of the tail of a list are the tail of the prefix sums of the list, which is wrong because those prefix sums depend on the previous element!

To solve this, you need to introduce an extra argument to maintain the sum value throughout recursive calls:

:- use_module(library(clpfd)).

prefix_sums(L, D) :-
    prefix_sums(L, 0, D).

prefix_sums([], _, []).
prefix_sums([H|T], S, [S1|T2]) :-
    S1 #= H + S,
    prefix_sums(T, S1, T2).

Using library(clpfd), we get the behaviour we expect:

?- prefix_sums([4,11,1,-3,8],Z).
Z = [4, 15, 16, 13, 21].

But also the reverse behaviour:

?- prefix_sums(Z, [4,15,16,13,21]).
Z = [4, 11, 1, -3, 8].

And also correct behaviour with even less information:

?- prefix_sums([A,B,C],Z).
Z = [A, _7964, _7970],
B+A#=_7964,
C+_7964#=_7970.

?- prefix_sums(X,Z).
X = Z, Z = [] ;
X = Z, Z = [_7122],
_7122 in inf..sup ;
X = [_7452, _7458],
Z = [_7452, _7482],
_7458+_7452#=_7482 ;
X = [_7770, _7776, _7782],
Z = [_7770, _7806, _7812],
_7776+_7770#=_7806,
_7782+_7806#=_7812 ;
…

Prolog predicate that will check if a list A is a list of the prefix sums of a list D

2 Answers