How to write a prolog program that takes List1 and List2 as inputs, and the resulting list is the alternating elements of List1 and List2?

Question

This is my first attempt at using recursion over lists on a non-sample program so bare with my inexperience!

Expected Valid Queries:

mixElements([],[a,b,c], [a,b,c]).
mixElements([a,b],[],[a,b]).
mixElements([a,b,c],[d,e,f],[a,d,b,e,c,f]).
mixElements([a,b,c],[d,e,f,g,h],[a,d,b,e,c,f,g,h]).

Here I tried to create the base case for when the inputs lists are empty, the Result is simply returned.

/* Base cases */
mixElements([],[],Result).

The logic for my recursive statement is that the input lists must be at least 1 or more elements. Thus they must both be represented by [H|L] respectively for list 1 and 2. Then it will append H1 and H2 to Result to create the alternating pattern of list elements. Finally it will call mixElements with the remainder of the lists, L1 and L2, and the Result list that should now contain the first head elements of both lists.

/* Recursive case where both L1 and L2 are not empty */
mixElements([H1|L1],[H2|L2],Result) :- append(H1,H2,Result), mixElements(L1,L2,Result).

My resulting output is always "no".

[near duplicate](https://stackoverflow.com/q/39677973/849891). — Will Ness, Oct 08 '17 at 09:08
@Will: There [is](https://stackoverflow.com/a/8091652/772868) a perfect duplicate! — false, Oct 27 '17 at 15:27

score 3 · Answer 1 · answered Oct 07 '17 at 20:50

When dealing with lists it's usually worthwhile considering DCGs since they yield easily readable code. It further aids readability to choose a descriptive name for the relation, say list_list_interlocked/3. Consider the following code:

list_list_interlocked(L1,L2,I) :-
   phrase(interlocked(L1,L2),I).

interlocked([],[]) -->           % if both input lists are empty
   [].                           % the resulting list is also empty
interlocked([],[H2|T2]) -->      % if the first input list is empty
   [H2],                         % the head of the second is in the list
   interlocked([],T2).           % the relation holds for the tail as well
interlocked([H1|T1],[]) -->      % if the second input list is empty
   [H1],                         % the head of the first is in the list
   interlocked(T1,[]).           % the relation holds for the tail as well
interlocked([H1|T1],[H2|T2]) --> % if both lists are non-empty
   [H1,H2],                      % the heads are in the list
   interlocked(T1,T2).           % the relation holds for the tails as well

Your example queries yield the desired result:

   ?- list_list_interlocked([],[a,b,c],I).
I = [a,b,c]
   ?- list_list_interlocked([a,b],[],I).
I = [a,b]
   ?- list_list_interlocked([a,b,c],[d,e,f],I).
I = [a,d,b,e,c,f]
   ?- list_list_interlocked([a,b,c],[d,e,f,g,h],I).
I = [a,d,b,e,c,f,g,h]

score 0 · Accepted Answer · answered Oct 07 '17 at 19:56

Basically there are four cases here:

the first list is empty, the second list is empty, in that case the result should be empty:
```
mixElements([],[],[]).
```
the first list is empty, the second list is non-empty, in that case, the result is the second list:
```
mixElements([],[H2|T2],[H2|T2]).
```
the first list is non-empty, the second list is empty, in that case, the result is the first list:
```
mixElements([H1|T1],[],[H1|T1]).
```
finall both lists are non-empty, in that case the two first elements of the result are the heads of the list, followed by mixing the tails of the lists:
```
mixElements([H1|T1],[H2|T2],[H1,H2|TT]) :-
    mixElements(T1,T2,TT).
```

Now we can put that all together into:

mixElements([],[],[]).
mixElements([],[H2|T2],[H2|T2]).
mixElements([H1|T1],[],[H1|T1]).
mixElements([H1|T1],[H2|T2],[H1,H2|TT]) :-
    mixElements(T1,T2,TT).

Now we have created some redundant statements. For instance we can merge the first two statements into one, like:

mixElements([],L,L).
mixElements([H1|T1],[],[H1|T1]).
mixElements([H1|T1],[H2|T2],[H1,H2|TT]) :-
    mixElements(T1,T2,TT).

I leave it as an exercise to further improve the predicate. You can for instance use cuts, but this can eliminate the multi-direction of the predicate, which is sometimes very useful.

score 0 · Answer 3 · answered Oct 08 '17 at 09:10

0

You're using append/3 where it's not needed. When the pattern is formed by 2 lists of at least one element, you can get the result immediately, then recurse to handle the tails:

mixElements([H1|L1],[H2|L2],[H1,H2|Rest]) :-
    !, mixElements(L1,L2,Rest).
mixElements(L1,L2,Rest) :- append(L1,L2,Rest).

answered Oct 08 '17 at 09:10

CapelliC

59,646
5
47
90

1

Isn't a potential problem with this predicate that for `mixElements(A,B,[a,b])`, `A=[a,b], B=[]` and `A=[], B=[a,b]` is not a possible answer? – Willem Van Onsem Oct 09 '17 at 20:06

How to write a prolog program that takes List1 and List2 as inputs, and the resulting list is the alternating elements of List1 and List2?

3 Answers3