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?

Do all sublists have to have the same length? – false Apr 22 '19 at 14:06 — false, Apr 22 '19 at 14:06
Yes, they have to be of the same length. – Katherine Apr 22 '19 at 23:39 — Katherine, Apr 22 '19 at 23:39

gusbro · Accepted Answer · 2019-04-30T18:48:28.207

5

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

edited Apr 30 '19 at 18:48

answered Apr 29 '19 at 16:06

gusbro

22,357
35
46

What is this X-X notation? I have never come across it? – Katherine Apr 29 '19 at 23:11
2

@Katherine `X-X` is the same as `-(X,X)` is the same as `p(X,X)` or `q(X,X)` etc., with arbitrary name `-`, `p`, `q`, or whatever. it is just a compound term holding two arguments, written in infix notation. – Will Ness Apr 30 '19 at 10:12
@Katherine here's [my re-write](https://gist.github.com/WillNess/0b6f19cea9b084d129bb0af1b048106c#file-so-55795221-md) of this code. see if it is easier to follow. :) – Will Ness Apr 30 '19 at 10:54
`is_prime(N):- length(L,N), findall(X, lists_interleaved( X, L), [_,_]).` !!! :) :) – Will Ness Apr 30 '19 at 16:44
1

@WillNess: Interesting observation... After thinking a bit it makes sense. – gusbro Apr 30 '19 at 17:11
another one: `factors(Num,M*N):- length(L,Num), lists_interleaved( X, L), maplist(length,X,[M|_]), length(X,N).` :) --- but that is of course a ***very*** roundabout way to do just the same as `factors(Num, M*N):- findall(A, between(1,Num, A),As), reverse(As,Bs), member(M,Bs), N is Num div M, Num is M*N.`...... – Will Ness Apr 30 '19 at 17:55
Any reason why `'='([])` is preferable to `=([])`? – false Apr 30 '19 at 18:36

false · Answer 2 · 2022-08-11T15:41:59.020

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)

Hi, thanks for the response. `P = [_16262, _16268|_16270].` is what i am getting for case 1. now, with your code. Rest of the cases fail as well. I don't have an issue with quotes, my earlier code ran fine for case 1. Can you please help me? — Katherine, Apr 22 '19 at 23:46
You probably added the improved version as a separate rule. To avoid any ambiguity, I have now given the entire program. And, of course all of your cases work. It is even better than that! The case `lists_interleaved(Ess, "abcdef").` is more general than the cases you asked for. — false, Apr 23 '19 at 09:55
Hi, I understood what I did wrong. I was getting `Undefined procedure: transpose/2` and `Undefined procedure: seqq/3` so defined those using their definitions I found in swipl-devel/clpfd.pl. And then it worked for 3/4 cases. Still fails for case no. 2 with `Arguments are not sufficiently instantiated`. — Katherine, Apr 23 '19 at 12:34
Use `clpfd:lists_transpose(Ess, EssT),` instead. This version has much too much error checking. — false, Apr 23 '19 at 13:42

Creating a list of interleaved elements: Prolog

2 Answers2