prolog finding cardinality of a list

Question

I have written a Prolog code to find the cardinality of a list ie number of distinct elements. It gives correct output but it runs multiple times and I cant seem to get my head around it. I have used the debugger but cant understand whats wrong

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

member checks if A is present in the remaining list.
if its not present ie it is the last occurrence of that element cardinality is increased by 1.

for example if i run the query

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

it returns

N = 2 ;
N = 2 ;
false.

but it should return

N = 2 ;
false.

Did you try stepping through this execution to see why it comes up with 2 ways to derive the proof? — Scott Hunter
I've stepped through the execution and realized that the case where A=1 and R=[], multiple rules fit the case, so is it that Prolog will fit both of them and giving the answers derived from both the cases? @ScottHunter — Anand Bhararia

Paulo Moura Paulo Moura · Accepted Answer · 2020-02-21T15:52:51

This is not answer but just a testing suggestion that doesn't fit in a comment.

Besides the unwanted duplicated solution, there's also the question on how to test the predicate. A simple alternative solution is to use the ISO Prolog standard predicate sort/2 and the de facto standard predicate length/2. The alternative solution could be:

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

We can use this alternative solution to define a property that your solution must comply with that allows to QuickCheck your solution (ignoring for now the unwanted non-determinism):

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

Using the QuickCheck implementation provided by Logtalk's lgtunit tool (which you can run in most Prolog systems; in this example I will be using 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

Of course, QuickCheck can show bugs but cannot prove their absence. That said, a distinctive feature of Logtalk's QuickCheck implementation is that it tries trivial/corner cases for the specified types before generating random values. This help in ensuring that the random testing will not miss obvious test cases (as we illustrate next).

What happens if we test instead the solution provided by Scott Hunter?

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

no

In fact, his solution doesn't take into account that the list may be empty. Assuming that's considered a bug, adding the missing clause:

crdnlty([], 0).

Re-testing:

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

(1509 ms) yes

prolog finding cardinality of a list

2 Answers