Prolog的替代(Prolog substitution)

2019-08-18 01:16发布

站内文章 / 前沿技术

66 0

闹够了就滚

女 | 书童

私信

我怎么可以用所包含将被替换的变量另一个列表清单。例如

rep([x, d, e, z, x, z, p], [x=z, z=x, d=c], R).
R = [z, c, e, x, z, x, p]

在X到Z和Z之后，它不会改变已经被更换。

到目前为止，我只做了一个没有列表

rep([], _, []).
rep(L1, H1=H2, L2) :-
   rep(L1, H1, H2, L2).

rep([],_,_,[]).
rep([H|T], X1, X2, [X2|L]) :-
   H=X1,
   rep(T,X1,X2,L),
   !.
rep([H|T],X1,X2,[H|L]) :-
   rep(T,X1,X2,L).

Answer 1:

我觉得你的代码比较混乱。首先，你必须rep/3和rep/4 ，但他们都没有在你传递变量绑定列表中的第二位置的列表。 H1=H2不可能匹配列表，这是唯一的rep/3条款，检查第二个参数。如果这是一个课堂作业，看起来你有点落后，我建议你花一些时间对以前的材料。

解决的办法是比你想象的简单：

rep([], _, []).
rep([X|Xs], Vars, [Y|Rest]) :-    member(X=Y, Vars), rep(Xs, Vars, Rest).
rep([X|Xs], Vars, [X|Rest]) :- \+ member(X=_, Vars), rep(Xs, Vars, Rest).

我们使用member/2找到列表中的“变量绑定”（加引号是因为这是原子，而不是真正的Prolog的变量）。如果它在列表中，Y是更换，否则我们继续使用X.你瞧，这有预期的效果：

?- rep([x, d, e, z, x, z, p], [x=z, z=x, d=c], R).
R = [z, c, e, x, z, x, p] ;
false.

这可以通过使用“或”直接（拯救我们一个选择点）进行某种程度上更高效的：

rep([], _, []).
rep([X|Xs], Vars, [Y|Ys]) :- 
  (member(X=Y, Vars), ! ; X=Y), 
  rep(Xs, Vars, Ys).

看到：

?- rep([x, d, e, z, x, z, p], [x=z, z=x, d=c], R).
R = [z, c, e, x, z, x, p].

Answer 2:

如果您使用SWI-Prolog的，与模块lambda.pl在那里发现： http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/lambda.pl你可以这样写：

:- use_module(library(lambda)).

rep(L, Rep, New_L) :-
    maplist(\X^Y^(member(X=Z, Rep)
              ->  Y = Z
              ;   Y = X), L, New_L).

Answer 3:

你应该试图保持的代码比可能更简单：

rep([], _, []).
rep([X|Xs], Vs, [Y|Ys]) :-
   ( memberchk(X=V, Vs) -> Y = V ; Y = X ),
   rep(Xs, Vs, Ys).

当然，要注意（直通memberchk / 2）的习惯的方法来检查一个变量的值。

仍然还是在一个更地道的方式做：将列出这几种语言的一个基本组成部分和前导也不例外：

rep(Xs, Vs, Ys) :- maplist(repv(Vs), Xs, Ys).
repv(Vs, X, Y) :- memberchk(X=V, Vs) -> Y = V ; Y = X .

Answer 4:

这里是你如何可以继续使用if_/3和(=)/3 。

首先，我们试图找到一个Key成对列表KV 。一个额外的参数具体化搜索的成功。

pairs_key_firstvalue_t([]       ,_  ,_    ,false).
pairs_key_firstvalue_t([K-V|KVs],Key,Value,Truth) :-
   if_(K=Key,
       (V=Value, Truth=true),
       pairs_key_firstvalue_t(KVs,Key,Value,Truth)).

接下来，我们需要处理“未找到”的情况：

assoc_key_mapped(Assoc,Key,Value) :-
   if_(pairs_key_firstvalue_t(Assoc,Key,Value),
       true,
       Key=Value).

最后，我们把它放在一起使用元谓词 maplist/3 ：

?- maplist(assoc_key_mapped([x-z,z-x,d-c]), [x,d,e,z,a,z,p], Rs).
Rs = [z,c,e,x,a,x,p].                       % OK, succeeds deterministically

Answer 5:

让我们改善这个答案通过移动“递归部分”成元谓词 find_first_in_t/4 ：

:- meta_predicate find_first_in_t(2,?,?,?).
find_first_in_t(P_2,X,Xs,Truth) :-
   list_first_suchthat_t(Xs,X,P_2,Truth).

list_first_suchthat_t([]    ,_, _ ,false).
list_first_suchthat_t([E|Es],X,P_2,Truth) :-
   if_(call(P_2,E),
       (E=X,Truth=true),
       list_first_suchthat_t(Es,X,P_2,Truth)).

为了填补“缺失的点点滴滴”，我们定义key_pair_t/3 ：

key_pair_t(Key,K-_,Truth) :-
   =(Key,K,Truth).

基于find_first_in_t/4和key_pair_t/3 ，我们可以写assoc_key_mapped/3是这样的：

assoc_key_mapped(Assoc,Key,Value) :-
   if_(find_first_in_t(key_pair_t(Key),_-Value,Assoc),
       true,
       Key=Value).

那么，根据OP的用例仍然有效？

?- maplist(assoc_key_mapped([x-z,z-x,d-c]), [x,d,e,z,a,z,p], Rs).
Rs = [z,c,e,x,a,x,p].                            % OK. same result as before

在建筑find_first_in_t/4

memberd_t(X,Xs,Truth) :-                        % memberd_t/3
   find_first_in_t(=(X),_,Xs,Truth).

:- meta_predicate exists_in_t(2,?,?).           % exists_in_t/3
exists_in_t(P_2,Xs,Truth) :-
   find_first_in_t(P_2,_,Xs,Truth).