CODEWITHSUNDEEP
listprologswap
Rosangela Casolare
Rosangela Casolare

Reputation: 1

Prolog how to swap two by two elements in a list function?

I need a function in Prolog: swapcouple(L, L1).

swapcouple([a,b,c,d,e], M) --> output M=[b,a,d,c,e]

swapcouple([a,b,c,d], M) --> output M=[b,a,d,c]

Upvotes: 0

Views: 2611

Answers (2)

repeat
repeat

Reputation: 18726

The implementation can hardly get more direct than this:

list_swappedcouples([],[]).
list_swappedcouples([A],[A]).
list_swappedcouples([A,B|Xs],[B,A|Ys]) :-
   list_swappedcouples(Xs,Ys).

Here are your sample queries:

?- list_swappedcouples([a,b,c,d,e],Ls).
Ls = [b,a,d,c,e] ;                        % succeeds, but leaves behind choicepoint
false.

?- list_swappedcouples([a,b,c,d],Ls).
Ls = [b,a,d,c].                           % succeeds deterministically

Edit 2015-06-03

We can utilize first argument indexing to improve determinism.

list_with_swapped_couples([],[]).
list_with_swapped_couples([X|Xs],Ys) :-
   list_prev_w_swapped_couples(Xs,X,Ys).

list_prev_w_swapped_couples([],X,[X]).
list_prev_w_swapped_couples([X1|Xs],X0,[X1,X0|Ys]) :-
   list_with_swapped_couples(Xs,Ys).

Note that all following sample queries succeed deterministically.

?- list_with_swapped_couples([],Xs).
Xs = [].

?- list_with_swapped_couples([1],Xs).
Xs = [1].

?- list_with_swapped_couples([1,2],Xs).
Xs = [2,1].

?- list_with_swapped_couples([1,2,3],Xs).
Xs = [2,1,3].

?- list_with_swapped_couples([1,2,3,4],Xs).
Xs = [2,1,4,3].

?- list_with_swapped_couples([1,2,3,4,5],Xs).
Xs = [2,1,4,3,5].

Upvotes: 1

Will Ness
Will Ness

Reputation: 71065

(what have you tried?) This is a valid definition:

swapcouple([a,b,c,d,e], M) :- M=[b,a,d,c,e].    
swapcouple([a,b,c,d], M) :- M=[b,a,d,c].

Proceed by abstraction. For example,

swapcouple([A,B,C,D,E], M) :- M=[B,A,D,C,E].    
swapcouple([A,B,C,D], M) :- M=[B,A,D,C].

Do you see where I'm going? [A,B,C,D,E] = [A,B | R] where R = [C,D,E]. Can we use that?

swapcouple([A,B|R], M) :- R=[C,D,E], M=[B,A|S], S=[D,C,E].

Right? Here's the crucial bit. R=[C,D,E], S=[D,C,E] is the same as swapcouple(R,S), isn't it?

swapcouple([A,B|R], M) :- M=[B,A|S], swapcouple(R,S).

Assuming that swapcouple does what it is advertised to do, we can just use it when the need arises. Here you've got your very own recursive procedure (well, predicate). It is even tail recursive modulo cons, which is even more hip and fun.

Few more edge cases are missing there. I'm positive you can finish it up.

Upvotes: 2

Related Questions