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

Your program needs to iterate over the lists in some fashion to interleave L1 and L2 into L3 or disassemble L3 into L1 and L2. When you write "loops" in your post, you mean this iteration. In Prolog, you use recursive predicates to implement loop-like behaviour. Every recursive predicate needs some anchor. In your program, one of the anchors would probably look like this:

zip([], L, L) :- !.

I.e., when L1 is an empty list, then L3 will simply consist of L2.

Note the cut (!/0) at the end of the clause. It tells Prolog that once a predicate call has successfully been unified with the head of this clause, it doesn't need to look for alternatives. This is to avoid unnecessary choicepoints.

This one anchor isn't sufficient. It shouldn't be hard to find the rest.

Now that you have the anchors, you can think about the recursion. The behaviour should be something like this: the next element of L3 (the "head") can either be the next element of L1 or the next element of L2 (i.e., there is a choice here, hence "choicepoint"). Each case probably goes into its own clause.

Whatever the choice, you then call the zip predicate recursively again with the rest (the "tail") of L1 (or L2) and the rest of L3.

This should now be easy to implement.

There is a small catch, however: you still have too many choicepoints, so e.g. this query:

?- zip([1,2],X,[1,a,2,b]).

will not end with a simple "yes", but tell you that there may be more solutions (which there aren't). In order to remove the surplus choicepoint you would have to check whether L3 is already completely instantiated (use ground/1) and handle this case separately.

Answer 2

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