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!

Answer 1

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.

Answer 2

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).

Answer 3

(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:

1. The input does not contain any unbounded variable.
2. 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).