Swapping consecutive items of a list in Prolog

Question

I'm trying to write Prolog code that can swap two elements of a list, but only if they are consecutive to each other. That is,

conseq_swap(d, e, [a, g, d, e, f], X).

should give:

X = [a, g, e, d, f].

(d and e are consecutive.)

However,

conseq_swap(a, e, [a, g, d, e, f], X).

should always fail (a and e are not consecutive.)

I can assume that an item appears in the list only once.

I have the following code, which is actually working fine:

swap_conseq(X, Y, MainList, SwappedList) :-
   indexOf(MainList, X, Xpos),
   indexOf(MainList, Y, Ypos),
   Diff is Ypos - Xpos,
   Diff is 1,
   Xpos < Ypos,
   swap_ordered(X, Y, Xpos, Ypos, MainList, SwappedList).

swap_conseq(X, Y, MainList, SwappedList) :-
   indexOf(MainList, X, Xpos),
   indexOf(MainList, Y, Ypos),
   Diff is Xpos - Ypos,
   Diff is 1,
   Ypos < Xpos,
   swap_ordered(Y, X, Ypos, Xpos, MainList, SwappedList).

swap_ordered(Min, Max, Minpos, Maxpos, MainList, SwappedList) :-
   compute_lists(MainList, Min, Minpos, Pre, _),
   compute_lists(MainList, Max, Maxpos, _, Post),
   append(Pre, [Max, Min], Temp),
   append(Temp, Post, SwappedList).

indexOf([Element|_], Element, 1):- !.
indexOf([_|Tail], Element, Index):-
   indexOf(Tail, Element, Index1),
   !,
   Index is Index1+1.

compute_lists(MainList, X, Xpos, A, B) :-
   L is Xpos - 1,
   append(A, [X | B], MainList),
   length(A, L).

However, just by looking at the code, I can tell that this is a horrible way to do this - repetitive, inefficient - something only a Prolog newbie like me could write.

Any suggestions on how to improve this would be greatly appreciated!

score 3 · Answer 1 · edited May 23 '17 at 12:05

Here's a logically pure implementation of conseq_swap/4:

conseq_swap(E1,E2,Xs,Ys) :-       % use aux predicate w/dif-argument-order
   list_item1_item2_swapped(Xs,E1,E2,Ys).

Compared to conseq_swap/4 the argument order of list_item1_item2_swapped/4 is altered, so first argument indexing is enabled. This can help prevent unneeded choice-points.

list_item1_item2_swapped([],_,_,[]).  
list_item1_item2_swapped([X|Xs],E1,E2,Ys) :-
   list_prev_item1_item2_swapped(Xs,X,E1,E2,Ys).

We thread an extra argument that refers to the previous list element through, employing a technique commonly called "lagging". To see another use of this technique in action, look at @mat's answer to some other question about implementing predicates on Prolog lists.

The actual relation is defined by list_prev_item1_item2_swapped/5:

list_prev_item1_item2_swapped([X|Xs],X0,X0,X,[X,X0|Xs]). % stop swapping
list_prev_item1_item2_swapped([X|Xs],X0,E1,E2,[X0|Ys]) :-
   dif(X0-X,E1-E2),               % state logically pure "not-equal"
   list_prev_item1_item2_swapped(Xs,X,E1,E2,Ys).

Done! Now let's run some queries with SWI-Prolog 7.1.37:

?- conseq_swap(a,e,[a,g,d,e,f],X).
false.                            % fails, as OP said it should

?- conseq_swap(d,e,[a,g,d,e,f],X).
X = [a,g,e,d,f] ;                 % succeeds, as OP said it should
false.

?- conseq_swap(d,e,[A,G,D,E,F],X), A=a,G=g,D=d,E=e,F=f.
A = a, G = g, D = d, E = e, F = f, X = [a,g,e,d,f] ;   % succeeds
false.

?- conseq_swap(d,e,[a,g,d,e,d,e,f],X).
X = [a,g,e,d,d,e,f] ;             % succeeds; only the 1st (d,e) pair is swapped
false.

Edit 2015-04-24

Here's a more direct, somewhat de-optimized variant of the code given before.

It is less efficient, but hopefully a bit easier to read by humans. As pure as the other variant.

conseq_swap(X0,X1,[X0,X1|Xs],[X1,X0|Xs]).
conseq_swap(E0,E1,[X0,X1|Xs],[X0|Ys]) :-
   dif(X0-X1,E0-E1),
   conseq_swap(E0,E1,[X1|Xs],Ys).

Same queries, same answers:

?- conseq_swap(a,e,[a,g,d,e,f],X).
false.

?- conseq_swap(d,e,[a,g,d,e,f],X).
X = [a,g,e,d,f] ;
false.

?- conseq_swap(d,e,[A,G,D,E,F],X), A=a,G=g,D=d,E=e,F=f.
A = a, G = g, D = d, E = e, F = f, X = [a,g,e,d,f] ;
false.

?- conseq_swap(d,e,[a,g,d,e,d,e,f],X).
X = [a,g,e,d,d,e,f] ;
false.

score 2 · Accepted Answer · edited May 23 '17 at 12:05

(Do read answers by repeat and Ludwig. Those are good answers)

Modified to remove both assumptions in old solution

conseq_swap(E1,E2,[E1,E2|R],[E2,E1|R]).
conseq_swap(E1,E2,[E2,E1|R],[E1,E2|R]).

conseq_swap(E1,E2,[A|RI],[A|RO]) :- conseq_swap(E1,E2,RI,RO).

Cuts ((!)/0) are removed.

?- conseq_swap(a,e,[a,g,d,e,f],X).
false.

?- conseq_swap(d,e,[a,g,d,e,f],X).
X = [a, g, e, d, f] ;
false.

?- conseq_swap(d,e,[D,A,G,E,F],X), A=a,G=g,D=d,E=e,F=f.
false.

?- conseq_swap(d,e,[A,G,D,E,F],X), A=a,G=g,D=d,E=e,F=f.
A = a,
G = g,
D = d,
E = e,
F = f,
X = [a, g, e, d, f] ;
false.

For the case where there are many possible pairs to swap, it output all ways of swapping only once. The question assumes that there can only be one pair anyway.

?- conseq_swap(d,e,[a,g,d,e,d,e,f],X).
X = [a, g, e, d, d, e, f] ;
X = [a, g, d, d, e, e, f] ;
X = [a, g, d, e, e, d, f] ;
false.

Modified to remove assumption 2

If you want the query conseq_swap(a, e, [a, g, d, e, f], X). to fail outright, remove the first two lines in the old solution, which allows the original list to end up as output when no swapping is performed.

Old solution (same output as the code in question)

This is the old solution written with the following assumptions:

The input does not contain any unbounded variable.
When no pair satisfying the condition is found, output the input list as-is, similar to what the code in the question does.

% Empty list gives empty list
conseq_swap(_,_,[],[]). 

% List with single element gives back the same list
conseq_swap(_,_,[A],[A]) :- !.

% If we found the 2 items that need to be swapped, we can swap them.
% We don't check for the rest of the list, due to the
% assumption.
% The cut at the end signals that the rule below do not need to be checked.
conseq_swap(E1,E2,[E1,E2|R],[E2,E1|R]) :- !.
conseq_swap(E1,E2,[E2,E1|R],[E1,E2|R]) :- !.

% We recursively check the rest of the list and append the result.
conseq_swap(E1,E2,[A|RI],[A|RO]) :- conseq_swap(E1,E2,RI,RO).

@repeat: Is there any drawback to using them? And if you have a better solution, why not post it? And if you don't want to post - please give me some idea how to improve it. — nhahtdh, Apr 24 '15 at 09:36
@repeat: Thanks. That is constructive criticism, compared to your first comment. For the case `?- conseq_swap(d,e,[A,G,D,E,F],X), A=a,G=g,D=d,E=e,F=f.`, I assume that the list is bounded - though it might be interesting to support it. For the second case, I agree that it is a bug. — nhahtdh, Apr 24 '15 at 10:05
@repeat: I realize that I implemented this based on OP's code, which actually return the original array on failure case. — nhahtdh, Apr 24 '15 at 10:19
These are good changes, making your code much more generally usable, more elegant and also easier to understand! +1! — mat, Apr 24 '15 at 14:03

score 2 · Answer 3 · answered Apr 24 '15 at 11:48

Another solution (in SWI-Prolog) would be:

conseq_swap(D, E, L, Z) :- 
            append([A,[D,E],B], L),
            append([A,[E,D],B], Z).

Same queries, same answers:

?- conseq_swap(a,e,[a,g,d,e,f],X).
false.

?- conseq_swap(d,e,[a,g,d,e,f],X).
X = [a, g, e, d, f] ;
false.

?- conseq_swap(d,e,[A,G,D,E,F],X), A=a,G=g,D=d,E=e,F=f.
A = a,
G = g,
D = d,
E = e,
F = f,
X = [a, g, e, d, f] ;
false.

?- conseq_swap(d,e,[a,g,d,e,d,e,f],X).
X = [a, g, e, d, d, e, f] ;
X = [a, g, d, e, e, d, f] ;
false.

(Sorry if I'm not able to write so much like "repeat", but I'm italian).

Thanks for value my solution. I want specify that my last comment was directed to other people, that could prefere to read more about this solution. It wasn't an attack to you! :) — Ludwig, Apr 24 '15 at 12:13

Swapping consecutive items of a list in Prolog

3 Answers3

Edit 2015-04-24

Modified to remove both assumptions in old solution

Modified to remove assumption 2

Old solution (same output as the code in question)

Linked