1

I would like to write in prolog "check if one list has the same elements" e.g list[a,a,a,a] is true. list[a,c,a,a] is false. How can I do so?

oralo
  • 17
  • 1
  • 6
  • I think you have a similar issue here : http://stackoverflow.com/questions/16408310/prolog-element-is-a-list-member-check – Francois Borgies Feb 19 '14 at 13:19
  • no this is not the same issue. i would like to check if one list has all elements same. thanks e.g list[a,a,a,a] is true. – oralo Feb 19 '14 at 13:24
  • If you solved your problem consider closing this question marking the answer with the sticky, as accepted answer – llrs Feb 19 '14 at 14:26

4 Answers4

5

It can be done with one, simple predicate:

same([]).   % You only need this one if you want the empty list to succeed
same([_]).
same([X,X|T]) :- same([X|T]).

Results:

| ?- same([a,b,a,a]).

no
| ?- same([a,a,a,a]).

true ? ;

no
| ?- same([]).

yes

ADDENDUM 1

Changing the order of the clauses so that the base cases are first allows:

| ?- same(L).

L = [] ? ;

L = [_] ? ;

L = [A,A] ? ;

L = [A,A,A] ? ;
...

ADDENDUM 2

Another approach, using DCG, might be:

same(_) --> [].
same(X) --> [X], same(X).

Then:

| ?- phrase(same(_), [a,b,a,a]).

no
| ?- phrase(same(_), [a,a,a,a]).

true ? a

(1 ms) no
| ?- phrase(same(X), L).

L = [] ? ;

L = [X] ? ;

L = [X,X] ? ;

L = [X,X,X] ? ;
...
lurker
  • 56,987
  • 9
  • 69
  • 103
  • +1 for the best recursive answer so far. – magus Feb 19 '14 at 14:37
  • 1
    1mo: Does it make sense to produce no answer for `same(L)`? 2do: Many systems are not able to execute this efficiently, since indexing does not go that deep. So `same/1` will create *n* choicepoints.... – false Feb 20 '14 at 15:50
  • @false - thanks and very good points. For `same(L)` I changed the order of the clauses. I'll need to think about your second point further. – lurker Feb 20 '14 at 16:04
3
same(L) :-
   maplist(=(_),L).

?- maplist(=(_),L).
   L = []
;  L = [_A]
;  L = [_A,_A]
;  L = [_A,_A,_A]
;  L = [_A,_A,_A,_A]
;  L = [_A,_A,_A,_A,_A]
;  L = [_A,_A,_A,_A,_A,_A]
;  ... .

See also this answer.

false
  • 10,264
  • 13
  • 101
  • 209
2

Okay, now that I understood the request whats about this:

compare([X|Y]):-help(Y,X).
compare([]).

help([],_).
help([Y|X],Y) :- help(X,Y).
DiCaprio
  • 823
  • 1
  • 7
  • 24
  • 1
    You can get the last line even shorter using pattern matching: `help([Y|X],Y) :- help(X,Y).` – traitor Feb 19 '14 at 14:03
  • 1
    `compare(X)` will start enumerating with `X = [_]`, `X = [_,_]`... but `X = []` will not be produced which is a bit unintuitive. – false Feb 20 '14 at 15:52
  • sure, but I think it doesn't need to. the recursion is in help, not in compare. The compare([]) kind of base case is just so the empty list gets accepted as well. – DiCaprio Feb 20 '14 at 18:54
1

Using the built-in list_to_set/2, this can be done in a single line:

?- list_to_set([a,a,a,a],[_]).
true.

?- list_to_set([a,a,c,a],[_]).
false.

The conversion of a list to a set removes duplicates.. so if you are left with a list that can be unified to one item [_], then there are no duplicates.

If the list has duplicates, there will be > 1 item in the set, and the [_] predicate unification will fail.

This obviously won't work on an empty list - a separate rule will be needed for that.

magus
  • 1,347
  • 7
  • 13
  • 1
    But removing duplicates costs as much as sorting, that is O(*n* ld *n*) instead of the necessary O(*n*). – false Feb 20 '14 at 15:48