PROLOG - Flatten a list of segments

user_10212261 0
Viewed 141

I want to flatten a list like this:

[[a,b],[b,c],[c,d],.. ] -> [a,b,c..]

In short, I want to take the head of each segment [a,b] and place in a flattened list.

I have the current code:

%unsplits a list from segments
%e.g [[a,b],[b,c]] becomes [a,b,c].
unSplitList([],_).
unSplitList([[H,_]|T], L) :- append([H], L1, L), unSplitList(T, L1).

But it gives me the following output:

?- unSplitList([[a,b],[b,c],[c,d]],L).
L = [a, b, c|_1046].

How would I go on about removing that tail (_1046)? Thanks in advance :).

prolog list
2 Answers

The problem here is the underscore in:

unSplitList([],_).

this means that the list you construct on the "fly" does not end with [], and hence keeps an open end.

You can fix this by writing:

unSplitList([], []).

That being said, the above can be improved a bit in terms of elegance and efficiency. Here we can replace append([H], L1, L) with L = [H|L1], so

unSplitList([],[]).
unSplitList([[H,_]|T], [H|L1]) :-
    unSplitList(T, L1).

we can also improve the above by writing it in terms of maplist/3 [swi-doc]:

head([H|_], H).

unSplitList(L, Hs) :-
    maplist(head, L, Hs).

Note that the above will not work for lists that contain empty sublists (or other objects like numbers).

user_675790

In addition to @WillemVanOnsem's elegant maplist/3 based solution I'd like to point out the possibility to describe the list of heads with a DCG.

lists_heads(Ls,Hs) :-      % the list of heads, HS, of the lists in Ls
   phrase(heads(Ls),Hs).   % is described by the DCG heads//1

heads([]) -->              % if there are no lists
   [].                     % there are no heads
heads([L|Ls]) -->          % if L is the first list in the list of lists
   head(L),                % its head is in the list of heads
   heads(Ls).              % followed by the heads of the other lists

head([H|_]) -->            % the head H of the list
   [H].                    % is in the list of heads

This DCG version produces the same answers as Willem's maplist/3 based version:

   ?- lists_heads([[a,b],[b,c],[c,d]],L).
L = [a,b,c]
   ?- unSplitList([[a,b],[b,c],[c,d]],L).
L = [a,b,c]

   ?- lists_heads([[a,b,c],[b,c],[c,d]],L).
L = [a,b,c]
   ?- unSplitList([[a,b,c],[b,c],[c,d]],L).
L = [a,b,c]

   ?- lists_heads(Ls,[a,b,c]).
Ls = [[a|_A],[b|_B],[c|_C]] ? ;
no
   ?- unSplitList(Ls,[a,b,c]).
Ls = [[a|_A],[b|_B],[c|_C]]

As Willem also pointed out, these predicates will only work if the first argument does not contain empty lists. You can easily modify the DCG head//1 to account for such cases. For comparison reasons I name the modified version lists_heads2/2 and only comment the additional DCG-rule:

lists_heads2(Ls,Hs) :-
   phrase(heads2(Ls),Hs).

heads2([]) -->
   [].
heads2([L|Ls]) -->
   head2(L),
   heads2(Ls).

head2([]) -->              % if the list is empty
   [].                     % it contributes no element to the list of heads
head2([H|_]) -->
   [H].

The following queries illustrate the difference between the two versions:

   ?- lists_heads([[],[a,b,c],[],[b,c],[c,d]],L).
no
   ?- lists_heads2([[],[a,b,c],[],[b,c],[c,d]],L).
L = [a,b,c]

However, this additional flexibility comes at a price that might not be evident at first glance: Since the first argument can contain an arbitrary number of empty lists, lists_heads2/2 will loop if used in the other direction:

   ?- lists_heads(Ls,[a,b,c]).
Ls = [[a|_A],[b|_B],[c|_C]] ? ;
no
   ?- lists_heads2(Ls,[a,b,c]).
...                            % <- loops infinitely

In order to avoid this behaviour you have to restrict the length of the first list if you use the predicate in this direction:

   ?- length(Ls,N), lists_heads2(Ls,[a,b,c]).
Ls = [[a|_A],[b|_B],[c|_C]],               % solution of length 3
N = 3 ? ;
Ls = [[],[a|_A],[b|_B],[c|_C]],            % solutions of length 4
N = 4 ? ;
Ls = [[a|_A],[],[b|_B],[c|_C]],
N = 4 ? ;
Ls = [[a|_A],[b|_B],[],[c|_C]],
N = 4 ? ;
Ls = [[a|_A],[b|_B],[c|_C],[]],
N = 4 ? ;
Ls = [[],[],[a|_A],[b|_B],[c|_C]],         % solutions of length 5
N = 5 ? ;
.
.
.
user_61011590
Related