Recursion problem in Prolog - getting False instead of True when going out of recursion

Question

I am trying to do a simple program in Prolog that would decide if the predicate is True or False. Basically I solved the problem, but I found one input that does not work. I know why but I have no idea how to solve it.

The predicate is in this form:

getPred(L, A, B, Y)

L - is a list containing intv predicates - intv(K,L,V) - < K,L > is interval and V is any value

< A,B > - is an interval

Y - value

The task is:

If < K,L > is in < A,B > add V to a sum. If it does not belong to < A,B >, ignore it.  
Finally, compare the sum of correct V values with Y. If it is equal - True, otherwise False.

Here is the example of correct TRUE predicates:

getPred([intv(2,10,15),intv(5,8,23), intv(12,15,8), intv(14,17,13)], 3, 16, 31).
getPred([intv(2,10,15),intv(5,8,23), intv(12,15,8), intv(14,17,13)], 3, 20, 44).

My code is:

getPred(List, A, B, Y) :-
    S is 0,
    program(List, A, B, Y, S).

program([], _, _, Y, S) :-
    S =:= Y.

program([intv(K,L,V)|P], A, B, Y, S) :-
    isinINTV(K, L, V, A, B, P, Y, S).

isinINTV(K, L, V, A, B, P, Y, S) :-
    K >= A,
    L =< B,
    S2 = S+V,
    program(P,A,B,Y,S2).

isinINTV(K, L, V, A, B, P, Y, S) :-
    program(P,A,B,Y,S).

My program worked perfectly unless I tried this predicate getPred([intv(2,10,10),intv(5,8,10)], 1, 20, 10).

The problem is that when Y != S, the recursion is going back and asks the same condition again but later Y == S because going back in recursion means that there is an old value in S.

Thank you for help. Important thing: I do not want to use any built-in predicates.

Change S2 = S+V to S2 is S+V. Don't confuse term unification (=/2) with arithmetic evaluation (is/2). — Paulo Moura
"Important thing: I do not want to use any built-in predicates." >=/2, =</2, =:=/2, and is/2 are built-in predicates. — Paulo Moura
I know. I meant predicates except these that I used already. I mean, I can use "relational operators". Anyway can you help me with the problem, please? — ofun

Paulo Moura Paulo Moura · Accepted Answer · 2020-04-08T15:43:09

Try:

check(Intervals, Inf, Sup, Value) :-
    check(Intervals, Inf, Sup, 0, Sum),
    Sum =:= Value.

check([], _, _, Sum, Sum).
check([intv(Inf0,Sup0,Value)| Intvs], Inf, Sup, Sum0, Sum) :-
    (   Inf0 >= Inf,
        Sup0 =< Sup ->
        Sum1 is Sum0 + Value,
        check(Intvs, Inf, Sup, Sum1, Sum)
    ;   check(Intvs, Inf, Sup, Sum0, Sum)
    ).

Some renaming for easier reading of the code. Sample calls:

| ?- check([intv(2,10,15),intv(5,8,23), intv(12,15,8), intv(14,17,13)], 3, 16, 31).
yes

| ?- check([intv(2,10,15),intv(5,8,23), intv(12,15,8), intv(14,17,13)], 3, 20, 44).
yes

| ?- check([intv(2,10,10),intv(5,8,10)], 1, 20, 10).
no

Notice that this solution also avoids the spurious choice points in your original code.

Recursion problem in Prolog - getting False instead of True when going out of recursion

1 Answers