Hello folks,
I'm trying to get through Graham's ANSI Common Lisp, and I've gotten
myself hung up on an exercise: chapter 3, ex. 2. "Write a version of union
that preserves the order of the elements in the original lists:
>(new-union '(a b c) '(b a d))
(A B C D)"
I've come up with something that gets close, but not quite. (Strangely,
the concept of recursion doesn't seem so hard, but operations on lists
seem to be throwing me.)
(defun unite (ls1 ls2)
(if (null ls2)
ls1
(if (member (car ls2) ls1)
(unite ls1 (cdr ls2))
(unite (list ls1 (car ls2)) (cdr ls2)))))
--with this, (unite '(a b c) '(b a d)) generates the following:
((A B C) D)
If I substitute "append" for list in the last line above, I get a list
like so:
(A B C . D)
And substituting cons gets everything in one list, but in the wrong order.
Any ideas on what I'm getting wrong here?
"A. Michael Perry" <·······@provide.net> wrote in message news:<······························@provide.net>...
> Hello folks,
>
> I'm trying to get through Graham's ANSI Common Lisp, and I've gotten
> myself hung up on an exercise: chapter 3, ex. 2. "Write a version of union
> that preserves the order of the elements in the original lists:
> >(new-union '(a b c) '(b a d))
> (A B C D)"
>
> I've come up with something that gets close, but not quite. (Strangely,
> the concept of recursion doesn't seem so hard, but operations on lists
> seem to be throwing me.)
>
> (defun unite (ls1 ls2)
> (if (null ls2)
> ls1
>
> (if (member (car ls2) ls1)
> (unite ls1 (cdr ls2))
> (unite (list ls1 (car ls2)) (cdr ls2)))))
>
> --with this, (unite '(a b c) '(b a d)) generates the following:
> ((A B C) D)
>
> If I substitute "append" for list in the last line above, I get a list
> like so:
> (A B C . D)
>
> And substituting cons gets everything in one list, but in the wrong order.
>
> Any ideas on what I'm getting wrong here?
Hmm. Aren't you making this a wee bit too complicated on yourself?
(defun unite (ls1 ls2)
(append ls1 ls2))
Works fine for me. Although I'm not sure if that is waht you are
aiming for here. I really don't think that the function has to be
recursive though. The reason you were getting dotted pairs at the end
when you plugged in append is because eval is seeing the final element
(cdr) as an atom. I also don't really think you need the
error-checking of (if (member (...) ...) either.
--
May the Source be with you.
neo88 (Philip Haddad)
From: Coby Beck
Subject: Re: Beginner's Question on an exercise from Graham's ACL
Date:
Message-ID: <PxLWc.2991$A8.332@edtnps89>
"neo88" <······@truevine.net> wrote in message
·································@posting.google.com...
> "A. Michael Perry" <·······@provide.net> wrote in message
news:<······························@provide.net>...
> > Hello folks,
> >
> > I'm trying to get through Graham's ANSI Common Lisp, and I've gotten
> > myself hung up on an exercise: chapter 3, ex. 2. "Write a version of
union
> > that preserves the order of the elements in the original lists:
> > >(new-union '(a b c) '(b a d))
> > (A B C D)"
[snip]
> Hmm. Aren't you making this a wee bit too complicated on yourself?
>
> (defun unite (ls1 ls2)
> (append ls1 ls2))
a union should not include duplicates for elements that appear once in each
list.
--
Coby Beck
(remove #\Space "coby 101 @ big pond . com")
······@truevine.net (neo88) writes:
> Hmm. Aren't you making this a wee bit too complicated on yourself?
>
> (defun unite (ls1 ls2)
> (append ls1 ls2))
I think the OP wanted a function which calculates the union of two sets,
represented as lists. And in a set all items are different so append
won't work.
> Works fine for me. Although I'm not sure if that is waht you are
> aiming for here. I really don't think that the function has to be
> recursive though. The reason you were getting dotted pairs at the end
> when you plugged in append is because eval is seeing the final element
> (cdr) as an atom. I also don't really think you need the
> error-checking of (if (member (...) ...) either.
This is no error checking. But if the first element of the second
list/set is a member of the first set/list, then it mustn't be inserted
to stay a set.
Regards,
Tassilo
--
Q: What's the difference between a golfer and a skydiver?
A: A golfer goes "[WHACK] ... Oh shit!". /---------------\
A skydiver goes "Oh shit! ... [WHACK]" | www.fscnrw.de |
\---------------/
> I think the OP wanted a function which calculates the union of two sets,
> represented as lists. And in a set all items are different so append
> won't work.
Ah yes, I see, sorry I misunderstood what he was asking for :-(
--
May the Source be with you.
neo88 (Philip Haddad)
A. Michael Perry wrote:
> (defun unite (ls1 ls2)
> (if (null ls2)
> ls1
>
> (if (member (car ls2) ls1)
> (unite ls1 (cdr ls2))
> (unite (list ls1 (car ls2)) (cdr ls2)))))
>
> --with this, (unite '(a b c) '(b a d)) generates the following:
> ((A B C) D)
>
> If I substitute "append" for list in the last line above, I get a list
> like so:
> (A B C . D)
>
> And substituting cons gets everything in one list, but in the wrong order.
the trivial way to do it is of course:
(defun unite (ls1 ls2)
(if (null ls2)
ls1
(if (member (car ls2) ls1)
(unite ls1 (cdr ls2))
(unite (append ls1 (list (car ls2)) (cdr ls2))))))
--
Joost Kremers ············@yahoo.com
Selbst in die Unterwelt dringt durch Spalten Licht
EN:SiS(9)
Joost Kremers <············@yahoo.com> wrote in message
> the trivial way to do it is of course:
>
> (defun unite (ls1 ls2)
> (if (null ls2)
> ls1
> (if (member (car ls2) ls1)
> (unite ls1 (cdr ls2))
> (unite (append ls1 (list (car ls2)) (cdr ls2))))))
or, if you want to be sneaky:
(defun new-union (ls1 ls2)
(when (null ls2)
(return-from new-union ls1))
(if (member (car ls2) ls1)
(new-union ls1 (cdr ls2))
(new-union `(,@ls1 ,(car ls2)) (cdr ls2))))
... but as I don't have/know Graham, I can't guarantee that he's
introduced [when], [return-from], [`], [,] or [,@].
From: Michiel Borkent
Subject: Re: Beginner's Question on an exercise from Graham's ACL
Date:
Message-ID: <cggb32$358$1@ares.cs.utwente.nl>
"Joost Kremers" <············@yahoo.com> wrote in message
································@j.kremers4.news.arnhem.chello.nl...
> (defun unite (ls1 ls2)
> (if (null ls2)
> ls1
> (if (member (car ls2) ls1)
> (unite ls1 (cdr ls2))
> (unite (append ls1 (list (car ls2)) (cdr ls2))))))
Last line should be
(unite (append ls1 (list (car ls2))) (cdr ls2)))))
but you probably meant that ;).
I first thought that the list should be sorted also, but come to think of
it, a union does not require that right? Not totally clear to me what Graham
wants and means with "preserves the order of the original lists".
Michiel Borkent
Michiel Borkent wrote:
> "Joost Kremers" <············@yahoo.com> wrote in message
>> (unite (append ls1 (list (car ls2)) (cdr ls2))))))
>
> Last line should be
> (unite (append ls1 (list (car ls2))) (cdr ls2)))))
>
> but you probably meant that ;).
it's a miracle...! you read my mind! ;-)
> I first thought that the list should be sorted also, but come to think of
> it, a union does not require that right? Not totally clear to me what Graham
> wants and means with "preserves the order of the original lists".
well, from the example he gives:
> (new-union '(a b c) '(b a d))
(A B C D)
i understand it to mean: the union is formed by taking the whole of the
first list unchanged, and then tucking onto the end of it those elements of
the second list that do not occur in the first list, preserving the order
in which they appear in the second list.
but i agree that there are other ways to interpret the example...
--
Joost Kremers ············@yahoo.com
Selbst in die Unterwelt dringt durch Spalten Licht
EN:SiS(9)
Michiel Borkent wrote:
> I first thought that the list should be sorted also, but come to think of
> it, a union does not require that right? Not totally clear to me what Graham
> wants and means with "preserves the order of the original lists".
If A = (x1 x2 ... xn) and B = (y1 ... ym) then it means
that in the list A U B the elements x1, ... xn occurs
in the same order they did in A and similar for B.
Thus
(union '(1 2) '(a))
can return
(1 2 a) or (1 a 2) or (a 1 b)
but not
(2 1 a) or (2 a 1) or (a 2 1) .
--
Jens Axel Søgaard
Jens Axel Søgaard wrote:
> Michiel Borkent wrote:
>
>> I first thought that the list should be sorted also, but come to think of
>> it, a union does not require that right? Not totally clear to me what
>> Graham
>> wants and means with "preserves the order of the original lists".
>
>
> If A = (x1 x2 ... xn) and B = (y1 ... ym) then it means
> that in the list A U B the elements x1, ... xn occurs
> in the same order they did in A and similar for B.
BTW: Note that,
(union '(a b c) '(b a)) => (a b c)
should be interpreted as keeping a, b, and c from the
first list and omitting b and a from the second list.
Thus those elements from the second list that occurs
in the output should be have the same relative order
as in the input.
--
Jens Axel Søgaard
"A. Michael Perry" <·······@provide.net> writes:
> I'm trying to get through Graham's ANSI Common Lisp, and I've gotten
> myself hung up on an exercise: chapter 3, ex. 2. "Write a version of union
> that preserves the order of the elements in the original lists:
*
That is not possible, if you don't specify more precisely what you mean.
(Sorry, I don't own this book).
> >(new-union '(a b c) '(b a d))
> (A B C D)
What about (B C A D) ?
> I've come up with something that gets close, but not quite. (Strangely,
> the concept of recursion doesn't seem so hard, but operations on lists
> seem to be throwing me.)
>
> (defun unite (ls1 ls2)
> (if (null ls2)
> ls1
>
> (if (member (car ls2) ls1)
> (unite ls1 (cdr ls2))
> (unite (list ls1 (car ls2)) (cdr ls2)))))
>
> --with this, (unite '(a b c) '(b a d)) generates the following:
> ((A B C) D)
>
> If I substitute "append" for list in the last line above, I get a list
> like so:
> (A B C . D)
>
> And substituting cons gets everything in one list, but in the wrong order.
>
> Any ideas on what I'm getting wrong here?
You need to study your toys, the lego^W lisp blocks. See CLHS, chapter
"14. Conses".
APPEND takes _lists_ and provide a new list containing the same elements.
CONS takes an _item_ and a _list_ and provide a new list containing
the _item_ and the same elements (and same cells) as in _list_.
NCONC takes _lists_ and glue them together, modifying the last cell of
all but the last.
Also of interest may be: LAST, ADJOIN, PUSHNEW, the various MAP functions, etc.
The first thing to specify is whether the function is "destructive" or
"constructive", ie. whether the arguments will (or may) be modified,
or whether the result must be a newly consed list and the arguments
must not be touched.
In the case of a desctructive function, NCONC could be used, like that:
(nconc ls1 (list (car ls2)))
But given that you pass literal arguments in your example, we'll assume
you want a constructive function.
So, you want to build a new list containing the same elements as ls1
followed by the elements in ls2 that are not already in ls1. A simple
solution could be:
(append ls1 (remove-if (lambda (e2) (member e2 ls1)) ls2))
But if you want to write it yourself recursively, you'll have to take
care of how you copy the first argument.
(defun unite (ls1 ls2)
(if (null ls2)
(copy-list ls1)
(nreverse (unite-rec ls1 ls2 (reverse ls1)))))
(defun unite-rec (ls1 ls2 result)
(cond ((null ls2) result)
((member (car ls2) ls1) (unite-rec ls1 (cdr ls2) result))
t (unite-rec ls1 (cdr ls2)
(cons (car ls2) result))))
Note that: (unite '(a b c) '(d e b c d e)) ==> (A B C D E D E)
You may want to test the elements of ls1 for "previous" membership in
ls1, and you may want to test the membership of elements of ls2 in the
partial result instead of ls1, to implement an implicit
REMOVE-DUPLICATES. (Or perhaps it's not specified?)
(defun unite (&rest lists)
(nreverse (unite-1 nil lists)))
(defun unite-1 (result lists)
(cond ((null lists) result)
((null (car lists)) (unite-1 result (cdr lists)))
((member (caar lists) result)
(unite-1 result
(cons (cdar lists) (cdr lists))))
(t (unite-1 (cons (caar lists) result)
(cons (cdar lists) (cdr lists))))))
(trace unite unite-1)
(unite '(a b b c) '(a b d e d) '( f a c e f))
1. Trace: (UNITE '(A B B C) '(A B D E D) '(F A C E F))
2. Trace: (UNITE-1 'NIL '((A B B C) (A B D E D) (F A C E F)))
3. Trace: (UNITE-1 '(A) '((B B C) (A B D E D) (F A C E F)))
4. Trace: (UNITE-1 '(B A) '((B C) (A B D E D) (F A C E F)))
5. Trace: (UNITE-1 '(B A) '((C) (A B D E D) (F A C E F)))
6. Trace: (UNITE-1 '(C B A) '(NIL (A B D E D) (F A C E F)))
7. Trace: (UNITE-1 '(C B A) '((A B D E D) (F A C E F)))
8. Trace: (UNITE-1 '(C B A) '((B D E D) (F A C E F)))
9. Trace: (UNITE-1 '(C B A) '((D E D) (F A C E F)))
10. Trace: (UNITE-1 '(D C B A) '((E D) (F A C E F)))
11. Trace: (UNITE-1 '(E D C B A) '((D) (F A C E F)))
12. Trace: (UNITE-1 '(E D C B A) '(NIL (F A C E F)))
13. Trace: (UNITE-1 '(E D C B A) '((F A C E F)))
14. Trace: (UNITE-1 '(F E D C B A) '((A C E F)))
15. Trace: (UNITE-1 '(F E D C B A) '((C E F)))
16. Trace: (UNITE-1 '(F E D C B A) '((E F)))
17. Trace: (UNITE-1 '(F E D C B A) '((F)))
18. Trace: (UNITE-1 '(F E D C B A) '(NIL))
19. Trace: (UNITE-1 '(F E D C B A) 'NIL)
19. Trace: UNITE-1 ==> (F E D C B A)
" " "
2. Trace: UNITE-1 ==> (F E D C B A)
1. Trace: UNITE ==> (A B C D E F)
(A B C D E F)
It works nicely, but it's not so good a solution because it conses a
lot of intermediary arguments.
Instead of consing, we could use one more argument:
(defun unite (&rest lists)
(nreverse (unite-1 nil (first lists) (rest lists))))
(defun unite-1 (result first-list other-lists)
(cond ((null first-list)
(if (null other-lists)
result
(unite-1 result (car other-lists) (cdr other-lists))))
((member (car first-list) result)
(unite-1 result (cdr first-list) other-lists))
(t (unite-1 (cons (car first-list) result)
(cdr first-list) other-lists))))
but depending on how good (or how bad) the compiler is, that could
make little difference.
--
__Pascal Bourguignon__ http://www.informatimago.com/
Our enemies are innovative and resourceful, and so are we. They never
stop thinking about new ways to harm our country and our people, and
neither do we.
On Tue, 24 Aug 2004 09:59:28 +0200, Pascal Bourguignon wrote:
*
> That is not possible, if you don't specify more precisely what you mean.
> (Sorry, I don't own this book).
>
>> >(new-union '(a b c) '(b a d))
>> (A B C D)
>
> What about (B C A D) ?
>
>
>
> You need to study your toys, the lego^W lisp blocks. See CLHS, chapter
> "14. Conses".
Thanks, your solution is probably correct, but I was trying to follow the
order of this book, which has not introduced many of the constructs you
mention. I am afraid I am also unfamiliar with CLHS...I only have the
Graham book at this moment, as it was the cheapest one that looked to be
any good. (Alas, low price is too often a guiding factor in my decisions.)
From: Edi Weitz
Subject: Re: Beginner's Question on an exercise from Graham's ACL
Date:
Message-ID: <87pt5g3jyj.fsf@bird.agharta.de>
On Tue, 24 Aug 2004 10:25:18 GMT, "A. Michael Perry" <·······@provide.net> wrote:
> I am afraid I am also unfamiliar with CLHS...
<http://www.lispworks.com/reference/HyperSpec/Front/index.htm>
That's the language standard, though, not an introductory book.
Edi.
--
"Lisp doesn't look any deader than usual to me."
(David Thornley, reply to a question older than most languages)
Real email: (replace (subseq ·········@agharta.de" 5) "edi")
"A. Michael Perry" <·······@provide.net> writes:
> On Tue, 24 Aug 2004 09:59:28 +0200, Pascal Bourguignon wrote:
>
> *
> > That is not possible, if you don't specify more precisely what you mean.
> > (Sorry, I don't own this book).
> >
> >> >(new-union '(a b c) '(b a d))
> >> (A B C D)
> >
> > What about (B C A D) ?
> >
> >
> >
> > You need to study your toys, the lego^W lisp blocks. See CLHS, chapter
> > "14. Conses".
>
> Thanks, your solution is probably correct, but I was trying to follow the
> order of this book, which has not introduced many of the constructs you
> mention. I am afraid I am also unfamiliar with CLHS...I only have the
> Graham book at this moment, as it was the cheapest one that looked to be
> any good. (Alas, low price is too often a guiding factor in my decisions.)
Well, it depends on your learning style.
When I learn, the objective is to learn, not to follow a tutorial...
--
__Pascal Bourguignon__ http://www.informatimago.com/
Our enemies are innovative and resourceful, and so are we. They never
stop thinking about new ways to harm our country and our people, and
neither do we.
From: Ian J Cottee
Subject: Re: Beginner's Question on an exercise from Graham's ACL
Date:
Message-ID: <tdurv1-9o3.ln1@suse.zobbo.org>
Pascal Bourguignon wrote:
> "A. Michael Perry" <·······@provide.net> writes:
>
>
>>On Tue, 24 Aug 2004 09:59:28 +0200, Pascal Bourguignon wrote:
>>>You need to study your toys, the lego^W lisp blocks. See CLHS, chapter
>>>"14. Conses".
>>
>>Thanks, your solution is probably correct, but I was trying to follow the
>>order of this book, which has not introduced many of the constructs you
>>mention. I am afraid I am also unfamiliar with CLHS...I only have the
>>Graham book at this moment, as it was the cheapest one that looked to be
>>any good. (Alas, low price is too often a guiding factor in my decisions.)
>
>
> Well, it depends on your learning style.
>
> When I learn, the objective is to learn, not to follow a tutorial...
As another Lisp newbie going through the ACL book I will lend some
support to the original poster here. Paul Graham specifically poses some
questions which are intended to be answered with reference to the
material in the chapter you are working on, rather than with simpler
solutions based on items you are not expected to know yet. e.g. from the
questions at the end of Chapter 2.
7. Using only operators introduced in this chapter, define a
function that takes a list as an argument and returns true if
one of its elements is a list.
That forces me to approach the solution with the new concepts that have
just been taught and to exercise my brain on them - not with some other
solution I might be aware of.
In my case, I'm having some problems in solving items recursively -
whereas an iterative function is much simpler for me. By forcing myself
to keep finding a recursive solution I'm exercising the concepts in my
head.
I have to say, I find it very hard to follow tutorials due to the desire
to leap forward and actually 'do' something. However, in the case of
lisp, I have managed to comprehensively fail to pick it up by delving
around so I'm trying to be disciplined. However, I was reading chapter
three of the Gigamonkeys online book today and rather enjoyed working
with a real (albeit very simple) application - instead of just assigning
variables repeatedly :)
Ian
Ian J Cottee <···@cottee.org> wrote in message news:<··············@suse.zobbo.org>...
> As another Lisp newbie going through the ACL book I will lend some
> support to the original poster here. Paul Graham specifically poses some
> questions which are intended to be answered with reference to the
> material in the chapter you are working on, rather than with simpler
> solutions based on items you are not expected to know yet. e.g. from the
> questions at the end of Chapter 2.
>
> 7. Using only operators introduced in this chapter, define a
> function that takes a list as an argument and returns true if
> one of its elements is a list.
>
> That forces me to approach the solution with the new concepts that have
> just been taught and to exercise my brain on them - not with some other
> solution I might be aware of.
>
> In my case, I'm having some problems in solving items recursively -
> whereas an iterative function is much simpler for me. By forcing myself
> to keep finding a recursive solution I'm exercising the concepts in my
> head.
[deleted and reposted. had to struggle with google groups to get it to
post right and still ended up not working. ignore if you've read or
just don't care.]
Recursion might be more worthwhile as a separate item to learn, rather
than binding up lisp and recursion into a single package of pain.
Recursion is elegant in some situations:
(defun list-inside? (list)
(cond ((null list)
nil)
((listp (car list))
t)
(t
(list-inside? (cdr list)))))
But often not direct:
(some #'listp '(1 2 3 4 (5) 6))
(loop for i in '(1 2 3 4 (5) 6)
thereis (listp i))
Recursion in lisp is probably a lot less common than many think.
Alternate places than lisp materials might teach it better, though if
you want, there's a section in chapter 3 in Graham's ANSI CL about it.
MfG,
Tayssir
From: Ian J Cottee
Subject: Re: Beginner's Question on an exercise from Graham's ACL
Date:
Message-ID: <hk5tv1-hf8.ln1@suse.zobbo.org>
Tayssir John Gabbour wrote:
> Recursion might be more worthwhile as a separate item to learn, rather
> than binding up lisp and recursion into a single package of pain.
>
> Recursion is elegant in some situations:
>
> (defun list-inside? (list)
> (cond ((null list)
> nil)
> ((listp (car list))
> t)
> (t
> (list-inside? (cdr list)))))
>
> But often not direct:
>
> (some #'listp '(1 2 3 4 (5) 6))
>
> (loop for i in '(1 2 3 4 (5) 6)
> thereis (listp i))
>
> Recursion in lisp is probably a lot less common than many think.
> Alternate places than lisp materials might teach it better, though if
> you want, there's a section in chapter 3 in Graham's ANSI CL about it.
Tayssir
Many thanks for that. In fact - I am just about to embark on chapter 3
but the questions were in chapter 2. Hopefully chapter 3 will help. Just
to clarify - it's not the concept of recursion I find hard to understand
but rather the specific examples used within ACL. I found last night
however (much to my relief) that somebody else had similar issues with
the same example I was sweating with.
http://lists.sfgoth.com/pipermail/rotwang-l/2004-January/000081.html
From that I conclude that my issue in this case is partly recursion and
partly sneaky uses of 'and' :)
Ian
From: Marco Baringer
Subject: Re: Beginner's Question on an exercise from Graham's ACL
Date:
Message-ID: <m2isb9rlth.fsf@convey.it>
a proper list is a chain of cons cells, where the last CDR is NIL, a
dotted list is a chain of cons cells where the last CDR is not NIL
(nor, obviously, a cons cell). so a list like (a b c) is actually
(cons a (cons b (cons c nil))), the lisp printer prints that chain of
cons cell as (a b c), but (a . (b . (c . nil))) would be just as
correct.
(list ls1 (car ls2)) is generating a two element proper list whose
first element is ls1 (a proper list) and whose second element is (car
ls2) (an atom) which is:
((a b c) d)
(append ls1 (car ls2)) is appending (car ls2) onto the last cdr of ls1
(which originally was NIL), but since (car ls2) is an atom and not a
proper list you get the dotted list:
(a b c . d)
what you seem to want is a copy of ls1 whose last "element" is (car
ls2). in list terms this means that the last cdr of the resulting
list should be (cons (car ls2) nil). we write this like so:
(append ls1 (cons (car ls2) nil))
but since (cons (car ls2) nil) is just long hand for (list (car ls2))
we'll just write:
(append ls1 (list (car ls2)))
makes sense?
--
-Marco
Ring the bells that still can ring.
Forget your perfect offering.
There is a crack in everything.
That's how the light gets in.
-Leonard Cohen
"A. Michael Perry" <·······@provide.net> writes:
> Hello folks,
Hi,
> I'm trying to get through Graham's ANSI Common Lisp, and I've gotten
> myself hung up on an exercise: chapter 3, ex. 2. "Write a version of union
> that preserves the order of the elements in the original lists:
>>(new-union '(a b c) '(b a d))
> (A B C D)"
Hm, I don't have the book but am trying to get into CL, too.
(I use the book (or the www page) "Successful LISP" of David B. Lamkins
[1].
This here seems to do the trick. I make it with cons but first I reverse
the list. (I think it's a very bad, expensive solution, because I
reverse the list two times every step and in my-list-reverse I use an
append, which should do the job directly.)
(defun my-unite (list1 list2)
(if (null list2)
list1
(if (member (first list2) list1)
(my-unite list1 (rest list2))
(my-unite
(my-list-reverse (cons (first list2) (my-list-reverse list1)))
(rest list2)))))
(defun my-list-reverse (list)
(if (null list)
()
(append
(my-list-reverse (rest list))
(list (first list)))))
So here's my secons solution:
(defun other-unite (list1 list2)
(if (null list2)
list1
(if (member (first list2) list1)
(other-unite
list1
(rest list2))
(other-unite
(append list1 (list (first list2)))
(rest list2)))))
Regards,
Tassilo
[1] www.psg.com/~dlamkins/sl/
--
alt.microsoft.crash.crash.crash The NG name describes it all.
From: Wade Humeniuk
Subject: Re: Beginner's Question on an exercise from Graham's ACL
Date:
Message-ID: <RaPWc.52097$X12.45339@edtnps84>
A. Michael Perry wrote:
> Hello folks,
>
> I'm trying to get through Graham's ANSI Common Lisp, and I've gotten
> myself hung up on an exercise: chapter 3, ex. 2. "Write a version of union
> that preserves the order of the elements in the original lists:
>
>>(new-union '(a b c) '(b a d))
>
> (A B C D)"
>
> I've come up with something that gets close, but not quite. (Strangely,
> the concept of recursion doesn't seem so hard, but operations on lists
> seem to be throwing me.)
>
> (defun unite (ls1 ls2)
> (if (null ls2)
> ls1
>
> (if (member (car ls2) ls1)
> (unite ls1 (cdr ls2))
> (unite (list ls1 (car ls2)) (cdr ls2)))))
>
Another solution might be:
(defun unite (list1 list2)
(let ((result nil))
(dolist (obj list1) (pushnew obj result))
(dolist (obj list2) (pushnew obj result))
(nreverse result)))
Wade
I skimmed through the thread. I don't recall seeing:
CL-USER 13 > (remove-duplicates (append '(a b c) '(b a d)) :from-end t)
(A B C D)
Note the CLHS says for remove-duplicates that "The order of the elements
remaining in the result is the same as the order in which they appear in
sequence."
Jeff Caldwell
...
> > I'm trying to get through Graham's ANSI Common Lisp, and I've gotten
> > myself hung up on an exercise: chapter 3, ex. 2. "Write a version of
union
> > that preserves the order of the elements in the original lists:
> >
> >>(new-union '(a b c) '(b a d))
> >
> > (A B C D)"
> >
...
Wade Humeniuk <····································@telus.net> wrote
> A. Michael Perry wrote:
> >>(new-union '(a b c) '(b a d))
> > (A B C D)"
> Another solution might be:
>
> (defun unite (list1 list2)
> (let ((result nil))
> (dolist (obj list1) (pushnew obj result))
> (dolist (obj list2) (pushnew obj result))
> (nreverse result)))
I'd simplify that to
(defun new-union (a b)
(let (u)
(dolist (i (append a b))
(pushnew i u))
(nreverse u)))
but the ultimate solution must surely be
(defun new-union (a b)
(remove-duplicates (append a b) :from-end t))
(not that it has anything to do with the original exercise, though :-) )
From: John Thingstad
Subject: Re: Beginner's Question on an exercise from Graham's ACL
Date:
Message-ID: <opsc96tmcbpqzri1@mjolner.upc.no>
try this:
(defun my-union-gen (l1 l2)
(if (null l2)
l1
(if (member (car l2) l1)
(my-union l1 (cdr l2))
(my-union (cons (car l2) l1) (cdr l2)))))
On Tue, 24 Aug 2004 06:57:05 GMT, A. Michael Perry <·······@provide.net>
wrote:
> Hello folks,
>
> I'm trying to get through Graham's ANSI Common Lisp, and I've gotten
> myself hung up on an exercise: chapter 3, ex. 2. "Write a version of
> union
> that preserves the order of the elements in the original lists:
>> (new-union '(a b c) '(b a d))
> (A B C D)"
>
> I've come up with something that gets close, but not quite. (Strangely,
> the concept of recursion doesn't seem so hard, but operations on lists
> seem to be throwing me.)
>
> (defun unite (ls1 ls2)
> (if (null ls2)
> ls1
>
> (if (member (car ls2) ls1)
> (unite ls1 (cdr ls2))
> (unite (list ls1 (car ls2)) (cdr ls2)))))
>
> --with this, (unite '(a b c) '(b a d)) generates the following:
> ((A B C) D)
>
> If I substitute "append" for list in the last line above, I get a list
> like so:
> (A B C . D)
>
> And substituting cons gets everything in one list, but in the wrong
> order.
>
> Any ideas on what I'm getting wrong here?
--
Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/
From: John Thingstad
Subject: Re: Beginner's Question on an exercise from Graham's ACL
Date:
Message-ID: <opsc97ljsdpqzri1@mjolner.upc.no>
sorry I missed the part about preserving order.
On Wed, 25 Aug 2004 11:18:48 +0200, John Thingstad
<··············@chello.no> wrote:
> try this:
>
> (defun my-union-gen (l1 l2)
> (if (null l2)
> l1
> (if (member (car l2) l1)
> (my-union l1 (cdr l2))
> (my-union (cons (car l2) l1) (cdr l2)))))
>
> On Tue, 24 Aug 2004 06:57:05 GMT, A. Michael Perry <·······@provide.net>
> wrote:
>
>> Hello folks,
>>
>> I'm trying to get through Graham's ANSI Common Lisp, and I've gotten
>> myself hung up on an exercise: chapter 3, ex. 2. "Write a version of
>> union
>> that preserves the order of the elements in the original lists:
>>> (new-union '(a b c) '(b a d))
>> (A B C D)"
>>
>> I've come up with something that gets close, but not quite. (Strangely,
>> the concept of recursion doesn't seem so hard, but operations on lists
>> seem to be throwing me.)
>>
>> (defun unite (ls1 ls2)
>> (if (null ls2)
>> ls1
>>
>> (if (member (car ls2) ls1)
>> (unite ls1 (cdr ls2))
>> (unite (list ls1 (car ls2)) (cdr ls2)))))
>>
>> --with this, (unite '(a b c) '(b a d)) generates the following:
>> ((A B C) D)
>>
>> If I substitute "append" for list in the last line above, I get a list
>> like so:
>> (A B C . D)
>>
>> And substituting cons gets everything in one list, but in the wrong
>> order.
>>
>> Any ideas on what I'm getting wrong here?
>
>
>
--
Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/