PROLOG - Свести список сегментов

Question

Я хочу сгладить список следующим образом:

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

Короче говоря, я хочу взять заголовок каждого сегмента [a, b] и поместить в плоский список.

У меня есть текущий код:

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

Но это дает мне следующий вывод:

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

Как мне продолжить удаление этого хвоста (_1046)? Заранее спасибо:).

Answer 1

В дополнение к элегантному решению @ WillemVanOnsem на основе maplist / 3, я хотел бы указать на возможность описать список головок с помощью 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

Эта версия DCG дает те же ответы, что и версия Willem's maplist / 3:

   ?- 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]]

Как отметил Виллем, эти предикаты будут работать только в том случае, если первый аргумент не содержит пустых списков. Вы можете легко изменить заголовок DCG // 1 для учета таких случаев. Для сравнения я называю измененную версию lists_heads2 / 2 и комментирую только дополнительное DCG-правило:

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

Следующие запросы иллюстрируют разницу между двумя версиями:

   ?- 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]

Однако эта дополнительная гибкость достигается ценой, которая может быть неочевидна на первый взгляд: поскольку первый аргумент может содержать произвольное количество пустых списков, lists_heads2 / 2 будет зацикливаться, если используется в другом направлении:

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

Чтобы избежать такого поведения, вы должны ограничить длину первого списка, если вы используете предикат в этом направлении:

   ?- 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 ? ;
.
.
.

Answer 2

Проблема здесь в подчеркивании:

unSplitList([],_).

это означает, что список, который вы строите на «лету», не заканчивается на [] и, следовательно, сохраняет открытый конец.

Вы можете исправить это, написав:

unSplitList([], <b>[]</b>).

При этом вышесказанное можно немного улучшить с точки зрения элегантности и эффективности. Здесь мы можем заменить append([H], L1, L) на L = [H|L1], поэтому

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

мы также можем улучшить вышесказанное, написав его в виде maplist/3 [swi-doc] :

head([H|_], H).

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

Обратите внимание, что вышеприведенное не будет работать для списков, которые содержат пустые подсписки (или другие объекты, такие как числа).