1

Suppose, I wanted to write a program in prolog, which accepts a number input X, and outputs all value pairs for which the sum is X.

some_pred(X,X1,X2) :-
    X1 + X2 = X.

This does not work, because X1 + X2 is not evaluated arithmetically.

some_pred(X,X1,X2) :-
    Xtemp is X1 + X2,
    Xtemp = X.

The other option I have also doesn't work, because X1 and X2 are not instantiated. How would someone solve this?

false
  • 10,264
  • 13
  • 101
  • 209
Morpheus
  • 11
  • 1

2 Answers2

2

Yes, unification doesn't evaluate arithmetic expressions, and if it did that wouldn't help you because X1 and X2 are undefined so adding them together is meaningless.

You need either to write a search yourself such as a brute force nested loop:

sum_a_b(X, A, B) :-
    between(1, X, A),
    between(1, X, B),
    X is A + B.

Or a more nuanced one where you encode something about arithmetic into it, start with 1+(X-1) and then (2+X-2), etc:

sum_a_b(X, A, B) :-
    between(0, X, A),
    B is X - A.

Or more generally, learn about clpfd (link1, link2) which can do arithmetic evaluating and solving for missing variables in equations, as well as searching through finite domains of possible values:

:- use_module(library(clpfd)).

sum_a_b(X, A, B) :-
    [A, B] ins 1..X,
    X #= A + B.

? sum_a_b(5, A, B), label([A, B]).
A = 1,
B = 4 ;

A = 2,
B = 3 ;

...

NB. I'm assuming positive integers, otherwise with negatives and decimals you'll get infinite pairs which sum to any given X.

TessellatingHeckler
  • 27,511
  • 4
  • 48
  • 87
  • 1
    Why `[A, B] ins 1..X`? This constrains the usage to a given `X`. – false Jan 24 '23 at 14:47
  • 2
    @false because clpfd requires finite domains and I want OP to see some integer answers instead of returned constraints, there isn't likely to be an answer in the billions + billions = 5 region. OP asked for an answer with a given X. As far as I can tell "the most general query" is basically never of any interest to me; "all things which could be a CSV line", "all numbers and all the pairs which add up to them" are too many things to ever want to ask about. – TessellatingHeckler Jan 24 '23 at 17:08
  • 3
    *"the most general query" is basically never of any interest to me* It is in case you try to debug a program. It isn't for the final program. – false Jan 24 '23 at 17:13
0

Here's something very similar, using a list:

pos_ints_sum(Sum, L) :-
    compare(C, Sum, 1),
    pos_ints_sum_(C, L, Sum).

% 0 means the list has ended
pos_ints_sum_(<, [], 0).
% 1 means there is only 1 possible choice
pos_ints_sum_(=, [1], 1).
pos_ints_sum_(>, [I|T], Sum) :-
    % Choose a number within the range
    between(1, Sum, I),
    % Loop with the remainder
    Sum0 is Sum - I,
    pos_ints_sum(Sum0, T).

Result in swi-prolog:

?- pos_ints_sum(5, L).
L = [1, 1, 1, 1, 1] ;
L = [1, 1, 1, 2] ;
L = [1, 1, 2, 1] ;
L = [1, 1, 3] ;
L = [1, 2, 1, 1] ;
L = [1, 2, 2] ;
L = [1, 3, 1] ;
L = [1, 4] ;
L = [2, 1, 1, 1] ;
L = [2, 1, 2] ;
L = [2, 2, 1] ;
L = [2, 3] ;
L = [3, 1, 1] ;
L = [3, 2] ;
L = [4, 1] ;
L = [5].

Note: X is a poor choice of variable name, when e.g. Sum can easily be used instead, which has far more meaning.

brebs
  • 3,462
  • 2
  • 3
  • 12