2

I'm having trouble figuring out how to find the sum of the integers that are in a list of pairs like so:

[[a, 1], [b, 2], [c, 3], [d, 4]]

I tried something like this, since it is reminiscent of a regular sum function:

sum([], 0).
sum([[_,Head]|[_,Tail]], Sum) :-
    sum([_,Tail], Sum2),
    Sum is Head+Sum2.

With the call being:

sum([[a, 1], [b, 2], [c, 3], [d, 4]], Total),
write('Sum = '), write(Total).

But that doesn't work. It prints out false, when it should print out the sum, which would be 10 here.

Kent
  • 21
  • 2
  • `sum([[_,Head]|[_,Tail]], Sum)` -> this says it only matches a list with two items, and nothing else. The entire tail section needs to be one name. This question was asked yesterday and has an answer here: https://stackoverflow.com/questions/55776612/prolog-how-to-sum-only-part-of-list-inside-another-list if an answer is what you're looking for. – TessellatingHeckler Apr 22 '19 at 06:06
  • The answerers are right: it's a good learning opportunity. But the simple answer is: you said [_,Tail] when you meant Tail. The rest of the list isn't 2 items to be called _ and Tail, but 3 items, best collectively called Tail. – Topological Sort Apr 22 '19 at 13:59

3 Answers3

1

I think it might help to split this into two tasks:

  1. create a new list of the second item of each sublist; and
  2. sum up that list.

This makes it easier to tackle the two problems, and furthermore you now have two extra predicates that can be used for other purposes.

We can obtain a list of the second item of the sublists with:

item2list([], []).
item2list([[_, X|_]|T], [X|T2]) :-
    item2list(T, T2).

or we can use maplist/3 [swi-doc] and nth1/3 [swi-doc]:

item2list(L1, L2) :-
    maplist(nth1(2), L1, L2).

or we can write item2list in terms of findall/3 [swi-doc] and member/2 [swi-doc]:

item2list(L1, L2) :-
    findall(X, member([_,X|_], L1), L2).

although here the predicate is not bidirectional.

For example:

?- item2list([[a, 1], [b, 2], [c, 3], [d, 4]], L).
L = [1, 2, 3, 4].

I leave summing up that list as an exercise.

Willem Van Onsem
  • 443,496
  • 30
  • 428
  • 555
  • `findall/3` + `member/2` will give you a notably faster implementation for your `item2list/2` predicate – Paulo Moura Apr 22 '19 at 11:42
  • But `findall/3` would mess with constraints. The `maplist/3` solution does not have this problem. – false Apr 22 '19 at 12:45
1

In your attempt to define the predicate sum/2, you're not handling the lists of lists correctly. Try:

sum(Lists, Sum) :-
    sum(Lists, 0, Sum).

sum([], Sum, Sum).
sum([[_,N]| Lists], Sum0, Sum) :-
    Sum1 is Sum0 + N,
    sum(Lists, Sum1, Sum).

This version uses an accumulator to enable a tail-recursive definition. Sample call:

| ?- sum([[a, 1], [b, 2], [c, 3], [d, 4]], Sum).

Sum = 10
yes
Paulo Moura
  • 18,373
  • 3
  • 23
  • 33
1

Whenever a goal fails that you expect to succeed, see this as an opportunity to learn (short form for logic earn = earn logic). After all, this is Prolog which was meant to mean Programming in Logic. So where is the logic in your program?

For the moment your program fails, but you expected it to succeed. Where is the culprit? Let's generalize your program such that the resulting program still fails, but is much smaller. There are two easy ways to generalize a program:

  • remove goals (by adding a prefix *)

  • remove terms (replacing term by _/*term*/

We can do this pretty blindly. No need to understand your program. Just recheck that the goal still fails. Here is what I came up with on my first try:

:- op(950, fy, *).
* _G_0. % ignore the argument _G_0

sum([], _/*0*/).
sum([_/*[_,Head]*/|[_,Tail]], Sum) :-
    * sum([_,Tail], Sum2),
    * Sum is Head+Sum2.

?- sum([_/*[a, 1]*/, _/*[b, 2]*/, _/*[c, 3]*/, _/*[d, 4]*/], Total).
   false.                            % gnah - still fails

One problem has to be in the remaining visible part. Too difficult to figure out? Let Prolog explain it to you by querying the most general query:

?- sum(Xs, Sum).
   Xs = []
;  Xs = [_A,_B,_C].

So only two lengths of lists are possible: The empty list and a list with three elements. Note that we have currently a generalized version of the predicate. So there is no guarantee that we will find solutions for both lengths. However, we can be 100% sure that for all other lengths there will be no solution.

Let's get back at the original program and ask the most general query:

?- sum(Os, Total).
   Os = [], Total = 0
;  false.

Oh no, there is a single solution only. And not even a single solution for sum([_|_], Total).

So let's generalize the program again but now with respect to this failing goal:

sum([], _/*0*/).
sum([_/*[_,Head]*/|[_,Tail|_/*[]*/]], Sum) :-
    sum([_,Tail], Sum2),
    * Sum is Head+Sum2.

?- Os = [_|_], sum(Os, Total).
   false.

In this part there must be a further error. And in fact, the goal sum([_,Tail], Sum2) is the culprit: It is about a list of exactly two elements, but the rule wants at least three

For the actual fixes, see the other answers.

This method works for pure, monotonic programs such as yours.

false
  • 10,264
  • 13
  • 101
  • 209