Prolog: sum the elements of a list

Question

I am very new to prolog and I'm trying to sum the elements of a list. So far, I have this:

     sum([],_,_). %base case
     sum([H|T], Y, _X):-
        X2 is H + Y,
        sum(T,X2,X2).

testing with sum([1,2,3,4], 0, X) results in an error, but I'm not sure what's wrong with this code. Could someone point me in the right direction?

What error are you having, specifically? What error message? I'm not a Prolog expert by any means, but I think your base case is wrong (maybe it should be sum([E], _, _):- E. or sum([],_,_):- 0.). Your summation algorithm also seems to use an extra parameter, but you might have a reason for that which isn't clear from this code snippet. — Nic
What does the middle argument mean? Note that sum([], _, _). means that if the first argument is empty, then the 2nd and 3rd arguments can be anything you like and it is considered true (succeeds). — lurker
@NicHartley Close but no cigar, both your ideas should be something like sum([E], _, E). or sum([], _, 0) as Prolog does not have expression/return semantics. As lurker rightly points out, there's no clarity on what the middle argument is supposed to be for. — Daniel Lyons
@DanielLyons Well, like I said, I'm no Prolog expert -- I'm more used to similarly functional languages that do have return semantics. I assume that it should be sum([],_,R):- R is 0. , or something closer to that, then? Though that still feels like it's using an extra parameter. — Nic
@NicHartley it's a little risky in general to assume that one language has the same semantics as another, and it's particularly risky with Prolog which is declarative not imperative. is/2 is for numeric expression evaluation. So although R is 0 works, it's not really intended as an assignment statement. Prolog's basic powerful functionality involves unification and backtracking. Predicates do not return values but rather either succeed or fail. In this case, sum([], _, 0). would be succeeds if the 3rd argument successfully unifies with 0. — lurker

num1 num1 · Accepted Answer · 2018-07-03T18:20:10

The code you gave is closer to working than you probably think, but it has a couple problems.

For one, Prolog predicates aren't functions, they don't return results like functions in other languages do. Predicates, instead, declare something about what is true. Later you can give prolog queries and it'll try to make them true.

For example, calls to length/2 are true when the left argument is a list, and the right argument is an int with the length of the list:

?- length([1, 2, 3, 4], 4).
true.

?- length([1, 2, 3, 4], X).
X = 4.

?- length(X, 2).
X = [_2300, _2306].

Looking back at your first line:

sum([],_,_). %base case

This says "sum/3 is always true, as long as the first element is an empty list". You can test this:

?- sum([], -20, hello).
true.

That's probably not what you were intending.

I'm not sure how to put the rest of this without just giving away the answer, but look at what this clause is saying:

 sum([H|T], Y, _X):-
    X2 is H + Y,
    sum(T,X2,X2).

"sum([H|T], Y, WhoCaresIllNeverUseThisVariable) is true if we can recur and prove that sum(T, H+Y, H+Y) is true".

Well, one point, that last argument is a little weird, because in both clauses you assign it to an anonymous variable (_ and _X). What you're saying is, "the third argument never matters and should match literally anything the uses throws at it". I don't think that's what you mean to say.

Second point, I don't know if you realize it but, you're actually computing a sum here! While trying to make sum([1, 2, 3, 4], 0, X) true Prolog will traverse the list and add each element to the middle argument, your accumulator. The summing part works! What you're failing to do is extract the sum from this predicate.

Generally in Prolog you "return" results by making them an additional argument. You could look at length/2 this way. Here's a way you might write it yourself:

my_length([], 0).
my_length([_|Rest], Length) :-
  my_length(Rest, Length1),
  Length is Length1 + 1.

This function "returns" the length of the array by only being true when the second argument of the predicate is the length of the array.

Prolog: sum the elements of a list

1 Answers