list - Prolog - 从列表中删除具有相同第一个值的对

Question

我有这样的对象列表

list([obj(x,y),obj(x,z),obj(a,b),obj(b,c)]).

我想删除那些共享相同第一个值的元素，以便我可以使用修改后的列表。在这种情况下，最终列表将如下所示

list([obj(a,b),obj(b,c)]

有人可以帮忙吗？我真的很挣扎这个。

Answer 1

对于初学者来说，有效地解决这个问题并非易事。假设列表的元素是接地的，我们可以首先注意到对列表进行排序会将所有共享 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 快速检查实现。但有一个问题。基于属性的测试要求我们能够使用 obj/2 生成列表。元素。解决办法，我们作弊!首先我们做一个 句法来自 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).

我们对 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:: .