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

我有这样的对象列表

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

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

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

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

对于初学者来说，有效地解决这个问题并非易事。假设列表的元素是地面的，我们可以首先注意到对列表进行排序会将共享列表中第一个参数的所有元素聚集在一起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

The 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 https://logtalk3.readthedocs.io/en/latest/devtools/lgtunit.html#quickcheck快速检查实施。但有一个问题。基于属性的测试要求我们能够生成列表obj/2元素。解决办法，我们作弊！首先我们做一个句法的转变自obj(X,Y) to 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 and select/3列表谓词可用于user（即在顶级解释器处）。如果情况并非如此，请在呼叫前加上前缀list::.