How to describe what conditions are to be met, and if they aren't, keep going through a list

Question

So I would like to know what would be a declarative way of looking at this specific part of a problem I'm trying to solve:

% create_arcs(CONNECTIONS_IN, NODES_IN, ARCS_OUT).  
% Create arcs - makes a list of arcs(NODE_ID_1, NODE_ID_2)...
create_arcs([], _, _).
create_arcs([A-B | T], [H|NODES], LISTARCS) :-
    ensure_arcs(A,B,H, LISTARCS, LISTARCS2),
    create_arcs(T, NODES, LISTARCS2).

%ensure_arcs(NODE_A, NODE_B, NODELIST, LISTARCSIN, LISTARCSOUT)
%builds a list of arcs TODO works WRONG when arc already was in the input. It should fail, but it just checks that is a member and moves on. So basically it works when arcs are new, because they are added properly, but not when arcs were already found (and as per the exercise it should fail and try another permutation).
ensure_arcs(A,B,NODES, LISTARCSIN, LISTARCSIN):-
    member(enum(NODE_ID_A, A), NODES),
    member(enum(NODE_ID_B, B), NODES),
    REMAINDER is abs(NODE_ID_A-NODE_ID_B),
    member(enum(REMAINDER,_), LISTARCSIN), !.

ensure_arcs(A,B,NODES, LISTARCSIN,[enum(REMAINDER, A-B) | LISTARCSIN]):-
    member(enum(NODE_ID_A, A), NODES),
    member(enum(NODE_ID_B, B), NODES),
    REMAINDER is abs(NODE_ID_A-NODE_ID_B).

The idea here, if I were able to get this right, is to define the conditions that have to be satisfied and if they aren't, keep travelling the input list.

So, trying to explain myself properly, the idea is, if it does not meet every condition, it should fail and keep traveling the list. If it fails, it should return successfully. How far off I am? Is this still an imperative way of looking at things?

I need to know how would I go to travel the list when the conditions are not met, and if they are not, try another option; otherwise if they are met, stop travelling.

Second edit:

So I changed code a bit, but I don't see maplist(dif(enum(REMAINDER,_)), ListArcsInput), ever saying "no" so it's very confusing. It should fail if what I put inside the dif/2 is already in the ListArcsInput, right??

Code for reference:

pairs_nodes_arcs(_, [],_).
pairs_nodes_arcs([], _, _).
pairs_nodes_arcs([A-B | T], [H|NODES], LISTARCS) :-
    member(enum(NODE_ID_A, A), H),
    member(enum(NODE_ID_B, B), H),
    REMAINDER is abs(NODE_ID_A-NODE_ID_B),
    arcs_are_repeated([A-B | T], [H|NODES], REMAINDER,LISTARCS).
    %maplist(dif(enum(REMAINDER,_)), LISTARCSIN),


    %pairs_nodes_arcs(T, [H|NODES], LISTARCS2),
    %pairs_nodes_arcs([A-B | T], NODES, []).

arcs_are_repeated([A-B | T],[H|NODES],REMAINDER,ListArcsInput):-
    maplist(dif(enum(REMAINDER,_)), ListArcsInput),
    pairs_nodes_arcs(T, [H|NODES], [enum(REMAINDER, A-B) | ListArcsInput]).

arcs_are_repeated([A-B | T],[H|NODES],ElementoListaArcos,ListArcsInput):-
    pairs_nodes_arcs([A-B | T], NODES, []).

And trace:

Call:'__aux_maplist/2_dif+1'([enum(1, a-b)], enum(1, _G3643))
 Call:dif:dif(enum(1, _G3643), enum(1, a-b))
 Exit:dif:dif(enum(1, _G3677), enum(1, a-b))
 Call:'__aux_maplist/2_dif+1'([], enum(1, _G3677))
 Exit:'__aux_maplist/2_dif+1'([], enum(1, _G3677))
 Exit:'__aux_maplist/2_dif+1'([enum(1, a-b)], enum(1, _G3677))
 Call:create_arcs([], [[enum(1, a), enum(2, b), enum(3, c)], [enum(1, a), enum(3, c), enum(2, b)], [enum(2, b), enum(1, a), enum(3, c)], [enum(2, b), enum(3, c), enum(1, a)], [enum(3, c), enum(1, a), enum(2, b)], [enum(3, c), enum(2, b), enum(1, a)]], [enum(1, b-c), enum(1, a-b)])
 Exit:create_arcs([], [[enum(1, a), enum(2, b), enum(3, c)], [enum(1, a), enum(3, c), enum(2, b)], [enum(2, b), enum(1, a), enum(3, c)], [enum(2, b), enum(3, c), enum(1, a)], [enum(3, c), enum(1, a), enum(2, b)], [enum(3, c), enum(2, b), enum(1, a)]], [enum(1, b-c), enum(1, a-b)])

I couldn't get maplist to work but I could get dif, so I'm traveling "by hand" the list, that meaning I do myself and compare with dif every element. Seems to be working so far?

---

Edit: This is the trace that I obtain as of right now with all my code, in which, what I would like is, if the follow case happens, it should NOT take/accept/keep with the current "branch" and since it did find something "twice" in the output list, it should skip, backtrack, and try another possibility.

Call:create_arcs([b-c], [[enum(1, a), enum(2, b), enum(3, c)], [enum(1, a), enum(3, c), enum(2, b)], [enum(2, b), enum(1, a), enum(3, c)], [enum(2, b), enum(3, c), enum(1, a)], [enum(3, c), enum(1, a), enum(2, b)], [enum(3, c), enum(2, b), enum(1, a)]], [enum(1, a-b)])
 Call:ensure_arcs(b, c, [enum(1, a), enum(2, b), enum(3, c)], [enum(1, a-b)], _G3600)
 Call:lists:member(enum(_G3555, b), [enum(1, a), enum(2, b), enum(3, c)])
 Exit:lists:member(enum(2, b), [enum(1, a), enum(2, b), enum(3, c)])
 Call:lists:member(enum(_G3558, c), [enum(1, a), enum(2, b), enum(3, c)])
 Exit:lists:member(enum(3, c), [enum(1, a), enum(2, b), enum(3, c)])
 Call:_G3607 is abs(2-3)
 Exit:1 is abs(2-3)


 Call:lists:member(enum(1, _G3567), [enum(1, a-b)])
 Exit:lists:member(enum(1, a-b), [enum(1, a-b)])

So that two lines, when there was nothing on the list, or there is, but it does not match, works properly: it goes to my other definition of ensure_arcs, and adds it to the output list. Now I want to, if there IS a matching member, to fail, or backtrack, or whatever. Doing it forcefully seems wrong (I'm sure there has to be some kind of halt or FAIL or whatever, but I would like to know how to program it so that, if it DOES match, to let it know it is not an accepted answer).

Answer 1

It seems that you are already very close to the solution.

I have the following suggestions to make your predicate more declarative, that is, as you correctly say, describe what holds.

My first suggestion is about names of your predicates. For good declarative names, choose nouns and adjectives, and avoid imperatives. This is because nice relational predicates can be used in all directions, whereas an imperative always suggests a particular directions or mode of use.

For example, instead of create_arcs/3, a more descriptive and declarative name would be: pairs_nodes_arcs/3. This correctly suggests that you can use this predicate also for example if the arcs are already specified.

My second suggestion is about actually carrying out the implied generality by using general relations throughout your program. In your specific case, check out your Prolog system's CLP(FD) constraints and replace low-level arithmetic predicates over integers with the CLP(FD) constraints (#=)/2 and others. These relations are reversible and yield much more general programs in addition to preserving your program's performance in cases that can be handled by lower-level arithmetic.

Third, retain the achieved generality by avoiding !/0 and related non-monotonic predicates. In your case, you are already quite close to this desirable state. Simply remove the single occurrence of !/0 to obtain all solutions. (Using !/0 impurely cuts away candidates that you may need on backtracking.)

By honoring these principles, you will obtain a quite general program that lets you:

• test given solutions
• complete partially instantiated solutions
• generate all solutions.

All of this follows naturally from a single declarative specification of what a solutions looks like.

Note that Prolog will automatically go through all possibilities until it finds a solution that satisfies all constraints. Focus on a clear description of the properties that must be met. It is not necessary to describe what isn't a solution.

EDIT: There is of course a way to cause the current branch of the computation to fail. All it takes is to post a goal that is clearly false. The aptly named built-in predicate false/0 does this, and so does any other goal that certainly does not hold, such as for example 0=1.

However, a much cleaner approch in your case is to explicitly state what must hold for a solution. In your case, it seems to be necessary to talk about terms or integers that are different. To denote that arbitrary terms are different, use the dif/2 predicate, see prolog-dif. As you are reasoning over integers, you can also use the clpfd constraints (#\=)/2 or all_distinct/1 to state this.

For example, to state that a relation only holds if enum(R,_) does not occur in Ls, use:

maplist(dif(enum(R,_)), Ls)

This is only true if, for each L in Ls, dif(enum(R,_), L) is true.

Use this to declaratively express that a term does not occur in a list. Note: This will retain the relational nature of your program. For example, it will work also if the term is (only or even, depending on how you look at it) partially instantiated.

I leave the more specific case of using CLP(FD) constraints (instead of dif/2, which does not take into account domain-specific knowledge about integers) as an easy exercise.