Finding number of unique elements in the list

user_13782227 0
Viewed 77

I want to write a code which will return number of unique elements in the list. My idea is to check if head of the list is there in the list of uniqeue elemeents. If it is not, add it to the list and increment the counter and continue witht the remaining list. So, I tried out following:

count([],0).
count([X,T], N) :- 
    count([X,T], [], N). %initially list of unique elements is empty

count([X,T], U, N) :- % U is a list of unique elements
    (not(member(X, U)), append(U, X, U2));
    count(T, U2, N1),
    N is N1 + 1.

%------ helpers ------
member_(X,[Y|T]):-
    member_(X, T).
member_(X,[X|_]).

append([], Y, [Y]).  % append[] and Y to get Y.
append([H|X], Y, [H|Z]) :- append(X, Y, Z). % append [H|X] and Y to get [H|Z] if appending X and Y gives Z

But running above simply return false:

3 ?- count([1,2,3],N).
   Call: (10) count([1, 2, 3], _7714) ? creep
   Fail: (10) count([1, 2, 3], _7714) ? creep
false.

Why is this so?

prolog
1 Answers

But running above simply return false:

3 ?- count([1,2,3],N).
   Call: (10) count([1, 2, 3], _7714) ? creep
   Fail: (10) count([1, 2, 3], _7714) ? creep
false.

Why is this so?

Because there is no head of a clause that count([1,2,3],N) can match.

You have two clauses for count/2:

count([],0).             %%% clause 1
count([X,T], N) :- ...   %%% clause 2

Since [1,2,3] can't be unified with [], clause 1 is no match. But [1,2,3] can also not be unified with [X,T], thus clause 2 is also no match. Therefore, count([1,2,3],N) cannot be proven.

You can test this by asking

?- [X,T]=[1,2,3].
false.

What you need to recursively break down lists of arbitrary length is [X|T] instead. (Please test ?- [X|T]=[1,2,3]. to see how you could fix your code.)

user_65406060
Related