CODEWITHSUNDEEP
prolog
Anand Bhararia
Anand Bhararia

Reputation: 11

prolog finding cardinality of a list

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.

Upvotes: 1

Views: 124

Answers (2)

Paulo Moura
Paulo Moura

Reputation: 18663

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

Upvotes: 1

Scott Hunter
Scott Hunter

Reputation: 49803

It might be better to build a list of distinct elements & yield its length for the cardinality:

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

Upvotes: 0

Related Questions