合并Prolog中两个列表中的备用元素

Question

mergealt(X,Y,Z)如果列表Z是列表X和Y中的备用元素的合并,我需要编写一个成功的Prolog谓词.

输入和输出如下:

?- mergealt([1,2,3,4],[6,7,8],Z).
Z = [1, 7, 3] .
?- mergealt([1,2,3,4],[6,7,8,9],Z).
Z = [1, 7, 3, 9] .
?- mergealt([1,2,3,4],[6,7,8,9,10],Z).
Z = [1, 7, 3, 9] .

我真的不明白递归.我怎样才能开始解决这个问题？

Answer 1

Prolog可以被认为是声明性语言的"旗手".所以尽量描述你的问题,自上而下:

mergealt(X, Y, Z) :-
  'take first element from X and put it in Z',
  'discard first element from Y',
  'mergealt rest-of-X and rest-of-Y, but exchange them'.

如果X中没有元素,则无法完成第一步.这一事实突出了递归终止案例.最初,Prolog没有使用if then else,而是替代品被陈述为不同的规则:

mergealt([], _Y, []).

在这里你可以看到,pattern matching在第一个参数上,它是区分备选方案的关键,而在上下文中,Z 绑定到一个空列表.Y未被使用,因此它被标记为匿名占位符,只是为了避免警告.

然后这个更简单的情况表明我们应该使用模式匹配来完成那些冗长的描述.看看您是否可以使用这些指南完成此过程:

mergealt([X|Xs], Y, [X|Zs]) :-
  % take first element from X and put it in Z : done in the head
  % discard first element from Y : see below
  % mergealt rest-of-X and rest-of-Y, but exchange them'. : make your recursive call

discard_first_element([_|Rest], Rest).
% why is this necessary? do you see where it fails if we don't specify this case?
discard_first_element([], []).