使用序言再添加两次 [英] Add two more occurrences using prolog

问题描述

我有一个列表[a, b, a, a, a, c, c] 并且我需要为每个元素添加两次以上的引用.

I have a list [a, b, a, a, a, c, c] and I need to add two more occurrences of each element.

最终结果应如下所示:

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

如果列表中有一个与下一个项目相同的项目，那么它将一直进行下去，直到有一个新项目为止，当它找到新项目时，它会添加两次出现的上一个项目，然后继续进行.

If I have an item on the list that is the same as the next item, then it keeps going until there is a new item, when it finds the new item, it adds two occurrences of the previous item then moves on.

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

This is my code so far, but I can't figure out how to add two...

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

推荐答案

您的代码看起来有些奇怪，因为最后一条规则带有三个参数.您只调用二进制版本，因此任何递归都不会尝试派生它.

Your code looks a bit strange because the last rule takes three parameters. You only call the binary version, so no recursion will ever try to derive it.

您已经有了一个好主意，可以查看列表中元素更改的部分.因此有4种情况:

You already had a good idea to look at the parts of the list, where elements change. So there are 4 cases:

1)您的列表为空. 2)您只有一个元素. 3)您的列表以两个相等的元素开头. 4)您的列表以两个不同的元素开头.

1) Your list is empty. 2) You have exactly one element. 3) Your list starts with two equal elements. 4) Your list starts with two different elements.

案例1未指定，因此您可能需要为此找到一个明智的选择.情况2在某种程度上类似于情况4，因为列表的末尾可以看作是元素的更改，您需要在其中添加两个副本，但随后就完成了.情况3非常简单，我们可以保留元素，然后递归其余部分.在情况4中，您需要再次插入两个副本.

Case 1 is not specified, so you might need to find a sensible choice for that. Case 2 is somehow similar to case 4, since the end of the list can be seen as a change in elements, where you need to append two copies, but then you are done. Case 3 is quite simple, we can just keep the element and recurse on the rest. Case 4 is where you need to insert the two copies again.

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

This means your code will look something like this:

% 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 3 should be easy to finish, we just drop the first X from both lists and recurse on dbl([X|Xs],Ys). Note that we implicitly made the first two elements equal (i.e. we unified them) by writing the same variable twice.

如果看案例4的开头，您可以直接模仿您描述的模式:假设列表以X开头，那么Y且它们是不同的(dif(X，Y))，X重复了3次而不是仅仅复制，然后我们继续以Y开头的其余部分递归:dbl([Y | Xs]，Ys).

If you look at the head of case 4, you can directly imitate the pattern you described: supposed the list starts with X, then Y and they are different (dif(X,Y)), the X is repeated 3 times instead of just copied and we then continue with the recursion on the rest starting with Y: dbl([Y|Xs],Ys).

所以让我们尝试一下谓词:

So let's try out the predicate:

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

我们的测试用例被接受(true)，并且我们发现的解决方案不止一个(false). 让我们看看是否找到错误的解决方案:

Our test case is accepted (true) and we don't find more than one solution (false). Let's see if we find a wrong solution:

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

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

No, that's also good. What happens, if we have variables in our list?

?- 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，那么我们需要在所有三个运行中附加副本.看起来还不错. (*)

Either X = a, then Ys is single run of 5 as; or X is not equal to a, then we need to append the copies in all three runs. Looks also fine. (*)

现在让我们看看，如果仅指定解决方案，会发生什么情况:

Now lets see, what happens if we only specify the solution:

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

对，一个只有两个bs的列表不能是我们指定的结果.因此，让我们尝试添加一个:

Right, a list with a run of only two bs can not be a result of our specification. So lets try to add one:

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

万岁，成功了！因此，如果我们仅使用两个变量来调用谓词，那么最后做一个测试看看会发生什么:

Hooray, it worked! So lets as a last test look what happens, if we just call our predicate with two variables:

?- 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的搜索策略的结果(在此将不做解释).但是，如果我们在生成更长的列表之前先查看较短的列表，则可以看到所有解决方案:

It seems we get the correct answers, but we see only cases for a single run. This is a result of prolog's search strategy(which i will not explain in here). But if we look at shorter lists before we generate longer ones, we can see all the solutions:

 ?- 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) ;
[...]

因此，似乎我们有一个有效的谓词(**)，假设您填写了文本中缺少的目标:)

So it seems we have a working predicate (**), supposed you filled in the missing goals from the text :)

(*)这里的说明:这种情况仅适用于我们使用dif的情况.具有相等性的第一个谓词，通常遇到的是=，==及其各自的否定\ =和\ ==. =代表统一性(用变量s.t.代替变量变得相等)，而==代表句法相等(术语完全相等).例如:

(*) A remark here: this case only works because we are using dif. The first predicates with equality, one usually encounters are =, == and their respective negations \= and \==. The = stands for unifyability (substituting variables in the arguments s.t. they become equal) and the == stands for syntactic equality (terms being exactly equal). E.g.:

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

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

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

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

这意味着，如果将X替换为a，则可以使f(X)等于f(a).这意味着，如果我们询问是否不能使它们相等(\ =)，我们将得到错误的答案.另一方面，这两个术语不相等，因此==返回false，而其否定\ ==则返回true.

This means, we can make f(X) equal to f(a), if we substitute X by a. This means if we ask if they can not be made equal (\=), we get the answer false. On the other hand, the two terms are not equal, so == returns false, and its negation \== answers true.

这也意味着X \ == Y始终为true，因此我们不能在代码中使用\ ==.与此相反，dif等待直到可以确定其参数是否相等.如果找到答案后仍不确定，则打印"dif(X，a)"语句.

What this also means is that X \== Y is always true, so we can not use \== in our code. In contrast to that, dif waits until it can decide wether its arguments are equal or not. If this is still undecided after finding an answer, the "dif(X,a)" statements are printed.

(**)这里的最后一句话:还有一种使用if-then-else构造的解决方案(测试-> Goal_if_true； targets_if_false，它将案例3和4合并在一起.由于我更喜欢​​这种解决方案，因此您可能需要自己查看其他版本.

(**) One last remark here: There is also a solution with the if-then-else construct (test -> goals_if_true; goals_if_false, which merges cases 3 and 4. Since i prefer this solution, you might need to look into the other version yourself.

这篇关于使用序言再添加两次的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！