How to find the cardinality of a set in Prolog?

Question

I 'm trying to find the cardinality of a set in Prolog. As is known, a set can haven't elements repeated. I tried this.

cardinal([], 0).
cardinal([_|Tail], N):-
    removeRepeated(Tail, ListWithoutRepeated),
    cardinal(ListWithoutRepeated, N1),
    N is N1 + 1.

----------------------------------------------------
consult:                                            

?- cardinal([1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5], N).
   N = 6

But the correct answer is N = 5. Obviously I'm counting only the items in the tail and ignored if the head is repeated in the tail. So I tried something like this. That is to add the head to tail and repeat the above process.

join([], L, [L]).
join([Head|Tail], L, [Head|Tail2]):-
   join(Tail,L, Tail2).

cardinal([], 0).
cardinal([Head|Tail], N):-
    join(Tail,Head, List),
    removeRepeated(List, ListWithoutRepeated),
    cardinal(ListWithoutRepeated, N1),
    N is N1 + 1.

But when you query an infinite loop is generated. Can someone help me solve this o can anyone help me out how can I write prolog statement for this?

Edit attached removeRepeated

removeRepeated([],[]).
removeRepeated([Head|Tail],ListWithoutRepeated):-
    member(Head,Tail),
    !,
    removeRepeated(Tail,ListWithoutRepeated).
removeRepeated([Head|Tail],[Head|ListWithoutRepeated]):-
    removeRepeated(Tail,ListWithoutRepeated).

----------------------------------------------------
consult:                                            

?- removeRepeated([1,1,1,1,2,2,2,3,3,3,4,4,4,8], N).
   N = [1, 2, 3, 4, 8]

Answer 1

Teh codez:

set_cardinality(Xs, N) :-
   list_nub(Xs, Ys),
   length(Ys, N).

using list_nub/2. It is possible to improve termination of this definition, since it only terminates if the length of Xs is fixed. But before we go into this, let's look at your definitions.

Relational names

Try to use names that actually reflect what the relations you define are about. Both cardinal/2 and removeRepeated/2 will leave one with the impression that the former is a relation between cardinals, and the latter does something. But relations don't do anything. OK, they "are". Or, they "relate". But these are not really action-filled verbs.

Now for your first definition cardinal/2. Actually, I tried not to read it. Particularly, because it contains the number one reason for programmer's vertigo — which is

Recursion

Yes, this makes me very dizzy too. Luckly, your question is about Prolog, and in Prolog we can often hide a lot of things and still get lots of insight. Here is what I looked at first (the things I did not look at are striked through).

cardinal([], 0).
cardinal([_|Tail], N):-
    removeRepeated(Tail, ListWithoutRepeated),
    cardinal(ListWithoutRepeated, N1),
    N is N1 + 1.

The fact, I can handle. Ok, the empty list corresponds to zero. Sounds fine to me. But then, there is the head of this rule: It reads:

N is independent of the first element of the list.

That is: For cardinal([1,2],N) and cardinal([2,2],N) you will get the very same N values. How can this be correct?

removeRepeated/2 (list_nub/2 might be a more relational name) works nicely for queries that have a ground first argument:

?- removeRepeated([1,2], X).
   X = [1,2].
?- removeRepeated([1,2],[1,2]).
   true.

However, it unexpectedly fails for:

?- removeRepeated([X,2],[1,2]).
   false.    % not relational
?- X = 1, removeRepeated([X,2],[1,2]).
   X = 1.

So while the specialization succeeds, the query that is more general fails. This is a clear indication that removeRepeated/2 is not a pure relation. For an implementation that works as expected, see list_nub/2.

Answer 2

First of all: there is a library lists that ships with SWI-Prolog (and some other versions) containing the list_to_set/2 that you can use to construct a Set: a sorted list where every item occurs only once. For example:

?- list_to_set([1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5],S),length(S,N).
S = [1, 2, 3, 4, 5],
N = 5.

Now to comment on your (first) solution. The problem is that you call removeRepeated/2 unknowing what item is currently in the head of the list in cardinal/2. A small fix would be to rewrite the removeRepeated/2 predicate to removeRepeated/3:

removeRepeated([],_,[]).
removeRepeated([H|T],H,U) :-
    !,
    removeRepeated(T,H,U).
removeRepeated([X|T],H,[X|U]) :-
    removeRepeated(T,H,U).

And call it with:

cardinal([], 0).
cardinal([H|Tail],N):-
    removeRepeated(Tail,H,ListWithoutRepeated),
    cardinal(ListWithoutRepeated, N1),
    N is N1 + 1.

Mind however it is still inefficient because:

1. the predicate has O(n²) time complexity; and
2. you do not use an accumulator such that the compiler can use tail recursion.

Answer 3

A solution using only standard predicates is to sort the list and then compute its length:

| ?- sort([1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5], Set), length(Set, Cardinality).

Cardinality = 5
Set = [1,2,3,4,5]

yes

Assuming a decent implementation fo the sort/2standard predicate, the time complexity of this solution should be (worst case) O(N*log(N)) + O(N).