Prolog: How can I implement the sum of squares of two largest numbers out of three?

Question

Exercise 1.3 of the book Structure and Interpretation of Computer Programs asks the following:

Define a procedure that takes three numbers as arguments and returns the sum of the squares of the two larger numbers.

I'm learning Prolog. Here's the function I tried to implement:

square(X, Y) :- Y is X * X.
squareTwoLargest(X, Y, Z, R) :- 
    R is square(L1) + square(L2), L1 = max(X, Y), L2 = max(min(X, Y), Z).

However, when I run it, it gives the following error: ERROR: is/2: Arguments are not sufficiently instantiated. I think I'm not only not getting Prolog's syntax, but I'm also not getting the logic programming paradigm yet. So, how could I implement this function in good logic programming style?

The is/2 operator requires that the second argument be fully instantiated. Also, Prolog has predicates, not functions. A predicate succeeds or fails (or fails to terminate :)) and does not "return" a value. It can, however instantiate arguments. So your use of square won't work. Your use of min(X, Y) will also be problematic. — lurker
@lurker So, I would have to actually write R is L1 * L1 + L2 * L2? — Marcus Vinícius Monteiro

repeat repeat · Accepted Answer · 2015-04-14T09:13:55

To get the two largest numbers out of three (V1, V2, and V3) you can proceed as follows: Sort the list [V1,V2,V3] and take the last two list items [_,X,Y], square and sum them.

:- use_module(library(lists)).
:- use_module(library(clpfd)).

squareTwoLargest(V1,V2,V3, R) :- 
    Zs = [_,X,Y],
    chain(Zs, #=<),
    permutation([V1,V2,V3],Zs),
    R #= X*X + Y*Y.

Sample query:

?- squareTwoLargest(20,30,10, R).
R = 1300

Better implementation

Above code is based on "permutation sort", which makes it inefficient in more than one way.

The goal squareTwoLargest(X,Y,Z, R) succeeds multiple times and gives redundant answers, if two or more of X, Y, and Z are equal. This is shown by the following two queries:

?- squareTwoLargest(0,10,10, R).
R = 200 ;
R = 200 ;
false.

?- squareTwoLargest(10,10,10, R).
R = 200 ;
R = 200 ;
R = 200 ;
R = 200 ;
R = 200 ;
R = 200 ;
false.

We can eliminate the redundant answers by using a sorting network of size 3. For details, look at this answer to the question ordering lists with constraint logic programming.

list_sorted__SN3([A0,A1,A2], [D0,D1,C2]) :-
    B1 #= min(A1,A2),   B2 #= max(A1,A2),
    C0 #= min(A0,B2),   C2 #= max(A0,B2),
    D0 #= min(C0,B1),   D1 #= max(C0,B1).

squareTwoLargest__SN(V1,V2,V3, R) :-
    list_sorted__SN3([V1,V2,V3],[_,X,Y]),
    R #= X*X + Y*Y.

Consider the following queries:

?- squareTwoLargest__SN(20,30,10, R).
R = 1300.                              % works like it did before

?- squareTwoLargest__SN(20,20,10, R).
R = 800.                               % succeeds deterministically

?- squareTwoLargest__SN(20,20,20, R).
R = 800.                               % succeeds deterministically

Note that all redundant answers of the corner cases shown above have been eliminated.

Prolog: How can I implement the sum of squares of two largest numbers out of three?

3 Answers

Better implementation