查找列表的基数

Question

我已经写了Prolog代码来查找列表的基数，即不同元素的数量。它给出了正确的输出，但是它运行了多次，我似乎无法理解。我已经使用了调试器，但无法理解出了什么问题

member(A, [A|_]).
member(A, [_|L]) :- member(A, L).

crdnlty([],0).
crdnlty([A|R],N) :-
    (
      \+ member(A, R),
      crdnlty(R, N1),
      N is N1+1
    );
    (
      member(A, R),
      crdnlty(R, N)
    ).

成员检查剩余列表中是否存在A。如果它不存在，即它是该元素基数的最后一次出现增加1。

例如，如果我运行查询

crdnlty([1,2,1,1], N).

返回

N = 2 ;
N = 2 ;
false.

但它应该返回

N = 2 ;
false.

Answer 1

这不是答案，只是一个不适合评论的测试建议。

除了不需要的重复解决方案之外，还有关于如何测试谓词的问题。一个简单的替代解决方案是使用ISO Prolog标准谓词sort/2和事实上的标准谓词length/2。替代解决方案可以是：

cardinality(List, Cardinality) :-
    sort(List, Sorted),
    length(Sorted, Cardinality).

我们可以使用此替代解决方案来定义您的解决方案必须遵守的property，这可以快速检查您的解决方案（现在忽略不需要的不确定性）：

property(List) :-
    once(crdnlty(List, C)),
    sort(List, S),
    length(S, C).

使用Logtalk的lgtunit工具提供的QuickCheck实现（您可以在大多数Prolog系统中运行；在此示例中，我将使用GNU Prolog）：

$ gplgt
...

| ?- {lgtunit(loader)}.
...
% (0 warnings)

(578 ms) yes
| ?- lgtunit::quick_check(property(+list(integer)), [n(2000)]).            
% 2000 random tests passed

(1589 ms) yes

当然，QuickCheck可以显示错误，但不能证明没有错误。就是说，Logtalk的QuickCheck实现的一个独特功能是，它会在生成随机值之前尝试对指定类型进行平凡/角落的情况。这有助于确保随机测试不会遗漏明显的测试用例（如下所述）。

如果我们改为测试Scott Hunter提供的解决方案会怎样？

| ?- lgtunit::quick_check(property(+list(integer)), [n(2000)]).      
*     quick check test failure (at test 1 after 0 shrinks):
*       property([])

no

实际上，他的解决方案没有考虑到列表可能为空。假定这是一个错误，请添加缺少的子句：

crdnlty([], 0).

重新测试：

| ?- lgtunit::quick_check(property(+list(integer)), [n(2000)]). 
% 2000 random tests passed

(1509 ms) yes

Answer 2

建立一个不同元素列表并根据基数得出其长度可能会更好：

crdnlty([A|R],N) :- distinct(R,N,[A],1).

% distinct(L,N,DL,DN): There are N distinct values in list L+DL,
% assuming there are DN distinct values in list DL alone.
distinct([],N,_,N).
distinct([A|R],N,DL,DN) :- 
    (
      \+ member(A, DL),
      DN1 is DN+1,
      distinct(R, N, [A|DL], DN1)
    );
    (
      member(A, DL),
      distinct(R, N, DL, DN)
    ).