Prolog中的zip功能

Question

我是Prolog的新手,我的任务要求我们实现如下所述的功能:

写Prolog的谓词zip(L1,L2,L3)如果列表是真的L3被压缩和解(即洗牌"或交错")名单的元素获得L1和L2.更新:列表L1,并L2可以有不同的长度.例如,完成后,您应该得到以下行为:

?- zip([1,2],[a,b],[1,a,2,b]).
true.
?- zip([1,2],[a,b],X).
X = [1, 2, a, b] ;
X = [1, 2, a, b] ;
X = [1, a, 2, b] ;
X = [1, a, b, 2] ;
X = [a, 1, 2, b] ;
X = [a, 1, b, 2] ;
X = [a, b, 1, 2] ;
X = [a, b, 1, 2] ;
false.
?- zip([1,2],[a,b],[1,2,a,b]).
true.
?- zip(X,[a,b],[1,a,2,b]).
X = [1,2]
true.
?- zip([1,2],X,[1,a,2,b]).
X = [a,b]
true.

我正在考虑创建一个包含来自L1和的元素L2的列表,然后将列表与之进行比较L3.但我不熟悉Prolog中的语法和循环.

Answer 1

实际上,我有三个答案.你可能想要第三个.但无论如何都要经历其他人.

1个不同的问题

我不确定你想要你所描述的关系.你也在同时学习OCaml和Python,在这些语言中,zip意味着别的东西.它意味着:

zip([], [], []).
zip([], [_|_], []).
zip([_|_], [], []).
zip([X|Xs], [Y|Ys], [X-Y|XYs]) :-
   zip(Xs, Ys, XYs).

?- zip([1,2],[3,4],XYs).
XYs = [1-3,2-4].

请注意Prolog中的不同约定.虽然OCaml,Python以及Haskell使用(X,Y)来表示元组,但Prolog中的常见约定是使用(XY).这里的减号并不意味着减法.这只是一个未被解释的术语.

在Prolog中实现此功能的常用方法是使用maplist.maplist要求所有列表具有相同的长度.

2隔行扫描

(编辑)另一种解释如下.这个名字喜欢interlace/3或者shuffle/3 理想.最近@salva向我们展示了一个非常漂亮的解决方案.别忘了给它+1!让我只展示一些如何使用它的很酷的方法:

?- shuffle([1,2],[3,4],Zs).
Zs = [1,3,2,4].

你已经知道了.但为什么我们需要同时给出两个列表[1,2] 和[3,4]Prolog？这不是一种简单的编程语言,它迫使你讲述所有内容.如果你懒得输入复杂的列表或其他术语,只需输入一个变量,看看Prolog是如何计算出来的.所以,让我们用变量替换第二个列表.

?- shuffle([1,2],Ys,Zs).
Ys = [],
Zs = [1,2] ;
Ys = [_G607],
Zs = [1,_G607,2] ;
Ys = [_G607,_G616|_G617],
Zs = [1,_G607,2,_G616|_G617].

通过这种方式,我们会问:怎么做Ys并且Zs必须看起来像shuffle/3是真的？事实上,有3个答案Ys:

• []成为空名单. Zs那么[1,2].所以这是一个解决方案.

• [_G607]是一个只有一个元素的列表.Zs是的[1,_G607,2].这_G607是一个自由变量.它可能有一个更好的名称,但关键是这个变量发生在内部Ys和内部Zs.这个答案说:适合该变量的所有术语都是解决方案.所以我们在这里有无限多的解决方案在一个答案中表达.

• [_G607,_G616|_G617] 意思是包含至少两个元素的列表.

这是一个更酷的查询:

?- shuffle(Xs,Xs,Zs).
Xs = Zs, Zs = [] ;
Xs = [_G592],
Zs = [_G592,_G592] ;
Xs = [_G592,_G601],
Zs = [_G592,_G592,_G601,_G601] ;
Xs = [_G592,_G601,_G610],
Zs = [_G592,_G592,_G601,_G601,_G610,_G610]
...

看看现在如何重复同一个变量Zs!

3交织在一起

也许这就是你真正想要的:

intertwine([], [], []).
intertwine([E|Es], Fs, [E|Gs]) :-
   intertwine(Es, Fs, Gs).
intertwine(Es, [F|Fs], [F|Gs]) :-
   intertwine(Es, Fs, Gs).

在下面的查询中,我们询问可以交织在一起的列表,以便给出三元素列表作为结果!

?- length(Zs,3), intertwine(Xs,Ys,Zs).
Zs = Xs, Xs = [_G648,_G651,_G654],
Ys = [] ;
Zs = [_G648,_G651,_G654],
Xs = [_G648,_G651],
Ys = [_G654] ;
Zs = [_G648,_G651,_G654],
Xs = [_G648,_G654],
Ys = [_G651] ;
Zs = [_G648,_G651,_G654],
Xs = [_G648],
Ys = [_G651,_G654] ;
Zs = [_G648,_G651,_G654],
Xs = [_G651,_G654],
Ys = [_G648] ;
Zs = [_G648,_G651,_G654],
Xs = [_G651],
Ys = [_G648,_G654] ;
Zs = [_G648,_G651,_G654],
Xs = [_G654],
Ys = [_G648,_G651] ;
Zs = [_G648,_G651,_G654],
Xs = [],
Ys = [_G648,_G651,_G654].