在 Prolog 中交换列表的连续项

我正在尝试编写可以交换列表中两个元素的 Prolog 代码，但前提是它们是彼此连续。那是，

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

应该给出：

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

（d 和 e 是连续的。）

However,

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

应该总是失败（a 和 e 不连续。）

我可以假设某个项目仅在列表中出现一次。

我有以下代码，实际上运行良好：

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

然而，只要看看代码，我就知道这是一种可怕的方法——重复、低效——只有像我这样的 Prolog 新手才能写出来。

任何有关如何改进这一点的建议将不胜感激！

这是一个逻辑纯粹实施conseq_swap/4:

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

相比conseq_swap/4的参数顺序list_item1_item2_swapped/4被改变，所以第一个参数索引 http://www.swi-prolog.org/pldoc/man?section=jitindex已启用。这可以帮助防止不必要的选择点。

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

我们使用一种通常称为的技术来线程化一个额外的参数，该参数引用前一个列表元素“滞后”。要查看此技术的另一种实际应用，请查看@mat的回答 https://stackoverflow.com/a/3966139/4609915对某些人其他问题 https://stackoverflow.com/questions/3965054/prolog-find-minimum-in-a-list关于在 Prolog 列表上实现谓词。

实际关系定义为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).

完毕！现在让我们运行一些查询SWI-Prolog http://www.swi-prolog.org/ 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.

编辑2015-04-24

这是之前给出的代码的更直接、稍微优化的变体。

It is效率较低，但希望有一点更容易被人类阅读。 与其他变体一样纯净。

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查询，same答案：

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