Home > Archive > Prolog > September 2004 > compare element in a list prolog
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
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
| |
| student 2004-09-24, 3:58 am |
| 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
| |
| Matthew Huntbach 2004-09-24, 8:58 am |
|
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
| |
| Bill Spight 2004-09-24, 4:02 pm |
| 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
| |
| Bart Demoen 2004-09-24, 4:02 pm |
| 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
| |
| Jan Wielemaker 2004-09-25, 9:00 am |
| 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 one
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
| |
| student 2004-09-25, 9:00 am |
| 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
--
| |
| Bill Spight 2004-09-25, 3:57 pm |
| 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.
| |
| student 2004-09-27, 9:01 pm |
| 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
| |
| Matthew Huntbach 2004-09-28, 4:12 pm |
|
On Sat, 25 Sep 2004, student wrote:
> Matthew Huntbach wrote:
[color=darkred]
> Hmm.
....
[color=darkred]
> no_elements_differ([X,Y]) :- ... ?
OK, that's my mistake, I should have written "at least two".
> Even if you had said
[color=darkred]
> it is might not be clear to a Prolog newcomer exactly what "its tail" refers
> 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 blank
> slate, do I arrive at languag 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.
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 s ing 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
| |
| Cesar Rabak 2004-09-28, 9:27 pm |
| Matthew Huntbach escreveu:
>
>
> On Sat, 25 Sep 2004, student wrote:
>
>
>
[snipped
>
> 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.
As bizarre as it feels, I believe is a symptom of bigger problem. See below.
> 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?
Perhaps because you have squeezed the time for training in Prolog in a
very short time and those concepts get into some written material which
students never become proficent?
[snipped]
>
>
> The same applies to programming in any language. Practice means you pick up
> common usage patterns and these become second nature.
Here is where I find the present problem for Prolog: most of training
offered does not arrive at this stage of 'second nature'. In fact, as
the students are left in a middle state, as soon they are not in
obligation of using Prolog, they will not even consider it.
>
> 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).
Which perhaps point Prolog can now be a kind of lower level language and
a meta language like the one you developed in your PhD should be used
instead?¹
> 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.
>
I would summarize with a motto from the TWI method "If the apprentice
did not learn, the supervisor did not teach."
The difference, I think between Prolog and other languages it that in
the more 'mainstream' languages, they get to other work environments and
through peer contact finish their learning 'on the job' or 'on the fly'
whereas in Prolog not.
--
Cesar Rabak
[1] BTW, would you mind of giving us a pointer to your PhD thesis?
| |
| Bill Spight 2004-09-28, 9:27 pm |
| Dear Matthew,
> 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 might be a question better directed to their instructors.
It is true, though, that people without sufficient training in music,
language, or mathematics might find the idea of recursion new and
strange, and that can be a hurdle.
To pick up on a comment by billh, are Prolog newbies not taught a
recursive definition of a list?
A list is either an empty structure, called the empty list, and written
as [], or a structure consisting of an item, called its head, followed
by another list, called its tail, and may be written as [Head | Tail].
The head of a list is a member of it, and each member of its tail is
also a member of it. (Or something like that.)
Now, such a definition will be hard for many people, at first, but it
can be taught, and there are good examples and analogies, such as clowns
in cars and citizens of Wyoming being citizens of the U. S. Furthermore,
you can define member/2 in a natural way, and show the basic pattern for
recursive predicates.
Best,
Bill
| |
| Bill Spight 2004-09-28, 9:27 pm |
| Dear billh,
>
> 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 skill of describing a problem logically, declaratively, is important
for solving problems, by *any* means. Studying Prolog fosters logical,
declarative thinking. (Unfortunately, not all instructors of Prolog seem
to use it for that, judging by some homework problems that appear in
this newsgroup from time to time.)
But here is what you wrote, substituting "COBOL" for "Prolog":
[color=darkred]
That sounds about right to me. :-)
Best regards,
Bill
| |
| Matthew Huntbach 2004-09-30, 11:36 am |
| | |
| Cesar Rabak 2004-09-30, 11:36 am |
| Matthew Huntbach escreveu:
>
>
> On Tue, 28 Sep 2004, Cesar Rabak wrote:
>
>
>
>
>
>
> The concept of dealing with a list using recursion is not unique to
> Prolog. Anyone who has followed a good course in data structures ought
> to be familiar with the idea of recursive processing of lists. However
> the issue in Prolog is that the syntax is built round the concept.
Yes. Depending upon the way the subjects are presented to the students,
it may even that the 'good course in data structures' is pending for
the next term for the students having Prolog. . .
> In other languages you can avoid using recursion if you find it a
> difficult concept to grasp, in Prolog you can't.
>
And there are even worse things happening in this area, where the
examples trivially done in non recursive way work as well as with it.
>
>
>
> I suspect that what is happening is that most people who put "homework"
> questions to comp.lang.prolog have covered Prolog only briefly as part
> of a programming languages course, perhaps taught by someone who isn't
> particularly familiar with the language. Hence the common refrain "My
> teacher
> has told me to do this, but I haven't a clue how". My impression is that
> apart from its brief appearance on a comparative programming languages
> course,
> Prolog has ow largely disappeared from univerity computer science
> curriculums.
Yes. This was my point and you captured it very well in this comment!
The bad news is that once we agree on this, we agree the status is not
good at all for teaching of Prolog :-(
>
>
>
>
> That's related to something I'm doing now. However, my PhD involved
> giving examples of input and output, and a Prolog program which gave the
> correct output for a given input being generated automatically. There
> wasn't a higher level meta-language.
I see.
>
>
>
> The more well-known PhD thesis that used the idea was E.Y.Shapiro's
> published by MIT Press in 1983 under the title "Algorithmic Program
> Debugging". My thesis re-implemented Shapiro's system and made some
> improvements to it.
>
Thanks.
--
Cesar Rabak
|
|
|
|
|