hello, recently i'm picking up lisp again, this time really studying
from ANSI Common Lisp by Paul Graham.. I seem to be stuck on Q2 on
Chapter 3, Where it wants me to define a new-union method which takes
in two lists, for example (new-union '(a b c) '(b a d)) and returns (a
b c d)
After writing several version and none of them work, i come to seek
help, and here is my current function:
(defun new-union (list1 list2)
"(new-union '(a b c) '(b a d)) returns (a b c d)"
(if (consp list2)
(dolist (obj list1)
(if (eql (car list2) obj)
(new-union list1 (cdr list2))
(new-union (append list1 (list (car list2))) (cdr list2))))
list1))
Here, i try to loop through the second list, upon encountering an
element (car list2), i would loop through the first list to see if
there is any matches, if there is, discard the element by going to next
one, if not found then append the element to the end (may be there is a
better way of doing this)..
After trying for 20 minutes to get it working, i thought i would go
back and do a sketch of union function within CL, and here is my failed
attempt:
(defun my-union (x y)
"defining a sketch of union method"
(if (consp x)
(dolist (obj y)
(if (eql (car x) obj)
(my-union (cdr x) y)
(my-union (cdr x) (push (car x) y)))))
y)
Here i attempt to loop recursively through the first list and upon each
encouter with a element (car x), i loop through iteratively through the
second list to find matches, if found, i would discard the element and
move on to the next, if not found, i would push the element on top of
the second list...
The two problems may be related. Can someone please point out where i'm
doing wrong? thanks alot!
> hello, recently i'm picking up lisp again, this time really studying
> from ANSI Common Lisp by Paul Graham.. I seem to be stuck on Q2 on
> Chapter 3, Where it wants me to define a new-union method which takes
> in two lists, for example (new-union '(a b c) '(b a d)) and returns (a
> b c d)
(defun new-union (a b)
(remove-duplicates (append a b) :from-end))
This is the simple way. But you probably want to use lower level
functions and play around with recursion for educational value :-)
On the other hand, if this were my assignment I would write it as above
and then come up with my own version of remove-duplicates.
>
> After writing several version and none of them work, i come to seek
> help, and here is my current function:
>
> (defun new-union (list1 list2)
> "(new-union '(a b c) '(b a d)) returns (a b c d)"
> (if (consp list2)
> (dolist (obj list1)
> (if (eql (car list2) obj)
> (new-union list1 (cdr list2))
> (new-union (append list1 (list (car list2))) (cdr list2))))
> list1))
You are combining iteration (dolist) with recursion. The result is
rather confusing, especially since it looks like the results of most of
your calculations get thrown away... For each value of obj that you
iterate over, new-union gets called and the result gets stored nowhere.
>
> (defun my-union (x y)
> "defining a sketch of union method"
> (if (consp x)
> (dolist (obj y)
> (if (eql (car x) obj)
> (my-union (cdr x) y)
> (my-union (cdr x) (push (car x) y)))))
> y)
This one has the same problem as your previous attempt. It calls
my-union and doesn't store the result. I also wonder about your use of
"push." Were you intending to modify y? If you were just trying to
build a list to pass to my-union, then you could instead use "cons."
>
> The two problems may be related. Can someone please point out where i'm
> doing wrong? thanks alot!
It looks like you have been rather confused by recursion and functional
programming. A book that would help with this is "The Little Lisper."
It is a very easy book that you should be able to get through in a day.
The programming language in that book is Scheme, which is very similar
to Common Lisp. After a couple hours with that book, recursion will
feel natural to you.
··········@gmail.com wrote:
>
> The two problems may be related. Can someone please point out where i'm
> doing wrong? thanks alot!
>
Just write the code like you think about it. For example ...
Forget the recursive car/cdr solution. Let CL be your friend.
(defun new-union (list1 list2)
(append list1
(remove-if (lambda (elt2) (member elt2 list1)) list2)))
CL-USER 13 > (new-union `(a a a b c) `(b a d))
(A A A B C D)
CL-USER 14 > (union `(a a a b c) `(b a d))
(D A A A B C)
CL-USER 15 > (new-union `(a b c) `(b a d))
(A B C D)
CL-USER 16 >
Wade
··········@gmail.com writes:
> hello, recently i'm picking up lisp again, this time really studying
> from ANSI Common Lisp by Paul Graham.. I seem to be stuck on Q2 on
> Chapter 3, Where it wants me to define a new-union method which takes
> in two lists, for example (new-union '(a b c) '(b a d)) and returns (a
> b c d)
>
> After writing several version and none of them work, i come to seek
> help, and here is my current function:
>
> (defun new-union (list1 list2)
> "(new-union '(a b c) '(b a d)) returns (a b c d)"
> (if (consp list2)
> (dolist (obj list1)
> (if (eql (car list2) obj)
> (new-union list1 (cdr list2))
> (new-union (append list1 (list (car list2))) (cdr list2))))
> list1))
>
> Here, i try to loop through the second list, upon encountering an
> element (car list2), i would loop through the first list to see if
> there is any matches, if there is, discard the element by going to next
> one, if not found then append the element to the end (may be there is a
> better way of doing this).. [...]
First, don't use tabulation in sources! Configure your emacs to
insert spaces when you type TAB.
Next, I can't imagine what you are thinking when writing these
functions. This could help debugging your thinking process...
What is the union of set1 and set2 ?
What can we say of the union of two sets?
From basic maths,
(1) We know that {} U S = S U {} = S
(2) We know that when x in S, {x} U S = S U {x} = S
(3) We know that when not(x in S), then {x} U S = {y| y = x or y in S}
(4) We know that (S1 U S2) U S3 = S1 U (S2 U S3)
We can translate this directly to lisp:
(defun union1 (S1 S2)
(cond ((null S1) S2) ; (1)
((member (first S1) S2) (union1 (rest S1) S2)) ; (4) & (2)
(t (cons (first S1) (union1 (rest S1) S2))))) ; (4) & (3)
(union1 '(a b c d) '(b d e f)) --> (A C B D E F)
Now, if you want to process the elements iteratively, we can design
the following algorithm:
union of S1, S2 is
R := S2
for all element in S1 do
if not element in S2 then
adjoint element to R
end
end
the result is R
end
(defun union2 (S1 S2)
(let ((R S2))
(dolist (element S1)
(if (not (member element R))
(setf R (cons element R))))
R))
In both cases the use of member inside the loops (or recursion) makes
the time complexity O(n�). If you have big sets, it'd be better to
use a hash table:
(defun union3 (S1 S2)
(let ((h (make-hash-table)))
(dolist (element S1) (setf (gethash element h) t))
(dolist (element S2) (setf (gethash element h) t))
(let ((r '()))
(maphash (lambda (k v) (push k r)) h)
r)))
--
__Pascal Bourguignon__ http://www.informatimago.com/
"This machine is a piece of GAGH! I need dual Opteron 850
processors if I am to do battle with this code!"
Pascal Bourguignon wrote:
> ··········@gmail.com writes:
>
>>hello, recently i'm picking up lisp again, this time really studying
>>from ANSI Common Lisp by Paul Graham.. I seem to be stuck on Q2 on
>>Chapter 3, Where it wants me to define a new-union method which takes
>>in two lists, for example (new-union '(a b c) '(b a d)) and returns (a
>>b c d)
>
> What is the union of set1 and set2 ?
> What can we say of the union of two sets?
>
> From basic maths,
> (1) We know that {} U S = S U {} = S
> (2) We know that when x in S, {x} U S = S U {x} = S
> (3) We know that when not(x in S), then {x} U S = {y| y = x or y in S}
> (4) We know that (S1 U S2) U S3 = S1 U (S2 U S3)
>
> We can translate this directly to lisp:
>
> (defun union1 (S1 S2)
> (cond ((null S1) S2) ; (1)
> ((member (first S1) S2) (union1 (rest S1) S2)) ; (4) & (2)
> (t (cons (first S1) (union1 (rest S1) S2))))) ; (4) & (3)
>
> (union1 '(a b c d) '(b d e f)) --> (A C B D E F)
>
Unfortunately, Graham's exercise is for a union that preserves the order
of the input lists -- note the example given. By preserving order, I
presume he meant the order of the first list takes precedence. I.e., you
want the elements in S1 followed by any elements in S2 not in S1.
Chris Riesbeck <··············@gmail.com> writes:
> Unfortunately, Graham's exercise is for a union that preserves the order
> of the input lists -- note the example given. By preserving order, I
> presume he meant the order of the first list takes precedence. I.e., you
> want the elements in S1 followed by any elements in S2 not in S1.
* (defun set-union (a b)
(if (endp a) b
(cons (car a)
(set-union (cdr a)
(remove (car a) b)))))
SET-UNION
* (set-union '(a b c) '(b a d))
(A B C D)
Alan Crowe
Edinburgh
Scotland
mmm.. after reading through the replies, i remembered seeing member
somewhere, then i look through chapter 3, sure enough, there is a
section on member..
here is a working code using member to do what i did before using the
dolist loop:
(defun new-union (x y)
"union after remembering member"
(if (null y)
x
(if (member (car y) x)
(new-union x (cdr y))
(new-union (append x (list (car y))) (cdr y)))))
Is there anything i shouldn't be doing (ie bad style? loopholes?)
A question, after Pascal Bourguignon kindly suggested to use spaces
instead of tabs, i wondered why that would be beneficial?
Also, to answer the question by Alan Crowe, it does help me understand
the code a bit better.. Especially if i'm quite new, since i don't know
what most of the functions do.. Though, i think breaking down one
function into several can't go past demonstration stage though, it gets
pretty tedious.. Also, i'm hoping that someone learning lisp wouldn't
need that kind of handholding :P
Thanks alot for all your warm replies!
··········@gmail.com writes:
> mmm.. after reading through the replies, i remembered seeing member
> somewhere, then i look through chapter 3, sure enough, there is a
> section on member..
>
> here is a working code using member to do what i did before using the
> dolist loop:
>
> (defun new-union (x y)
> "union after remembering member"
> (if (null y)
> x
> (if (member (car y) x)
> (new-union x (cdr y))
> (new-union (append x (list (car y))) (cdr y)))))
>
> Is there anything i shouldn't be doing (ie bad style? loopholes?)
>
> A question, after Pascal Bourguignon kindly suggested to use spaces
> instead of tabs, i wondered why that would be beneficial?
Read your function above. Does it look correctly indented?
Compare with:
(defun new-union (x y)
"union after remembering member"
(if (null y)
x
(if (member (car y) x)
(new-union x (cdr y))
(new-union (append x (list (car y))) (cdr y)))))
--
A: Because it messes up the order in which people normally read text.
Q: Why is top-posting such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
__Pascal Bourguignon__ http://www.informatimago.com/
Yah, i just noticed, i'm posting with google groups, and i tried
preview, then i copy and paste it back into the textbox (otherwise, i
wouldn't be able to see other threads i'm replying to), somehow, that
screwed up the indentation on my code, it's indented properly in my
source file.. Sorry about that..
··········@gmail.com writes:
> (new-union (append x (list (car y))) (cdr y)))))
>
> Is there anything i shouldn't be doing (ie bad style? loopholes?)
As Kernighan and Ritchie say: The only way to learn a new
programming language is by writing programs in it. So I
would advise you to tick that exercise off as done and press
on to greater things.
Later you can think some more about the fact that Lisp's
built in lists are singly-linked lists. The notation is
symmetric, left to right, and right to left, but the
underlying data structure is not. (a b c) is really
(a . (b . (c . nil)))
If a list is n long, then
(cons item list-of-n) takes unit time and space
but
(append list-of-n (list item)) take n times as much time and
space.
After you have got your code to compute the right answer
there is still more to learn, in particular the knack of
getting lists the right way round, so that items can go on
the accessible end.
However there is an order to learning this, and my guess is
that learning the structure sharing comes first. Once you
understand this:
CL-USER> (defvar middle (list 4 5 6))
MIDDLE
CL-USER> (defvar beginning (cons 3 middle))
BEGINNING
CL-USER> (defvar end (append middle (list 7)))
END
CL-USER> (list beginning middle end)
((3 4 5 6) (4 5 6) (4 5 6 7))
CL-USER> (setf (elt middle 1) 'new)
NEW
CL-USER> (list beginning middle end)
((3 4 NEW 6) (4 NEW 6) (4 5 6 7))
(Hint: cheat with (setf *print-circle* t) )
then the perils of (append x (list (car y))) will be obvious.
Alan Crowe
Edinburgh
Scotland
··········@gmail.com writes:
> Though, i think breaking down one
> function into several can't go past demonstration stage though, it gets
> pretty tedious..
I don't understand that. Breaking down functions into smaller parts
is very close to obtaining powerfull, reusable, understandable, easily
reviewed functions. Alas not all decompositions are good.
You'll soon see that many beginner exercises are decomposable into a
set of 1-4 liners. Then you may be close to functional enlightment :)
Others have pointed out that your latest code does not exhibit best
performance. Nevertheless be proud of it, because it works. You'll
later learn that (append foo (list element)) is better avoided because
it leads to O(n2) algorithms and will learn other solutions.
Regards,
Jorg Hohle
Telekom/T-Systems Technology Center
··········@gmail.com writes:
> After trying for 20 minutes to get it working, i thought i would go
> back and do a sketch of union function within CL, and here is my failed
> attempt:
>
> (defun my-union (x y)
> "defining a sketch of union method"
> (if (consp x)
> (dolist (obj y)
> (if (eql (car x) obj)
> (my-union (cdr x) y)
> (my-union (cdr x) (push (car x) y)))))
> y)
Traditionally teachers present a simple function, such as
union, to their pupils with a single defun. I'm very curious
to have a real beginners opinion on whether breaking it up
as below is helpful or not.
CL-USER> (defun set-union (a b)
(if (nothing-in a) b
(if (already-in b (first a))
(omit-first a b)
(retain-first a b))))
SET-UNION
CL-USER> (defun nothing-in (a)
(null a))
NOTHING-IN
CL-USER> (defun already-in (set element)
(member element set))
ALREADY-IN
CL-USER> (defun omit-first (a b)
(set-union (rest a) b))
OMIT-FIRST
CL-USER> (defun retain-first (a b)
(cons (first a)
(set-union (rest a) b)))
RETAIN-FIRST
Does trying out the internal parts as though they were
external parts make a difference?
CL-USER> (retain-first '(a b c) '(b a d)) => (A C B A D)
CL-USER> (omit-first '(a b c) '(b a d)) => (C B A D)
Alan Crowe
Edinburgh
Scotland