Let's say I have to define copy-list using reduce.
CL-USER 74 > (setf lst '(1 2 3 4 5))
(1 2 3 4 5)
CL-USER 75 > (defun our-copy-lst (lst)
(if (atom lst)
lst
(reduce #'append lst :key #'list)))
OUR-COPY-LST
CL-USER 76 > (our-copy-lst lst)
(1 2 3 4 5)
It works, but I don't really like it. Is there a way to do this using
cons?
I tried this:
CL-USER 77 > (defun our-copy-lst (lst)
(if (atom lst)
lst
(reduce #'cons lst)))
OUR-COPY-LST
CL-USER 78 > (our-copy-lst lst)
((((1 . 2) . 3) . 4) . 5)
and this:
CL-USER 2 > (defun our-copy-lst (lst)
(reduce #'(lambda (x y)
(cons x (list y))) lst))
OUR-COPY-LST
CL-USER 3 > (our-copy-lst lst)
((((1 2) 3) 4) 5)
I understand completely why these functions don't work and why I
receive this output.
What I would have liked to use is concatenate (although I'm not sure
how it's implemented):
CL-USER 4 > (defun our-copy-lst (lst)
(reduce #'(lambda (x y)
(concatenate 'list x y)) lst))
OUR-COPY-LST
CL-USER 5 > (our-copy-lst lst)
Error: In a call to LENGTH: 1 is not of type SEQUENCE.
1 (abort) Return to level 0.
2 Return to top loop level 0.
Type :b for backtrace, :c <option number> to proceed, or :? for other
options
I find that I spend a long time thinking about how these Lisp utility
functions work. I keep thinking that I should use only primitive
operators. I know that this is counter-productive and that I should
focus on solving the problem on hand; but that's difficult when I
write code that packages a list only to unpackage it at the next call
(append....(list....)). I wonder what I should do. I've been
skimming my textbook and I see that further on that it becomes harder
to write sloppy code. Nonetheless, do you just ignore inefficiences?
-Charles
"Charles K Johnson" <·················@hotmail.com> wrote in message
·································@posting.google.com...
> Let's say I have to define copy-list using reduce.
>
<snip>
> It works, but I don't really like it. Is there a way to do this using
> cons?
Note that a symbol can be both a function and a variable at the same
time
so this
>(defun foo (list) (list list))
FOO
>(foo '(1 2 3))
((1 2 3))
is legitimate. Some people dislike this, I think most lispers like it,
I prefer using `list' over `lst'.
(defun our-copy-list (list)
(reduce #'cons list :initial-value nil :from-end t))
>
> What I would have liked to use is concatenate (although I'm not sure
> how it's implemented):
>
> CL-USER 4 > (defun our-copy-lst (lst)
> (reduce #'(lambda (x y)
> (concatenate 'list x y)) lst))
All concatenate's arguments after the result-type must be sequences.
(defun our-copy-list (lst)
(reduce #'(lambda (x y)
(concatenate 'list x (list y))) lst :initial-value nil))
>
> I find that I spend a long time thinking about how these Lisp utility
> functions work. I keep thinking that I should use only primitive
> operators. I know that this is counter-productive and that I should
> focus on solving the problem on hand; but that's difficult when I
> write code that packages a list only to unpackage it at the next call
> (append....(list....)). I wonder what I should do. I've been
> skimming my textbook and I see that further on that it becomes harder
> to write sloppy code. Nonetheless, do you just ignore inefficiences?
>
Some quotes:
Rules of Optimization:
Rule 1: Don't do it.
Rule 2 (for experts only): Don't do it yet.
- M.A. Jackson
"More computing sins are committed in the name of efficiency
(without necessarily achieving it) than for any other single
reason - including blind stupidity."
- W.A. Wulf
"We should forget about small efficiencies, say about 97% of
the time: premature optimization is the root of all evil."
- Donald Knuth
---------------
Geoff
"Geoff Summerhayes" <·············@hNoOtSmPaAiMl.com> writes:
> "Charles K Johnson" <·················@hotmail.com> wrote in message
> ·································@posting.google.com...
> > Let's say I have to define copy-list using reduce.
I hope this isn't homework. We already HAVE a COPY-LIST and REDUCE is
the wrong way to implement it anyway. I'm suspicious of any problem
defined as "how do I do x ignoring most of the operators available to
me in the language?"
> <snip>
>
> > It works, but I don't really like it. Is there a way to do this using
> > cons?
>
> Note that a symbol can be both a function and a variable at the same
> time
> so this
>
> >(defun foo (list) (list list))
> FOO
> >(foo '(1 2 3))
> ((1 2 3))
>
> is legitimate. Some people dislike this, I think most lispers like it,
> I prefer using `list' over `lst'.
>
>
> (defun our-copy-list (list)
> (reduce #'cons list :initial-value nil :from-end t))
For programming style reasons, I recommend
:initial-value '()
> > What I would have liked to use is concatenate (although I'm not sure
> > how it's implemented):
> >
> > CL-USER 4 > (defun our-copy-lst (lst)
> > (reduce #'(lambda (x y)
> > (concatenate 'list x y)) lst))
>
> All concatenate's arguments after the result-type must be sequences.
>
> (defun our-copy-list (lst)
> (reduce #'(lambda (x y)
> (concatenate 'list x (list y))) lst :initial-value nil))
Or (mapcan #'list x), since MAPCAN has a "merge" phase to it.
Of course, (mapcar #'identity x) is simpler and more to the point.
Assuming you can't bring yourself to do (copy-list x).
In previous dialects, people wasted a lot of time coming up with idioms
for doing this. That's why there's an operator in the language that
directly accomplishes this action--so there will be no ambiguity of intent.
Btw, in a related post, a desire was indicated to use APPEND. Indeed,
(append x nil) was the standard COPY-LIST idiom in the predecessor dialect
Maclisp. But in CL, it is not a COPY-LIST since it is allowed to return
X without copying it! This is relevant to this query because an iterative
pairwise application of APPEND to a list will get at least the very tail
being (APPEND X NIL) and so the last cons will be shared even though all
the other conses get copied. It is therefore not going to be a viable
solution under any circumstances.
In article <···············@world.std.com>,
Kent M Pitman <······@world.std.com> wrote:
>"Geoff Summerhayes" <·············@hNoOtSmPaAiMl.com> writes:
>
>> "Charles K Johnson" <·················@hotmail.com> wrote in message
>> ·································@posting.google.com...
>> > Let's say I have to define copy-list using reduce.
>
>I hope this isn't homework.
Why not? The usual complaint is that someone simply asks us to give them
the answer. In this case, he's showing his work (he even came up with a
solution that works) and asking for additional advice. That's not the
typical homework cheating that we complain about.
This is clearly an academic exercise -- the location is in the Subject
line. Whether it's for a class or he's on his own doesn't seem relevant to
me.
>Or (mapcan #'list x), since MAPCAN has a "merge" phase to it.
>Of course, (mapcar #'identity x) is simpler and more to the point.
>Assuming you can't bring yourself to do (copy-list x).
Neither of those solutions fits the criteria in the problem statement:
"define COPY-LIST using REDUCE". Your solution would be like going around
the block when the driving instructor tells you to make a U-turn; sure,
both of them result in you facing the other direction, but that wasn't the
point or the exercise.
--
Barry Margolin, ······@genuity.net
Genuity, Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
Barry Margolin <······@genuity.net> writes:
> In article <···············@world.std.com>,
> Kent M Pitman <······@world.std.com> wrote:
> >"Geoff Summerhayes" <·············@hNoOtSmPaAiMl.com> writes:
> >
> >> "Charles K Johnson" <·················@hotmail.com> wrote in message
> >> ·································@posting.google.com...
> >> > Let's say I have to define copy-list using reduce.
> >
> >I hope this isn't homework.
>
> Why not? The usual complaint is that someone simply asks us to give them
> the answer.
Well, we also just ask people to say that it's homework.
I agree it's reasonable under some circumstances to post hoemwork,
as you say, if they've tried, etc.
> This is clearly an academic exercise -- the location is in the Subject
> line. Whether it's for a class or he's on his own doesn't seem
> relevant to me.
It affects the other question you ask.
> >Or (mapcan #'list x), since MAPCAN has a "merge" phase to it.
> >Of course, (mapcar #'identity x) is simpler and more to the point.
> >Assuming you can't bring yourself to do (copy-list x).
>
> Neither of those solutions fits the criteria in the problem statement:
> "define COPY-LIST using REDUCE". Your solution would be like going around
> the block when the driving instructor tells you to make a U-turn; sure,
> both of them result in you facing the other direction, but that wasn't the
> point or the exercise.
Yes, it was not responsive on the issue per se. But if the goal was
learning and linking up knowledge with knowledge, I thought it worth
putting it in perspective. I don't have a copy of the referenced book
handy to see what the context was.
In article <···············@world.std.com>,
Kent M Pitman <······@world.std.com> wrote:
>Yes, it was not responsive on the issue per se. But if the goal was
>learning and linking up knowledge with knowledge, I thought it worth
>putting it in perspective. I don't have a copy of the referenced book
>handy to see what the context was.
"I have to implement copy-list using reduce" seems pretty clear to me. I
don't have to read the book, I recognize it as a pretty typical problem and
can infer the context.
I'm not even sure what book it is. I thought that in the context of Lisp
"ACL" stood for Allegro Common Lisp.
--
Barry Margolin, ······@genuity.net
Genuity, Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
"Barry Margolin" <······@genuity.net> wrote in message
·····················@burlma1-snr2...
> In article <···············@world.std.com>,
> Kent M Pitman <······@world.std.com> wrote:
> >Yes, it was not responsive on the issue per se. But if the goal was
> >learning and linking up knowledge with knowledge, I thought it worth
> >putting it in perspective. I don't have a copy of the referenced
book
> >handy to see what the context was.
>
> "I have to implement copy-list using reduce" seems pretty clear to me.
I
> don't have to read the book, I recognize it as a pretty typical
problem and
> can infer the context.
>
> I'm not even sure what book it is. I thought that in the context of
Lisp
> "ACL" stood for Allegro Common Lisp.
>
I think the OP's specific question is his, the more general question
might be homework.
I'm guessing ANSI Common Lisp by Paul Graham. Since I don't have my
copy handy at the moment, I'm also guessing the question is far less
specific and merely requests an implementation (possibly tail-recursive)
of copy-list. In fact, in the back Graham gives the questionable
implementation:
(defun -copy-list (lst)
(labels ((cl (x)
(if (atom x)
x
(cons (car x)
(cl (cdr x))))))
(cons (car lst)
(cl (cdr lst)))))
Geoff
"Barry Margolin" <······@genuity.net> wrote in message
·····················@burlma1-snr2...
>
> I'm not even sure what book it is. I thought that in the context of Lisp
> "ACL" stood for Allegro Common Lisp.
>
Have my copy of ANSI Common Lisp in my hand
4.2. Read the description of reduce on page 368 then use it
to define
a) copy-list
b) reverse (for lists)
Unfortunately, my copy is missing pages 337-368 (just missed
the relevant leaf by one, try to explain that). If someone
in the NG has duplicates of these pages I have a duplicate
set of 369-400, willing to trade!
Geoff
"Charles K Johnson" <·················@hotmail.com> wrote in message
·································@posting.google.com...
> Let's say I have to define copy-list using reduce.
...
> It works, but I don't really like it. Is there a way to do this using
> cons?
Hint: look at the :from-end keyword to REDUCE.
P.
--
Posted from [195.120.205.142]
via Mailgate.ORG Server - http://www.Mailgate.ORG