Find all lists of sublists that when concatenated give a given list

Question

I wrote this function that given as a first parameter a list of lists, it generates in the second parameter the result of concatenating all the lists.

appall([],[]).
appall([H|T],V) :- appall(T,V1), append(H,V1,V).

However, I want it to work the other way around - appall(X,[1,2,3]) - to give me X = [[],[1,2,3]] then X=[[1],[2,3]] and so on. This doesn't work because the call appall(T, V1) doesn't decrease.

How do I fix it?

Answer 1

Here is one solution:

split([],[]).
split([Head|Tail],[[Head]|Split]) :-
    split(Tail,Split).
split([Head|Tail],[[Head|List]|Split]) :-
    split(Tail,[List|Split]).

For example:

?- split([1,2,3,4],Lists), split(Recover,Lists).
Lists = [[1], [2], [3], [4]],
Recover = [1, 2, 3, 4] ;
Lists = [[1], [2], [3, 4]],
Recover = [1, 2, 3, 4] ;
Lists = [[1], [2, 3], [4]],
Recover = [1, 2, 3, 4] ;
Lists = [[1], [2, 3, 4]],
Recover = [1, 2, 3, 4] ;
Lists = [[1, 2], [3], [4]],
Recover = [1, 2, 3, 4] ;
Lists = [[1, 2], [3, 4]],
Recover = [1, 2, 3, 4] ;
Lists = [[1, 2, 3], [4]],
Recover = [1, 2, 3, 4] ;
Lists = [[1, 2, 3, 4]],
Recover = [1, 2, 3, 4] ;
false.

This solution is based on the following observation. I will refer to the flattened list as the input list and the unflattened list as the output list. In the recursive case, the input list has the form [H|T] and split(T,R) succeeds by assumption. There are three cases to consider.

1. If R = [] we can begin constructing a new list whose last element is H.
2. If R = [_|_] we can begin constructing a new list whose last element is H.
3. If R = [L|_] we can continue constructing L by prepending H to L.

In each case, we obtain valid output lists. The first two cases are implemented by the second clause of split/2 (it doesn't matter whether R = [] or R = [_|_]) and the third by the third clause.