Удаление повторяющихся решений

Мой код объединяет два списка списков, элемент за элементом, следующим образом:

mergeL([[a,b],[c,d]], [[1,2],[3,4]], Result). Result = [[a,b,1,2],[c,d,3,4]]

И это код, который я использую:

mergeL([],[],[]).
mergeL(List, [], List).
mergeL([], List, List).
mergeL([X|Rest],[Y|Rest2], [XY|Res2]) :-
   mergeL(Rest, Rest2, Res2),
   append(X,Y,XY).

Кажется, это работает, но если я вызову его с двумя списками одинакового размера, я получу три повторяющихся результата. Пример (оба списка содержат только один элемент):

?- mergeL([[a,b]],[[1,2,3]],Q).
Q = [[a, b, 1, 2, 3]] ;
Q = [[a, b, 1, 2, 3]] ;
Q = [[a, b, 1, 2, 3]].

Есть ли чистый способ сделать этот вывод только одним решением?


list prolog prolog-cut
person Enoon    schedule 15.11.2012    source источник

Ответы (4)


arrow_upward
3
arrow_downward

Уже есть 3 SO-ответа, но я не могу согласиться ни с одним! Все они неверны.

Как избавиться от избыточных решений

Рассмотрим три факта в вашем определении:

mergeL([],[],[]).
mergeL(List, [], List).
mergeL([], List, List).

Все они преуспевают для mergeL([],[],[]), который является источником ваших увольнений. Второй и третий факты связаны с тем, что List является непустым списком. Итак, давайте добавим это к определению:

mergeL([],[],[]).
mergeL(List, [], List) :- List = [_|_].
mergeL([], List, List) :- List = [_|_].

Это устраняет избыточные решения. Нет необходимости в разрезе, чтобы удалить избыточные решения. Однако сокращения, представленные в другом SO-ответе, могут скрывать решения. Для запроса mergeL(Xs,YS,Zs) есть ровно одно решение для урезанной версии, а их должно быть бесконечно много.

Как устранить оставшиеся точки выбора

Тем не менее, есть некоторый смысл в использовании сокращений: они могут удалить одну точку выбора. Но такой разрез должен быть защищен соответствующим образом, например:

mergeL(Xs, Ys, Zs) :-
   ( Xs == [], Ys == [] -> !
   ; Zs == [] -> !
   ; true
   ),
   Xs = [], Ys = [], Zs = [].
...

Я не уверен, стоит ли это усилий... Реализация может предложить это более эффективно. Подробнее об этом см. это и это.

Хвостовая рекурсия

Гораздо интереснее для вас, наверное, изменение последнего правила. Скорее следует читать:

mergeL([X|Rest],[Y|Rest2], [XY|Res2]) :-
   append(X,Y,XY),
   mergeL(Rest, Rest2, Res2).

Это позволяет избежать временного выделения пространства локального стека. Так что это однозначно оптимизация. Но оптимизация, которая не повредит логическому чтению вашего предиката.

На моем 32-битном ноутбуке 2009 года (почти паровом) и SWI 6.3.3-40-g064f37b:

Оригинальная версия:

?- N is 2^20, length(L,N), maplist(=([]),L), time(mergeL(L,L,J)).
% 2,097,206 inferences, 5.232 CPU in 5.250 seconds (100% CPU, 400851 Lips)

Хвостовая рекурсивная версия:

?- N is 2^20, length(L,N), maplist(=([]),L), time(mergeL(L,L,J)).
% 2,097,152 inferences, 0.525 CPU in 0.526 seconds (100% CPU, 3997337 Lips)

Э-это коэффициент 10.

А теперь с более длинными списками: Хвостовая рекурсивная версия:

?- N is 2^22, length(L,N), maplist(=([]),L), time(mergeL(L,L,J)).
% 8,388,608 inferences, 4.228 CPU in 4.237 seconds (100% CPU, 1984272 Lips)

по сравнению с исходным порядком:

?- N is 2^22, length(L,N), maplist(=([]),L), time(mergeL(L,L,J)).
% 1,765,930 inferences, 1.029 CPU in 1.033 seconds (100% CPU, 1716119 Lips)
ERROR: Out of local stack

Таким образом, для заполнения локального стека было выполнено только 1,7Ми. Это в первую очередь космическая проблема! Если у вас больше памяти, чем у меня, просто увеличьте N is 2^22!

person false    schedule 15.11.2012
comment
Спасибо за очень развернутый ответ. :) Вопрос: в разделе Tail recursiveness вы предлагаете поменять местами порядок добавления и слияния, я прав? Я не знал, что порядок имеет значение! - person Enoon; 15.11.2012
comment
@Enoon: Вы должны переключить их, определенно! Рекурсивный вызов должен быть последним. В общем можно сказать так: если у нас есть две детерминированные цели, рекурсивную поставьте последней. При условии, что это не повлияет на завершение (которого в данном случае нет). - person false; 15.11.2012

arrow_upward
1
arrow_downward

Запрос с первым пустым списком, т. е. ?-merge([],,), будет соответствовать первому и третьему предложению. Аналогично, запрос со вторым пустым списком будет соответствовать первому и второму предложению. Вот почему вы получаете точки выбора и, следовательно, дублируете решения.

Если вы поместите сокращение в тело первого предложения, все будет в порядке:

merge([],[],[]) :- !.
person twinterer    schedule 15.11.2012
comment
Спасибо. То есть сокращение — это способ сказать, что этот пункт больше не используется? - person Enoon; 15.11.2012
comment
Он говорит, что нет никакой другой альтернативы, чтобы попробовать. - person twinterer; 15.11.2012

arrow_upward
1
arrow_downward

Я бы совершил последний выбор:

mergeL([X|Rest],[Y|Rest2], [XY|Res2]) :-
    mergeL(Rest, Rest2, Res2), !, append(X,Y,XY).

также ответ @twinterer работает!

person CapelliC    schedule 15.11.2012

arrow_upward
1
arrow_downward

Вы можете добавить вырезы:

mergeL([],[],[]) :- !.
mergeL(List, [], List):- !.
mergeL([], List, List):- !.
mergeL([X|Rest],[Y|Rest2], [XY|Res2]) :-
   mergeL(Rest, Rest2, Res2),
   append(X,Y,XY).
person joel76    schedule 15.11.2012