zip function in Prolog

Question

I'm new to Prolog and my assignment requires us to implement a function as described below:

Write a Prolog predicate zip(L1,L2,L3) that is true if the list L3 is obtained by zipping (i.e. shuffling", or interleaving") the elements of the lists L1 and L2. Update: the lists L1 and L2 can have different lengths. For instance, when you are done, you should get the following behavior:

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

I'm thinking of creating a list which contains elements from L1 and L2 and then compare the list with L3. But I'm not familiar with the syntax and loops in Prolog.

Answer 1

Actually, I have three answers to you. You probably want the third. But go through the others anyway.

1 Different problem

I am not that sure that you want the relation you describe. You are also learning OCaml and Python at the same time and in those languages zip means something else. It means something like:

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

Note the different convention in Prolog. While OCaml, Python but also Haskell use (X,Y) to denote a tuple, the frequent convention in Prolog is to use (X-Y). The minus sign here does not mean subtraction. It is just an uninterpreted term.

The common way to implement this in Prolog is to use maplist. maplist requires that all lists are of same length.

2 Interlacing

(Edit) Another interpretation is the following. A name like interlace/3 or shuffle/3 would be ideal here. Recently @salva has showed us a very beautiful solution to this. Don't forget to +1 it! Let me only show some cool ways how you can use it:

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

This you already know. But why do we need to give both lists [1,2] and [3,4] to Prolog? This isn't a simple programming language which forces you to tell everything. If you are too lazy to type in a complex list or another term, just put a variable and see how Prolog figures it out. So, let's replace the second list by a variable.

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

In this manner we ask: How do Ys and Zs have to look like such that shuffle/3 is true? In fact, there are 3 answers for Ys:

• [] being the empty list. Zs is then [1,2]. So this is one solution.

• [_G607] being a list with exactly one element. Zs is the [1,_G607,2]. The _G607 is a free variable. It could have a nicer name, but the point is that this variable occurs both within Ys and within Zs. This answer says: All terms that fit into that variable are solutions. So we have here infinitely many solutions expressed within a single answer.

• [_G607,_G616|_G617] meaning a list with at least two elements.

Here is an even cooler query:

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

Look how there are now duplicates of the same variable in Zs!

3 Intertwining

Maybe this is what you actually want:

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

In the following query we ask about the lists that can be intertwined to give a three element list as result!

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