Creating a list of interleaved elements: Prolog

Question

I am defining a function alternate_func(Ps, P) where Ps is a list of lists and P is a list of all elements in Ps that behaves in the following way: .

?- alternate_func([[p,q],[r,s]],P). 
P=[p,r,q,s]. (case 1)

?- alternate_func([P,Q,R],[p,q,r,s,t,u]). 
P=[p,s], Q=[q,t], R=[r,u]. (case 2)

?- alternate_func([Q],[1,2,3]). 
Q=[1,2,3]. (case 3)

?- alternate_func([[4,5,6],[3,1],[4,1,2]],X).
false. (because Length of sublists must be same) (case 4)

This is what I have tried so far,

alternate_func([[], L], L).          
alternate_func([[H|T], []], [H|T]).  

alternate_func([[X|L1], [Y|L2]], [X,Y|L3]) :-
    alternate_func([L1, L2], L3).

I am getting correct result for the case 1 but fails for the 2,3 and 4. What is the problem here?

Answer 1

This solution processes the list of lists splitting the head / tail off each list. Afterwards:

• If all tails are empty we are done.
• Otherwise the process is repeated again, with the tails.

Code:

lists_interleaved( Ess, Es):-
  lists_interleaved( Ess, X-X, Es).

lists_interleaved( [], Head-[], []):-
  maplist(=([]), Head).
lists_interleaved( [], [First|Head]-[], Es):-
  lists_interleaved( [First|Head], X-X, Es).
lists_interleaved( [[E|ETail]|Ess], Head-[ETail|Rest], [E|Es]):-
  lists_interleaved( Ess, Head-Rest, Es).

Answer 2

First, stick to good naming of relations. There is no function here. You have a relation between a list of lists and a list. So a name lists_interleaved(Ess, Es) is preferable.

:- set_prolog_flag(double_quotes, chars).  % to permit that "abc" = [a,b,c]

lists_interleaved(Ess, Es) :-
   transpose(Ess, EssT),
   phrase(seqq(EssT), Es).          % alternatively append(EssT,Es)

See the definition of seqq//1.

Still this is not the nicest definition. After all, ?- lists_interleaves(Ess, "abcd"). does not terminate. Let's use a failure-slice to see why:

lists_interleaved(Ess, Es) :-
   transpose(Ess, EssT), false,
   phrase(seqq(EssT), Es). 

?- lists_interleaved(Ess, "abcd"), false.
   loops.

A simple way to fix this is to establish a relation between Ess and Es. After all, the first list in Ess can be at most as long as Es, and also Ess cannot be longer.

By adding these restrictions as extra goals, we get:

lists_interleaved(Ess, Es) :-
   Ess = [Fs|_],
   Fs = [_|_],
   list_longer(Ess, Es),
   list_longer(Fs, Es),
   transpose(Ess, EssT),
   phrase(seqq(EssT), Es).

list_longer([], _).
list_longer([_|Es], [_|Fs]) :-
   list_longer(Es, Fs).

This now constrains us to an Es with at least one element.

?- lists_interleaved(Ess, "abcdef").
   Ess = ["abcdef"]
;  Ess = ["ace","bdf"]
;  Ess = ["ad","be","cf"]
;  Ess = ["a","b","c","d","e","f"]
;  false.

See this answer how to print solutions using compact double-quotes notation.

And still, this isn't perfect as these list_longer/2 goals are now essentially guessing. But I will leave it as is since this is what you asked for.

(I will put a bounty for a better definition/or justification why this is not possible)