Prolog how do I append a list of lists into one list?

Question

So I'm totally new to Prolog and need some help. I'm trying to take a list of lists like [[1,2,3],[4,5,6],[7,8]] and create a list like [2,3,5,6,8], so basically all the values into a new list besides the first of each list. I got this:

test5(X,[[_|X]|_]).
test5(X,[_|A]) :- test5(X,A).

which returns [2,3] and then [5,6] and then [8] each time I press enter. I'm not sure how to make them run all at once and make them into a list. I tried using append in different ways but I could not get this working. Any idea on how to implement this? Thanks!

Answer 1

You have the common predicate flatten/2, which almost does the job:

?- flatten([[1,2,3],[4,5,6],[7,8]], L).
L = [1, 2, 3, 4, 5, 6, 7, 8].

There are many implementations of flatten/2 available, just google it.

If you know that the list of lists is not nested, you should rather use append/2.

Then, you need to drop the first element of each list before appending:

list_tail([_|T], T).

Then:

?- maplist(list_tail, [[1,2,3],[4,5,6],[7,8]], T), append(T, L).
T = [[2, 3], [5, 6], [8]],
L = [2, 3, 5, 6, 8].

It might be a good exercise to take a more careful look at the implementation of append/2 linked above. With a small change in the definition (literally removing 1 character and adding 5) it will do the dropping and appending in the same step, without traversing the original list twice.

EDIT

So why is it that @repeat's initial solution does not terminate when the first argument is not a proper list, but the second is a proper list?

nt_tails_append([[_|T]|Ls], As) :-
    append(T, Ws, As),
    nt_tails_append(Ls, Ws).

It is because when the first argument to nt_tails_append/2 is a free variable, the first two arguments to append/3 above are variables, too. When we call append/3 in this mode, we get, by definition:

?- append(A, B, L).
A = [],
B = L .

In other words, the second and the third arguments are now unified. With the definition of nt_tail_append/2, this means that the recursive call gets the same second argument as the original call, and a new free variable as the first argument. This is an endless loop, of course.

(Tellingly, if you care to look at the definition of append/2 linked above, you will see that the first argument must_be a list.)

How does this help?

tails_append(Ls, As) :-
    maplist(list_tail, Ls, T),
    append(T, As).

list_tail([_|T], T).

The way that maplist is defined, all list arguments will be instantiated to proper lists. So you can safely use append/3 (here, used in the definition of append/2).

Answer 2

Here is how you could do it using append/3:

lists_concatenatedTails([],[]).
lists_concatenatedTails([[_|Xs0]|Xss],Ys) :-
    append(Xs0,Ys0,Ys),
    lists_concatenatedTails(Xss,Ys0).

Sample query:

?- lists_concatenatedTails([[1,2,3],[4,5,6],[7,8]], Xs).
Xs = [2, 3, 5, 6, 8].

---

Edit 2015-05-07

Note that the code that @Boris suggested (using list_tail/2,maplist/3,append/2) also gives answers for the following query:

?- maplist(list_tail,Xss,Yss), append(Yss,[1,2,3]).
Xss = [[_G97, 1, 2, 3]],                   Yss = [[1, 2, 3]]         ;
Xss = [[_G97], [_G106, 1, 2, 3]],          Yss = [[], [1, 2, 3]]     ;
Xss = [[_G97, 1], [_G106, 2, 3]],          Yss = [[1], [2, 3]]       ;
Xss = [[_G97, 1, 2], [_G106, 3]],          Yss = [[1, 2], [3]]       ;
Xss = [[_G97, 1, 2, 3], [_G106]],          Yss = [[1, 2, 3], []]     ;
Xss = [[_G97], [_G106], [_G115, 1, 2, 3]], Yss = [[], [], [1, 2, 3]] ...

This doesn't terminate universally---nor do we expect it to: the set of solutions is infinite in size and it can, in this case, only be covered by an infinite sequence of answers.

In the following equivalent query lists_concatenatedTails/2 "loops" right away:

?- lists_concatenatedTails(Lss,[1,2,3]).
% not a single answer within finite time

Only when constraining the length of Lss right away, fair enumeration can be achieved:

?- length(Lss,_), lists_concatenatedTails(Lss,[1,2,3]).
Lss = [[_G23, 1, 2, 3]] ;
Lss = [[_G26], [_G29, 1, 2, 3]] ;
Lss = [[_G26, 1], [_G32, 2, 3]] ;
Lss = [[_G26, 1, 2], [_G35, 3]] ;
Lss = [[_G26, 1, 2, 3], [_G38]] ;
Lss = [[_G29], [_G32], [_G35, 1, 2, 3]] ...