--------------29AD9FE46F6193DB435854B3
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Thanks for all the clues received last time, here is another question i
hope
someone can help me with it.
given the following input
>(BAG-TO-SET '(A A C A B C A B))
(A C B)
basically the function needs to remove duplicates and keep the order of
the elements.
I wrote the following:
(DEFUN MY-MEMBER (ITEM MYLIST)
(COND ((NULL MYLIST) NIL)
((EQUAL (FIRST MYLIST) ITEM) T)
(T(MY-MEMBER ITEM(REST MYLIST)))
)
)
(DEFUN BAG-TO-SET (MYLIST)
(COND ((NULL MYLIST) NIL)
((ATOM MYLIST) (LIST MYLIST))
((MY-MEMBER (FIRST MYLIST) (REST MYLIST))
(APPEND NIL (BAG-TO-SET (REST MYLIST))))
(T (APPEND (LIST (FIRST MYLIST)) (BAG-TO-SET (REST MYLIST))))
)
)
which when given the same input as specified above
will return the following
>(BAG-TO-SET '(A A C A B C A B))
(C A B)
I can see that the error is where i test if the item is in the rest of
the list
and if it is i do APPEND NIL so that causes for the last A to get
appended
and therefore i lose the order of my set. I am not at all sure how to
fix this
problem. Would it be better if i was using a stack structure or should
i keep a second list that i keep comparing to the original every time i
check
an atom?
HELP PLEASE
thank you
Natalia
--------------29AD9FE46F6193DB435854B3
Content-Type: text/html; charset=us-ascii
Content-Transfer-Encoding: 7bit
<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
<html>
<tt>Thanks for all the clues received last time, here is another question
i hope</tt>
<br><tt>someone can help me with it.</tt><tt></tt>
<p><tt>given the following input</tt><tt></tt>
<p><tt>>(BAG-TO-SET '(A A C A B C A B))</tt>
<br><tt>(A C B)</tt><tt></tt>
<p><tt>basically the function needs to remove duplicates and keep the order
of the elements.</tt><tt></tt>
<p><tt>I wrote the following:</tt><tt></tt>
<p><tt>(DEFUN MY-MEMBER (ITEM MYLIST)</tt>
<br><tt> (COND ((NULL MYLIST) NIL)</tt>
<br><tt>
((EQUAL (FIRST MYLIST) ITEM) T)</tt>
<br><tt>
(T(MY-MEMBER ITEM(REST MYLIST)))</tt>
<br><tt> )</tt>
<br><tt>)</tt>
<br><tt>(DEFUN BAG-TO-SET (MYLIST)</tt>
<br><tt> (COND ((NULL MYLIST) NIL)</tt>
<br><tt> ((ATOM MYLIST)
(LIST MYLIST))</tt>
<br><tt> ((MY-MEMBER (FIRST
MYLIST) (REST MYLIST))</tt>
<br><tt> (APPEND
NIL (BAG-TO-SET (REST MYLIST))))</tt>
<br><tt> (T (APPEND (LIST
(FIRST MYLIST)) (BAG-TO-SET (REST MYLIST))))</tt>
<br><tt> )</tt>
<br><tt>)</tt><tt></tt>
<p><tt>which when given the same input as specified above</tt>
<br><tt>will return the following</tt><tt></tt>
<p><tt>>(BAG-TO-SET '(A A C A B C A B))</tt>
<br><tt>(C A B)</tt><tt></tt>
<p><tt>I can see that the error is where i test if the item is in the rest
of the list</tt>
<br><tt>and if it is i do APPEND NIL so that causes for the last A to get
appended</tt>
<br><tt>and therefore i lose the order of my set. I am not at all sure
how to fix this</tt>
<br><tt>problem. Would it be better if i was using a stack structure or
should</tt>
<br><tt>i keep a second list that i keep comparing to the original every
time i check</tt>
<br><tt>an atom?</tt>
<br><tt>HELP PLEASE</tt>
<br><tt>thank you</tt>
<br><tt>Natalia</tt></html>
--------------29AD9FE46F6193DB435854B3--
Natalia <····@one.net.au> writes:
> Thanks for all the clues received last time, here is another question i hope
> someone can help me with it.
>
> given the following input
>
> >(BAG-TO-SET '(A A C A B C A B))
> (A C B)
>
> basically the function needs to remove duplicates and keep the order of the elements.
>
> I wrote the following:
>
> (DEFUN MY-MEMBER (ITEM MYLIST)
> ����� (COND ((NULL MYLIST) NIL)
> ����������� ((EQUAL (FIRST MYLIST) ITEM) T)
> ����������� (T(MY-MEMBER ITEM(REST MYLIST)))
> ����� )
> )
> (DEFUN BAG-TO-SET (MYLIST)
> �� (COND ((NULL MYLIST) NIL)
> �������� ((ATOM MYLIST) (LIST MYLIST))
> �������� ((MY-MEMBER (FIRST MYLIST) (REST MYLIST))
> ��������� (APPEND NIL (BAG-TO-SET (REST MYLIST))))
> �������� (T (APPEND (LIST (FIRST MYLIST)) (BAG-TO-SET (REST MYLIST))))
> ��� )
> )
Some hints: (append nil <anything>) => <anything>
(append (list <anything>) <tail>) => (cons <anything> <tail>)
> which when given the same input as specified above
> will return the following
>
> >(BAG-TO-SET '(A A C A B C A B))
> (C A B)
>
> I can see that the error is where i test if the item is in the rest of the list
> and if it is i do APPEND NIL so that causes for the last A to get appended
> and therefore i lose the order of my set. I am not at all sure how to fix this
> problem. Would it be better if i was using a stack structure or should
> i keep a second list that i keep comparing to the original every time i check
> an atom?
Keep a second list. In fact, this second list is the result!
Instead of checking each element of MYLIST against the remaining
elements to see if it will be added later on, check each element of
MYLIST against what you have accumulated so far to see if you need to
add it.
> HELP PLEASE
> thank you
Hope this gets you started.
--
~jrm
Natalia wrote:
> given the following input
>
> >(BAG-TO-SET '(A A C A B C A B))
> (A C B)
> basically the function needs to remove duplicates and keep the
> order of the elements.
While doing this yourself is useful for learning the basics, if
you only wanted the thing done there is a ready-made operation
for this in Common Lisp:
(remove-duplicates <set> :from-end T)
> (DEFUN BAG-TO-SET (MYLIST)
> (COND ((NULL MYLIST) NIL)
> ((ATOM MYLIST) (LIST MYLIST))
> ((MY-MEMBER (FIRST MYLIST) (REST MYLIST))
> (APPEND NIL (BAG-TO-SET (REST MYLIST))))
> (T (APPEND (LIST (FIRST MYLIST)) (BAG-TO-SET (REST
> MYLIST))))
> )
> )
>
> which when given the same input as specified above
> will return the following
>
> >(BAG-TO-SET '(A A C A B C A B))
> (C A B)
>
> I can see that the error is where i test if the item is in the
> rest of the list
> and if it is i do APPEND NIL so that causes for the last A to
> get appended
> and therefore i lose the order of my set. I am not at all sure
> how to fix this
> problem.
NIL -> (first mylist), (REST MYLIST) -> (remove (first mylist)
(rest mylist))
> Would it be better if i was using a stack structure
> or should
> i keep a second list that i keep comparing to the original
> every time i check
> an atom?
The easiest way to implement a stack in this kind of use is just
a list, operated on by push and pop.
- You'll probably find reverse or nreverse useful, too, with a
stack.
--
> Natalia
In article <················@one.net.au>,
Natalia <····@one.net.au> wrote:
> >(BAG-TO-SET '(A A C A B C A B))
> (A C B)
someone's already posted the simplest soln, but if you have to write the
code yourself, using loop is perhaps simplest (i didn't learn loop at
first because it seemed complicated, but it can be very useful). you'd
need to "collect into" a list, and use a when clause to make sure that
the item you were collecting wasn't already in that list (if you don't
need to define your own test function, you can use member).
andrew
Sent via Deja.com http://www.deja.com/
Before you buy.
Andrew Cooke wrote:
> In article <················@one.net.au>,
> Natalia <····@one.net.au> wrote:
> > >(BAG-TO-SET '(A A C A B C A B))
> > (A C B)
>
> someone's already posted the simplest soln, but if you have to write the
> code yourself, using loop is perhaps simplest (i didn't learn loop at
> first because it seemed complicated, but it can be very useful). you'd
> need to "collect into" a list, and use a when clause to make sure that
> the item you were collecting wasn't already in that list (if you don't
> need to define your own test function, you can use member).
>
> andrew
>
I thought of using a loop, but unfortunately the questions asks us to
do the solution recursively : (
Centuries ago, Nostradamus foresaw a time when Natalia would say:
>I thought of using a loop, but unfortunately the questions asks us to
>do the solution recursively : (
This is the unfortunate part of much of the teaching that is done with
"non-Algol-descended" languges; they tend to be used solely to exercise
the bit of functionality that the instructor feels is the "point" of the
language.
In the case of Lisp, that is recursion.
--
((lambda (foo) (bar foo)) (baz))
········@ntlug.org - - <http://www.hex.net/~cbbrowne/lisp.html>
"Fernando D. Mato Mira" wrote:
> * (defvar *must-not-destroy2* '(a c e))
> *MUST-NOT-DESTROY2*
> * (delete-duplicates (append *must-not-destroy1* *must-not-destroy2*)
> :from-end t)
> (A B C E)
This is called being lucky in inputs.
(A A C E)
* (delete-duplicates (append *must-not-destroy1* *must-not-destroy2*)
:from-end t)
(A B C E)
* *must-not-destroy2*
(A A C E)
And this is called being lucky in implementation.
The correct code is:
(delete-duplicates (append *must-not-destroy1* (copy-list
*must-not-destroy2*)) :from-end t)
And Series touches home again twice! It's the World Series :)
--
Fernando D. Mato Mira
Real-Time SW Eng & Networking
Advanced Systems Engineering Division
CSEM
Jaquet-Droz 1 email: matomira AT acm DOT org
CH-2007 Neuchatel tel: +41 (32) 720-5157
Switzerland FAX: +41 (32) 720-5720
www.csem.ch www.vrai.com ligwww.epfl.ch/matomira.html
"Fernando D. Mato Mira" wrote:
> (A A C E)
> * (delete-duplicates (append *must-not-destroy1* *must-not-destroy2*)
> :from-end t)
> (A B C E)
> * *must-not-destroy2*
> (A A C E)
>
> And this is called being lucky in implementation.
Stiil lucky with inputs
* (defvar *must-not-destroy2* '(e c a))
*MUST-NOT-DESTROY2*
* (delete-duplicates (append *must-not-destroy1* *must-not-destroy2*)
:from-end t)
(A B C E)
* *MUST-NOT-DESTROY2*
(E)
--
Fernando D. Mato Mira
Real-Time SW Eng & Networking
Advanced Systems Engineering Division
CSEM
Jaquet-Droz 1 email: matomira AT acm DOT org
CH-2007 Neuchatel tel: +41 (32) 720-5157
Switzerland FAX: +41 (32) 720-5720
www.csem.ch www.vrai.com ligwww.epfl.ch/matomira.html