list - 使用 prolog 再添加两次

Question

我有一个 list [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).

Answer 1

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

您已经有一个好主意，可以查看列表中元素发生变化的部分。所以有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) 上递归。请注意，我们通过两次写入相同的变量隐式地使前两个元素相等(即我们统一了它们)。

如果你看case 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 的单次运行；或者 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) ;
[...]

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

(*) 备注:这种情况仅适用于我们使用了 dif。通常遇到的第一个等式谓词是 =、== 以及它们各自的否定词\= 和\==。 = 代表统一性(替换参数中的变量 s.t. 它们变得相等)而 == 代表句法相等(术语完全相等)。例如。:

?- 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 始终为真，所以我们不能在我们的代码中使用\==。与此相反， diff 等待直到它可以决定其参数是否相等。如果在找到答案后仍未决定，则打印“dif(X,a)”语句。

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