Recursive definitions in Prolog

Question

How would I write a recursive definition in Prolog to create an alternating list in the following way :

alternate(K, L, M) holds if the list M is obtained by taking elements alternately from the lists K and L, e.g.:

?- alternate([1,2,3,4,5,6],[a,b,c],Zs).

Zs = [1, a, 2, b, 3, c, 4, 5, 6]

Also, if one list is longer than the other, then the remaining elements of the longer list appear at the end of the result, M .

My attempt for this problem is the following but it is not working:

alternate([],L,L).
alternate(K, [], K).
alternate([Firstk|Restk], [Firstl|Restl], M):-
   K is [Firstk|Restk], L is [Firstl|Restl],
   M is [M|[Firstk]], K is Restk,
   M is [M|[Firstl]], L is Restl,
   alternate(K, L, M).

Any hints or suggestions appreciated

Answer 1

You could describe this relation by flipping the first two arguments in the recursive call, as suggested by @WillNess in the comments. And since the two lists can differ in length it would be helpful to have a predicate that describes lists in general to avoid matching arbitrary terms in the non-recursive rule. It would also be nice to have a somewhat more descriptive name that reflects the relational nature of the predicate. Taking all this into account the predicate might look something like this:

islist([]).
islist([_|T]) :-
   islist(T).

list_list_interlocked([],L,L) :-
   islist(L).
list_list_interlocked([X|Xs],Ys,[X|Zs]) :-
   list_list_interlocked(Ys,Xs,Zs).

Your example query works as expected:

?- list_list_interlocked([1,2,3,4,5,6],[a,b,c],Zs).
Zs = [1, a, 2, b, 3, c, 4, 5, 6].

The predicate also works if the second list is longer:

?- list_list_interlocked([1,2,3],[a,b,c,d,e,f],Zs).
Zs = [1, a, 2, b, 3, c, d, e, f].

And it only works with lists:

?- list_list_interlocked(definitelynolist,[],Zs).
false.

?- list_list_interlocked([],definitelynolist,Zs).
false.

The latter is the reason why you need islist/1. If you define the non-recursive rule like this: list_list_interlocked([],L,L). then Prolog can unify arbitrary terms with L and the query would yield an incorrect result:

?- list_list_interlocked([],definitelynolist,Zs).
Zs = definitelynolist.

The predicate can also be used in the other direction, e.g. What lists yield [1,a,2,b,3,c] when interlocked?:

?- list_list_interlocked(X,Y,[1,a,2,b,3,c]).
X = [],
Y = [1, a, 2, b, 3, c] ;
X = [1, a, 2, b, 3, c],
Y = [] ;
X = [1],
Y = [a, 2, b, 3, c] ;
X = [1, 2, b, 3, c],
Y = [a] ;
X = [1, 2],
Y = [a, b, 3, c] ;
X = [1, 2, 3, c],
Y = [a, b] ;
X = [1, 2, 3],
Y = [a, b, c] ;
false.

Answer 2

I like the other answers, especially the one by @tas. But still, this approach feels too... "small-step". If you are processing two lists and are supposed to pick elements from each, why not pick those two elements simultaneously instead of picking from only one and swapping the lists? That feels like an "algorithm", not like a logical, declarative description of a relation.

So I propose the following:

alternate([], Ys, Ys).
alternate([X|Xs], [], [X|Xs]).
alternate([A | As], [B | Bs], [A, B | ABs]) :-
    alternate(As, Bs, ABs).

The general case, alternating two non-empty lists, is covered by the third clause: The first two elements of the alternated list are the first elements of the two lists to be alternated. The first two clauses just deal with the case where one or the other of the lists is empty. (You could add @tas's islist goals to these to enforce that the other argument really is a proper list.)

Here are the tests:

?- alternate([1,2,3,4,5,6],[a,b,c],Zs).
Zs = [1, a, 2, b, 3, c, 4, 5, 6] ;
false.

?- alternate([1,2,3],[a,b,c,d,e,f],Zs).
Zs = [1, a, 2, b, 3, c, d, e, f].

?- alternate(Xs, Ys, [1,a,2,b,3,c]).
Xs = [],
Ys = [1, a, 2, b, 3, c] ;
Xs = [1, a, 2, b, 3, c],
Ys = [] ;
Xs = [1],
Ys = [a, 2, b, 3, c] ;
Xs = [1, 2, b, 3, c],
Ys = [a] ;
Xs = [1, 2],
Ys = [a, b, 3, c] ;
Xs = [1, 2, 3, c],
Ys = [a, b] ;
Xs = [1, 2, 3],
Ys = [a, b, c] ;
false.

(In SWI-Prolog, which only indexes on the first argument, this leaves slightly more choice points than some alternatives.)

Answer 3

Just write two predicates where one call the other and viceversa, like this:

alternate1([],[],[]).
alternate1([],L,L).
alternate1([H|T],L,[H|T1]):-
    alternate2(T,L,T1).
alternate2([],[],[]).
alternate2(L,[],L).
alternate2(L,[H|T],[H|T1]):-
    alternate1(L,T,T1).

?- alternate1([1,2,3,4,5,6],[a,b,c],Zs).
Zs = [1, a, 2, b, 3, c, 4, 5, 6]
false