CODEWITHSUNDEEP
prolog
codingisfun543
codingisfun543

Reputation: 29

Prolog check if list X has any duplicates

I have the function already but it is not working exactly as I want it to. The function I have is below..

isSet(List) :-
    \+ (
        select(Element, List, Tail),
        select(Element, Tail, _)
    ).

When I do isSet([1,2,3]) it gives me true which is expected. When I do isSet([1,1,2]) it gives me false which is also what I expect and is correct. My question is how can I pass a list that is already made? For example If I do X = [1,2,3] and than pass it as a argument like isSet(X) it should give me true but instead it generates an error.

What can I do to fix this?

Edit:

?- [db].
true.

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

?- isSet(X).
false.

?- X = (1,2,3).
X =  (1, 2, 3).

?- isSet(X).
false.

?- X = [1,1,2].
X = [1, 1, 2].

?- isSet(X).
false.

Upvotes: 1

Views: 756

Answers (4)

TA_intern
TA_intern

Reputation: 2422

The correct way to check if a list is a set in Prolog is to sort it, removing duplicates, and check if its length is still the same. This is correct for all kinds of reasons, from very pragmatic (easy to program) to purely theoretic (it is the only robust approach to checking if a singly linked list is a set).

"But this is not what I asked" sure it isn't.

is_set(List) :-
    sort(List, Sorted),
    length(List, N),
    length(Sorted, N).

Don't throw Bloom filters and the like at me, at least not without proper justification.

To address the comments by @IsabelleNewbie, if you really want to use attributed variables to make sure that a list will forever remain a set under unification, you would do:

all_different([]).
all_different([H|T]) :-
    maplist(dif(H), T),
    all_different(T).

but this is a different thing altogether. You also shouldn't use it unless you want to take a list with variables and make sure no two elements in this list will ever unify. You get answers like this (in SWI-Prolog):

?- all_different(X).
X = [] ;
X = [_] ;
X = [_A, _B],
dif(_A, _B) ;
X = [_A, _B, _C],
dif(_A, _B),
dif(_A, _C),
dif(_B, _C) ;
X = [_A, _B, _C, _D],
dif(_A, _B),
dif(_A, _D),
dif(_A, _C),
dif(_B, _D),
dif(_B, _C),
dif(_C, _D) .

I suspect you can find this code in other places too.

Upvotes: 2

Isabelle Newbie
Isabelle Newbie

Reputation: 9378

As there are discussions on how to best define the concept of "sets represented by lists", I humbly submit the following:

real_actual_set([]).
real_actual_set([X | Xs]) :-
    nonmember_of(X, Xs),
    real_actual_set(Xs).

nonmember_of(_X, []).
nonmember_of(X, [Y | Ys]) :-
    dif(X, Y),
    nonmember_of(X, Ys).

This is pure and works properly even in the presence of variables, including the most general query, and any lists containing variables that we would try to bind later:

?- real_actual_set([1, 2, 3]).
true .

?- real_actual_set([1, 1, 2]).
false.

?- real_actual_set([A, B, C]).
dif(A, C),
dif(A, B),
dif(B, C).

?- real_actual_set([A, A, B]).
false.

?- real_actual_set(Set).
Set = [] ;
Set = [_2222] ;
Set = [_2672, _2678],
dif(_2672, _2678) ;
Set = [_2970, _2976, _2982],
dif(_2970, _2982),
dif(_2970, _2976),
dif(_2976, _2982) ;
Set = [_3388, _3394, _3400, _3406],
dif(_3388, _3406),
dif(_3388, _3400),
dif(_3388, _3394),
dif(_3400, _3406),
dif(_3394, _3400),
dif(_3394, _3406) .

?- real_actual_set([A, B, C]), A = 1, B = 2, C = 3.
A = 1,
B = 2,
C = 3.

?- real_actual_set([A, B, C]), A = 1, B = 1, C = 3.
false.

This is quadratic, so it's "less performant" than other approaches. But as John Ousterhout is quoted, "The best performance improvement is the transition from the nonworking state to the working state."

Upvotes: 3

Peter Ludemann
Peter Ludemann

Reputation: 1005

SWI-Prolog allows the form $Xs to access a variable from a previous query. E.g.:

?- Xs=[1,2,3].
Xs = [1, 2, 3].

?- isSet($Xs).
Xs = [1, 2, 3].

?- isSet([1|$Xs]).
false.

BTW, it's slightly more efficient to write your code like this (and I suggest using Rest rather than Tail: the latter is typically used in the form List=[Head|Tail]):

isSet(List) :-
  \+ ( select(Element, List, Rest),
       member(Element, Rest)
     ).

Also, you can't write a list like this: X = (1,2,3) ... that's actually something different:


?- write_canonical((1,2,3)), nl.
','(1,','(2,3))
true.

Upvotes: 4

Isabelle Newbie
Isabelle Newbie

Reputation: 9378

For example If I do X = [1,2,3] and than pass it as a argument like isSet(X) it should give me true but instead it generates an error.

You should show us exactly what you tried!

This works:

?- Xs = [1, 2, 3], isSet(Xs).
Xs = [1, 2, 3].

Note that both parts (binding Xs and testing it) are in one query. Maybe you tried entering them separately:

?- Xs = [1, 2, 3].
Xs = [1, 2, 3].

?- isSet(Xs).
false.

This doesn't work because the value of Xs is not saved from one query to the next. This still isn't an error, though. However, it is not great behavior because failing for isSet(Xs) seems to imply that no sets exist at all.

Upvotes: 1

Related Questions