5

我有一个列表[a, b, a, a, a, c, c] ，我需要在每个元素中再添加两次。

最终结果应如下所示：

[a, a, a, b, b, b, a, a, a, a, a, c, c, c, c]

如果我在列表中有一个与下一个项目相同的项目，那么它会一直运行直到有一个新项目，当它找到新项目时，它会添加上一个项目的两次出现然后继续。

到目前为止，这是我的代码，但我不知道如何添加两个......

dbl([], []).
dbl([X], [X,X]).
dbl([H|T], [H,H|T], [H,H|R]) :- dbl(T, R).
4

4 回答 4

7

您的代码看起来有点奇怪，因为最后一条规则需要三个参数。您只调用二进制版本，因此没有递归会尝试派生它。

您已经有了一个好主意来查看列表中元素发生变化的部分。所以有4种情况：

1) 你的清单是空的。2）你只有一个元素。3）您的列表以两个相等的元素开始。4）您的列表以两个不同的元素开始。

没有指定案例 1，因此您可能需要为此找到一个明智的选择。案例 2 与案例 4 有点相似，因为列表的末尾可以看作是元素的变化，您需要附加两个副本，然后就完成了。案例 3 非常简单，我们可以只保留元素并递归其余元素。案例 4 是您需要再次插入两个副本的地方。

这意味着您的代码将如下所示：

% Case 1
dbl([],[]).
% Case 2
dbl([X],[X,X,X]).
% Case 3
dbl([X,X|Xs], [X|Ys]) :-
   % [...] recursion skipping the leading X
% Case 4
dbl([X,Y|Xs], [X,X,X|Ys]) :-
   dif(X,Y),
   % [...] we inserted the copies, so recursion on [Y|Xs] and Ys

案例 3 应该很容易完成，我们只需从两个列表中删除第一个 X 并递归 dbl([X|Xs],Ys)。请注意，我们通过两次写入相同的变量来隐式地使前两个元素相等（即我们统一它们）。

如果您查看案例4的头部，您可以直接模仿您描述的模式：假设列表以X开头，然后是Y并且它们不同（dif（X，Y）），X重复3次而不是仅仅复制，然后我们继续对从 Y 开始的其余部分进行递归：dbl([Y|Xs],Ys)。

所以让我们试试谓词：

?- dbl([a,b,a,a,a,c,c],[a,a,a,b,b,b,a,a,a,a,a,c,c,c,c]).
true ;
false.

我们的测试用例被接受（真），我们没有找到一个以上的解决方案（假）。让我们看看我们是否找到了错误的解决方案：

?- dif(Xs,[a,a,a,b,b,b,a,a,a,a,a,c,c,c,c]), dbl([a,b,a,a,a,c,c],Xs).
false.

不，那也很好。如果我们的列表中有变量会发生什么？

?- dbl([a,X,a],Ys).
X = a,
Ys = [a, a, a, a, a] ;
Ys = [a, a, a, X, X, X, a, a, a],
dif(X, a),
dif(X, a) ;
false.

要么 X = a，则 Ys 是 5 as 的单次运行；或者 X 不等于 a，那么我们需要在所有三个运行中附加副本。看起来也不错。(*)

现在让我们看看，如果我们只指定解决方案会发生什么：

?- dbl(X,[a,a,a,b,b]).
false.

对，只有两个 bs 的列表不可能是我们规范的结果。所以让我们尝试添加一个：

?- dbl(X,[a,a,a,b,b,b]).
X = [a, b] ;
false.

万岁，它成功了！所以让我们作为最后一个测试看看会发生什么，如果我们只用两个变量调用我们的谓词：

?- dbl(Xs,Ys).
Xs = Ys, Ys = [] ;
Xs = [_G15],
Ys = [_G15, _G15, _G15] ;
Xs = [_G15, _G15],
Ys = [_G15, _G15, _G15, _G15] ;
Xs = [_G15, _G15, _G15],
Ys = [_G15, _G15, _G15, _G15, _G15] ;
Xs = [_G15, _G15, _G15, _G15],
Ys = [_G15, _G15, _G15, _G15, _G15, _G15] ;
[...]

似乎我们得到了正确的答案，但我们只看到单次运行的案例。这是prolog的搜索策略的结果（我不会在这里解释）。但是，如果我们在生成较长的列表之前先查看较短的列表，我们可以看到所有解决方案：

 ?- length(Xs,_), dbl(Xs,Ys).
Xs = Ys, Ys = [] ;
Xs = [_G16],
Ys = [_G16, _G16, _G16] ;
Xs = [_G16, _G16],
Ys = [_G16, _G16, _G16, _G16] ;
Xs = [_G86, _G89],
Ys = [_G86, _G86, _G86, _G89, _G89, _G89],
dif(_G86, _G89) ;
Xs = [_G16, _G16, _G16],
Ys = [_G16, _G16, _G16, _G16, _G16] ;
Xs = [_G188, _G188, _G194],
Ys = [_G188, _G188, _G188, _G188, _G194, _G194, _G194],
dif(_G188, _G194) ;
[...]

所以看起来我们有一个有效的谓词（**），假设你从文本中填写了缺失的目标:)

(*) 这里要说明一下：这种情况只有效，因为我们使用的是 diff。第一个具有相等性的谓词，通常遇到的是 =、== 和它们各自的否定 \= 和 \==。= 代表可统一性（在参数 st 中替换变量它们变得相等）， == 代表句法相等（术语完全相等）。例如：

?- f(X) = f(a).
X = a.

?- f(X) \= f(a).
false.

?- f(X) == f(a).
false.

?- f(X) \== f(a).
true.

这意味着，如果我们用 a 代替 X，我们可以使 f(X) 等于 f(a)。这意味着如果我们问它们是否不能相等（\=），我们会得到错误的答案。另一方面，这两个项不相等，所以 == 返回 false，它的否定 \== 返回 true。

这也意味着 X \== Y 总是正确的，所以我们不能在我们的代码中使用 \==。与此相反，dif 等待直到它可以决定它的参数是否相等。如果在找到答案后仍未决定，则打印“dif(X,a)”语句。

(**) 最后一句话：还有一个带有 if-then-else 构造的解决方案 (test ->goals_if_true;goals_if_false，它合并了案例 3​​ 和 4。由于我更喜欢​​这个解决方案，您可能需要查看其他版本自己。

于 2013-12-22T01:19:11.520 回答
4

当我看到@repeat 已经建议它时，我正要扔掉这个带有if_/3和(=)/3的版本。所以这本质上是@repeat 概述的更紧凑的版本：

list_dbl([],[]).
list_dbl([X],[X,X,X]).
list_dbl([A,B|Xs],DBL) :-
   if_(A=B,DBL=[A,B|Ys],DBL=[A,A,A,B|Ys]),
   list_dbl([B|Xs],[B|Ys]).

它产生与@repeat 的 dbl2/2 相同的结果：

   ?- list_dbl([a],DBL).
DBL = [a,a,a]
   ?- list_dbl([a,b,b],DBL).
DBL = [a,a,a,b,b,b,b]

OP 的示例查询按预期工作：

   ?- list_dbl([a,b,a,a,a,c,c],DBL).
DBL = [a,a,a,b,b,b,a,a,a,a,a,c,c,c,c]

另外，这里是@lambda.xy.x 提供的一些示例查询。它们产生与@repeat 的 dbl/2 和 @lambda.xy.x 的 dbl/2 相同的结果：

   ?- dif(Xs,[a,a,a,b,b,b,a,a,a,a,a,c,c,c,c]), list_dbl([a,b,a,a,a,c,c],Xs).
no

   ?- list_dbl(X,[a,a,a,b,b]).
no

   ?- list_dbl(L,[a,a,a,b,b,b]).
L = [a,b] ? ;
no

   ?- list_dbl(L,DBL).
DBL = L = [] ? ;
DBL = [_A,_A,_A],
L = [_A] ? ;
DBL = [_A,_A,_A,_A],
L = [_A,_A] ? ;
DBL = [_A,_A,_A,_A,_A],
L = [_A,_A,_A] ? ;
...

   ?- list_dbl([a,X,a],DBL).
DBL = [a,a,a,a,a],
X = a ? ;
DBL = [a,a,a,X,X,X,a,a,a],
dif(X,a),
dif(a,X)

   ?- length(L,_), list_dbl(L,DBL).
DBL = L = [] ? ;
DBL = [_A,_A,_A],
L = [_A] ? ;
DBL = [_A,_A,_A,_A],
L = [_A,_A] ? ;
DBL = [_A,_A,_A,_B,_B,_B],
L = [_A,_B],
dif(_A,_B) ? ;
DBL = [_A,_A,_A,_A,_A],
L = [_A,_A,_A] ?
于 2016-05-21T00:06:14.880 回答
4

TL;DR：从声明的角度来看，@lambda.xy.x 绘制的代码是完美的。可以在不牺牲情况下提高其确定性。

代码变体 #0：@lambda.xy.x 的代码

这是我们要改进的代码：

dbl0（[]，[]）。
dbl0（[X]，[X，X，X]）。
dbl0([X,X|Xs], [X|Ys]) :-
   dbl0([X|Xs], Ys)。
dbl0([X,Y|Xs], [X,X,X|Ys]) :-
   差异（X，Y），
   dbl0([Y|Xs], Ys)。

考虑以下查询和 SWI-Prolog 给我们的答案：

?- dbl0([a],Xs)。
Xs = [a,a,a] ;
假的。

; falseSWI 表示在证明目标时留下了一个选择点。

  • 对于第一个答案，Prolog 没有搜索整个证明树。
  • 相反，它回答说“这是一个答案，可能还有更多”。
  • 然后，当被要求提供更多解决方案时，Prolog 遍历了证明树的剩余分支，但没有找到更多答案。

换句话说：Prolog 需要三思而后行来证明我们一直都知道的事情！

那么，我们如何向 Prolog 提供确定性提示呢？通过利用：

  1. 控制结构 !/0和/或(->)/2（可能不纯）

  2. 主函子上的第一个参数索引（从不纯）

@CapelliC在较早的答案中提供的代码（基于!/0,(->)/2和元逻辑谓词）如果所有参数都充分实例化，则运行良好。如果没有，可能会导致不稳定的答案——正如@lambda.xy.x 的评论所示。 (\=)/2

代码变体 #1：索引

索引可以提高确定性，而不会使代码变得非单调。虽然不同的 Prolog 处理器具有不同的高级索引功能，但“第一参数主函子”索引变体是广泛可用的。

主要的？ 这就是为什么执行目标dbl0([a],Xs)会留下一个选择点：是的，目标只匹配一个子句——dbl0([X],[X,X,X]).但看起来并不比主函子 Prolog 假设最后三个子句中的任何一个最终都可以使用。当然，我们更清楚...

为了告诉 Prolog，我们使用了主函子第一参数索引：

dbl1（[]，[]）。
dbl1([E|Es], Xs) :-
   dbl1_(Es, Xs, E)。

dbl1_([], [E,E,E], E)。
dbl1_([E|Es], [E|Xs], E) :-
   dbl1_(Es, Xs, E)。
dbl1_([E|Es], [E0,E0,E0|Xs], E0) :-
   差异（E0，E），
   dbl1_(Es, Xs, E)。

更好的？有点，但确定性可能会更好......

代码变体 #2：对具体化的术语相等性进行索引

为了让 Prolog 看到 的两个递归子句dbl1_/3是互斥的（在某些情况下），我们具体化术语相等的真值，然后对该值进行索引：

这就是具体化术语平等(=)/3 发挥作用的地方：

dbl2（[]，[]）。
dbl2([E|Es], Xs) :-
   dbl2_(Es, Xs, E)。

dbl2_([], [E,E,E], E)。
dbl2_([E|Es], Xs, E0) :-
   = (E0, E, T),
   t_dbl2_(T, Xs, E0, E, Es)。

t_dbl2_(true, [E|Xs], _, E, Es) :-
   dbl2_(Es, Xs, E)。
t_dbl2_(false, [E0,E0,E0|Xs], E0, E, Es) :-
   dbl2_(Es, Xs, E)。

使用 SWI-Prolog 的示例查询：

?- dbl0([a],Xs)。
Xs = [a, a, a] ;
错误的。

?- dbl1([a],Xs)。
Xs = [a, a, a]。

?- dbl2([a],Xs)。
Xs = [a, a, a]。

?- dbl0([a,b,b],Xs)。
Xs = [a, a, a, b, b, b, b] ;
错误的。

?- dbl1([a,b,b],Xs)。
Xs = [a, a, a, b, b, b, b] ;
错误的。

?- dbl2([a,b,b],Xs)。
Xs = [a, a, a, b, b, b, b]。

为了使上面的代码更紧凑，请使用 control 构造。 if_/3

于 2016-05-20T18:44:25.523 回答
1 
dbl([X,Y|T], [X,X,X|R]) :- X \= Y, !, dbl([Y|T], R).
dbl([H|T], R) :-
        T = []
    ->  R = [H,H,H]
    ;   R = [H|Q], dbl(T, Q).

第一个子句处理基本要求，在序列更改时添加两个元素。第二个将列表终止处理为序列更改，否则进行纯副本。

于 2013-12-22T08:44:20.320 回答