Эффективное решение этой проблемы не является тривиальным для новичка. Предполагая, что элементы списка измельчены, мы можем начать с того, что при сортировке списка будут объединены все элементы, которые имеют первый аргумент в составном термине obj/2. Например:
| ?- sort([obj(x,y),obj(x,z),obj(a,b),obj(b,c)], S).
S = [obj(a, b), obj(b, c), obj(x, y), obj(x, z)]
yes
sort/2 - это стандартный встроенный предикат. Любая приличная система Prolog должна реализовывать это со сложностью O (n * log (n)). После сортировки мы можем просмотреть список, который мы можем в O (n) отфильтровать:
filter(List, Filtered) :-
sort(List, Sorted),
walk(Sorted, Filtered).
walk([], []).
walk([obj(X,Y)| Sorted], Filtered) :-
walk(Sorted, X, obj(X,Y), Filtered).
walk([], _, Element, [Element]).
walk([obj(X,_)| Sorted], X, _, Filtered) :-
!,
delete(Sorted, X, Rest),
walk(Rest, Filtered).
walk([obj(X,Y)| Sorted], _, Element, [Element| Filtered]) :-
walk(Sorted, X, obj(X,Y), Filtered).
delete([], _, []).
delete([obj(X,_)| Sorted], X, Rest) :-
!,
delete(Sorted, X, Rest).
delete(Rest, _, Rest).
Пример вызова:
| ?- filter([obj(x,y),obj(x,z),obj(a,b),obj(b,c)], Filtered).
Filtered = [obj(a, b), obj(b, c)]
yes
выглядит хорошо, но мы должны сделать больше комплексное тестирование. Мы можем определить свойство, которому должны удовлетворять все решения-предикаты filter/2:
property(List, Filtered) :-
filter(List, Filtered),
% all elements of the output list must
% be in input list
forall(
member(X, Filtered),
member(X, List)
),
% no two elements in the output list
% should share the first argument
\+ (
select(obj(X,_), Filtered, Rest),
member(obj(X,_), Rest)
),
% all elements in the input list whose
% first argument is not repeated must
% be in the output list
\+ (
select(obj(X,Y), List, Rest),
\+ member(obj(X,_), Rest),
\+ member(obj(X,Y), Filtered)
).
Теперь мы можем использовать реализацию тестирования на основе свойств , такую как Logtalk lgtunit Реализация QuickCheck. Но есть подвох. Тестирование на основе свойств требует, чтобы мы могли создавать списки с элементами obj/2. Решение мы обманываем! Сначала мы делаем преобразование syntacti c из obj(X,Y) в X-Y. Это преобразование не меняет семантику тестируемого предиката:
filter(List, Filtered) :-
sort(List, Sorted),
walk(Sorted, Filtered).
walk([], []).
walk([X-Y| Sorted], Filtered) :-
walk(Sorted, X, X-Y, Filtered).
walk([], _, Element, [Element]).
walk([X-_| Sorted], X, _, Filtered) :-
!,
delete(Sorted, X, Rest),
walk(Rest, Filtered).
walk([X-Y| Sorted], _, Element, [Element| Filtered]) :-
walk(Sorted, X, X-Y, Filtered).
delete([], _, []).
delete([X-_| Sorted], X, Rest) :-
!,
delete(Sorted, X, Rest).
delete(Rest, _, Rest).
Мы применяем то же преобразование syntacti c к предикату property/2:
property(List, Filtered) :-
filter(List, Filtered),
% all elements of the output list must
% be in input list
forall(
member(X, Filtered),
member(X, List)
),
% no two elements in the output list
% should share the first argument
\+ (
select(X-_, Filtered, Rest),
member(X-_, Rest)
),
% all elements in the input list whose
% first argument is not repeated must
% be in the output list
\+ (
select(X-Y, List, Rest),
\+ member(X-_, Rest),
\+ member(X-Y, Filtered)
).
Мы можем Теперь протестируйте, используя цель:
| ?- lgtunit::quick_check(
property(
+list(pair(char,char)),
-list(pair(char,char))
)
).
% 100 random tests passed
% starting seed: seed(25256,26643,1563)
yes
Примечание: в определении предиката property/2 мы предполагаем, что стандартные предикаты списка member/2 и select/3 де-факто доступны в user ( то есть на переводчике верхнего уровня). Если это не так, добавьте к их вызовам list::.