Пролог нахождение мощности списка

Question

Я написал код Пролога, чтобы найти количество элементов в списке ie количество различных элементов. Это дает правильный вывод, но он работает несколько раз, и я, кажется, не могу разобраться с этим. Я использовал отладчик, но не могу понять, что не так

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 в оставшемся списке.
если его нет ie это последнее вхождение этого элемента, то количество элементов увеличивается на 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).

. Мы можем использовать это альтернативное решение, чтобы определить свойство , которому должно соответствовать ваше решение, что позволяет QuickCheck ваше решение (игнорируя пока нежелательные не -determinism):

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

Использование реализации QuickCheck, предоставляемой инструментом lgtunit Logtalk (который вы можете запускать в большинстве систем 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 может показывать ошибки, но не может доказать их отсутствие. Тем не менее, отличительной особенностью реализации QuickTheck в Logtalk является то, что он пробует тривиальные / угловые случаи для указанных типов перед генерацией случайных значений. Это помогает гарантировать, что случайное тестирование не пропустит очевидные тестовые случаи (как мы проиллюстрируем далее).

Что произойдет, если вместо этого мы протестируем решение, предоставленное Скоттом Хантером?

| ?- 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)
    ).