compare element in a list prolog

hi all,
im new to prolog

and im trying to make this pred.

compare[a,a,a,a].
yes


compare[a,e,a,t].
no


so if the element of the list are the same then its a yes  if not then its a
 no

how can i do this?

i was trying this but it didnt work

compare([H|T]):-
element(H, [H|T]).
element(H, [H|T]):-
element(H,T).

but this is wronge.  anyone can help me plz?

TIA

kimos wrote:
> hi all,
> im new to prolog
>
> and im trying to make this pred.
>
> compare[a,a,a,a].
> yes
>
>
> compare[a,e,a,t].
> no
>
>
> so if the element of the list are the same then its a yes  if not then its
 a no
>
> how can i do this?
>
> i was trying this but it didnt work
>
> compare([H|T]):-
> element(H, [H|T]).
> element(H, [H|T]):-
> element(H,T).
>
> but this is wronge.  anyone can help me plz?
>
> TIA

I take it your question is: "How do I say 'All of the members of a
list of variable-free terms are the same.'?"

1. Surely all of the members of a list are the same if no two of them
differ.

2. No two members of the empty list differ because the empty list has
no members.

3. Therefore all of the members of the empty list are the same, i.e.,

same_members(L) :- L = what?

4. If  L is a non-empty list of variable-free terms all of which are
the same
and  X is the first member of L then all of the members of [X|L]
are the same, i.e.,

same_members([X|L]) :- L = what?


bill

On Thu, 23 Sep 2004, kimos wrote:

> hi all,
> im new to prolog
>
> and im trying to make this pred.
>
> compare[a,a,a,a].
> yes
>
>
> compare[a,e,a,t].
> no
>
>
> so if the element of the list are the same then its a yes  if not then its
 a no
>
> how can i do this?
>
So what you want is a predicate that tests whether all the elements in a
list are the same?

As usual with this sort of thing, tbink logically about it:

All the elements of the empty list are the same (since there aren't any).
All the elements of a list consisting of just one element are the same.
All the elements of a list consisting of two elements are the same if all
the elements of its tail are the same and the first element is the same
as the second element.

Is there anything which is not obvious in the above? If not, why can't you
write a Prolog program for it, since the above translated directly to a
Prolog program.

Matthew Huntbach

Dear Matthew,

> As usual with this sort of thing, tbink logically about it:
>
> All the elements of the empty list are the same (since there aren't any).
> All the elements of a list consisting of just one element are the same.
> All the elements of a list consisting of two elements are the same if all
> the elements of its tail are the same and the first element is the same
> as the second element.

Actually, "same" is undefined for less than two items.

Best,

Bill

kimos wrote:
> hi all,
> im new to prolog
>
> and im trying to make this pred.
>
> compare[a,a,a,a].
> yes
>
>
> compare[a,e,a,t].
> no
>
>
> so if the element of the list are the same then its a yes  if not then its
 a no
>
> how can i do this?
>
> i was trying this but it didnt work
>
> compare([H|T]):-
> element(H, [H|T]).
> element(H, [H|T]):-
> element(H,T).
>
> but this is wronge.  anyone can help me plz?

First name the predicate to "allsame" - "compare" doesn't express
clearly enough what you want.

How about the following rather straithforward definition in logic:

allsame(L) iff (all X in L and all Y in L -> X == Y)

or equivalently

allsame(L) iff not (exists X in L and exists Y in L and X \==Y)


Now in Prolog this becomes:

allsame(L) :- \+ (member(X,L), member(Y,L), X \==Y).

If your gut feeling (or your application) tells you that the cases L is
empty or a singleton should be treated in a special way, just do it.


And here is one more way:

allsame(L) :- sort(L), L = [_].  % now an empty list is not allsame !


I am only posting these so you would see solutions that do not require
you to write code that explicitly traverses the list, but uses libraries
and standard built-ins :-)

Cheers

Bart Demoen

In article <1096050952.725666@seven.kulnet.kuleuven.ac.be>, Bart Demoen wrote:
> kimos wrote:

> 	allsame(L) iff not (exists X in L and exists Y in L and X \==Y)
>
>
> Now in Prolog this becomes:
>
>     allsame(L) :- \+ (member(X,L), member(Y,L), X \==Y).

I thought equality is transitive :-)  So there is only the need to compare o
ne
arbitrary member with all the others:

allsame([H|T]) :- \+ (member(X,L), H \== X).

This version uses the library _and_ is efficient. The above is order N^2
and using sort/2 is order NlogN. Of course you still need to think what
to do about allsame([]).

Cheers --- Jan

Matthew Huntbach wrote:
>
>
> On Thu, 23 Sep 2004, kimos wrote:
> 
> So what you want is a predicate that tests whether all the elements in a
> list are the same?
>
> As usual with this sort of thing, tbink logically about it:
>
> All the elements of the empty list are the same (since there aren't any).
> All the elements of a list consisting of just one element are the same.
> All the elements of a list consisting of two elements are the same if all
> the elements of its tail are the same and the first element is the same
> as the second element.
>
> Is there anything which is not obvious in the above?

Hmm.

> All the elements of the empty list are the same (since there aren't any).

no_elements_differ([]).

Agreed.

> All the elements of a list consisting of just one element are the same.

no_elements_differ([X]).

Agreed.

> All the elements of a list consisting of two elements are the same if all
> the elements of its tail are the same and the first element is the same
> as the second element.

no_elements_differ([X,Y]) :- ... ?

Even if  you had said

> All the elements of a list consisting of two *or more* elements are
the same if all
> the elements of its tail are the same and the first element is the same
> as the second element.

it is might not be clear to a Prolog newcomer exactly what "its tail"
refers to.

All the elements of a list consisting of two or more elements are the
same if
the first element is the same as the second element
and
all the elements of the list that remains after the first element is
deleted are the same.

translates readily into

no_elements_differ([X1,X2|L]) :- X1==X2, no_elements_differ([X2|L]).

But saying only that much is tantamount to begging what I am sure is
the real question
for most Prolog newcomers, namely, how, starting with a blank slate, do
I arrive at language
that translates readily into Prolog? All I can suggest is that that
skill is the essence
of Prolog programming and, as such, only comes from continued practice.

billh
--

Dear billh,

>   But saying only that much is tantamount to begging what I am sure is
> the real question
> for most Prolog newcomers, namely, how, starting with a blank slate, do
> I arrive at language
> that translates readily into Prolog? All I can suggest is that that
> skill is the essence
> of Prolog programming and, as such, only comes from continued practice.

That makes it sound worse than it is. It also applies to any programming
language. (Actually, it is easier for Prolog, since you can start with
logic.)

The current problem follows a common pattern, and a common method, for
processing lists. Do a case by case analysis. For recursion, identify
the base case or cases, and the recursive case or cases. (And, BTW, any
beginner who faces this problem should know what the tail of a list is.
Otherwise, they do not even know what a list is.)

Anyway, to recast the predicate:

no_elements_differ([]).              % Base case 1
no_elements_differ([X]).             % Base case 2
no_elements_differ([X, X | Xs]) :-
no_elements_differ([X | Xs]).    % Recursive case.

What makes this a little tricky, and a good homework solution, is that
there are two base cases instead of one, and the representation of the
list in the recursive case looks at the first two elements instead of
just the head. It also requires some thought to get the original idea.
Here is a perhaps less thoughtful version.

no_elements_differ([]).              % No elements differ in the empty
list.
no_elements_differ([X | Xs]) :-      % No elements differ in a list if
its tail
contains_nothing_but(Xs, X).     % contains nothing but its head.


contains_nothing_but([],_).             % The empty list contains
nothing.
contains_nothing_but([X | Xs], X) :-    % A list contains nothing but it
head
contains_nothing_but(Xs, X).        % if its tail does, too.

A typical case-by-case analysis, with an auxiliary predicate in the
typical recursive pattern.

Best regards,

Bill S.

Bill Spight wrote:
> Dear billh,
>
> 
>
>
> That makes it sound worse than it is.

Indeed. Since most of us normally have to be able to see what we
intend to say
before we can say it, I probably should at least have said that drawing
pictures
is sometimes a great help.

> It also applies to any programming language.

Or to riding bicycles or flying kites, I suppose, but that was not
the idea I was trying to convey. I do not doubt that skill at
formulating problems
by means of sentences which have the form of Horn Clauses applies to
all sorts of
problems, so if by "it also applies to any programming language" you
mean it applies
to designing programs in any programming language, I agree, but AFAIK
it applies *directly* only to Prolog programming.

I would question, for example, that the skill of describing a problem
by using only sentences
that translate directly into Prolog is the essence of COBOL programming.

> The current problem follows a common pattern, and a common method, for
> processing lists.

The *solution" to the current problem follows a common pattern and a
common method for processing lists, a fact which would not necessarily
be obvious to a
Prolog newcomer who is looking for a solution.

> Do a case by case analysis. For recursion, identify
> the base case or cases, and the recursive case or cases.

That is a bit like advising an aspiring playwright to invent some
characters, devise a plot, and make up some interesting dialog.

Becoming proficient at that takes years of practice


> And,  BTW, any
> beginner who faces this problem should know what the tail of a list is.
> Otherwise, they do not even know what a list is.

They'd better.

But I believe "tail" is defined i.t.o. "list", in which case it does
not follow
that one does not know what a list is if one does not know what a tail is.

And as long as there is nothing to prevent anyone from writing

[ X1, X2 | Tail ]

I will continue to believe that clear language is superior to jargon.

>
> Anyway, to recast the predicate:
>
> no_elements_differ([]).              % Base case 1
> no_elements_differ([X]).             % Base case 2
> no_elements_differ([X, X | Xs]) :-
>     no_elements_differ([X | Xs]).    % Recursive case.
>

This actually expresses the idea "no pair of successive elements fails
to unify", as in

?- no_elements_differ([1,1,1,Y]).
Y = 1
One answer.

In fact, the OP did not specifically mention that his "elements" were
variable-free terms, so, following O'Keefe, I thought it safer to use
the "robust" form

no_elements_differ([X1, X2 | Xs]) :-
X1==X2,
no_elements_differ([X2 | Xs]).    % Recursive case.

which gives

?- no_elements_differ([1,1,1,Y]).
No.

--
billh

On Sat, 25 Sep 2004, student wrote:
> Matthew Huntbach wrote:
 

> Hmm.

...
 

>   no_elements_differ([X,Y]) :- ... ?

OK, that's my mistake, I should have written "at least two".

>  Even if  you had said
 

> it is might not be clear to a Prolog newcomer exactly what "its tail" refe
rs
> to.

It would seem to me to be bizarre to teach someone Prolog, ask them to do
exercises using lists, but not give them the very basic vocabulary of lists.
If someone has gone to the bother of explaining Prolog to the point that the
novice can write syntactically correct programs, I would have thought they
could also have explained the terms "head" and "tail". After all, it is
a core part of Prolog syntax that we have a pattern [X|Y]. What other words
would we use for X and Y here?

> All the elements of a list consisting of two or more elements are the same
> if
>   the first element is the same as the second element
>   and
>   all the elements of the list that remains after the first element is
> deleted are the same.
>
> translates readily into
>
>   no_elements_differ([X1,X2|L]) :- X1==X2, no_elements_differ([X2|L]).

OK, but the sentence becomes more convoluted if we disallow the term "tail".
I also don't like the word "deleted" here, since it suggests we have
changed the value of the variable holding the list. A lot of the problem
novices have with Prolog is that they are unable to shake off the way
of thinking which comes from conventional programming languages where
variables are containers whose value can be rewritten.

> But saying only that much is tantamount to begging what I am sure is the
> real question for most Prolog newcomers, namely, how, starting with a blan
k
> slate, do I arrive at languag that translates readily into Prolog? All I c
an
> suggest is that that skill is the essence of Prolog programming and, as
> such, only comes from continued practice.

The same applies to programming in any language. Practice means you pick up
common usage patterns and these become second nature.

Writing simple recursive programs with lists in Prolog ought not to be a
taxing problem. In fact it is such a simple problem that it can be
readily automated (it happens that this is what I wrote my PhD on).
Experience from this newsgroup, however, suggests that many Prolog
novices *do* find it difficult. I find it intriguing that this should be
the case, and am sing an explanation from novices as to why it should
be so. That is why, as I have done here, I give a simple recursive
solution that a machine exploring the space of possible recursive Prolog
clauses could have come up with and ask why it is that this solution did not
come naturally to the novice.

Matthew Huntbach