I am new to lisp and am having trouble catching on to this language. I
have been trying to reverse a list iteratively and I have come into
problems.
(defun revnums (n)
(let ((count 1) (result (list n)))
(loop
(cond ((equal count 1) (return result)))
(setq count(1- count))
(setq result (cons count
result)) (setq n (remove car n)
n))))
Any suggestions would be great
Thanks
Ski
Ski wrote:
>
> I am new to lisp and am having trouble catching on to this language. I
> have been trying to reverse a list iteratively and I have come into
> problems.
There is of course a reverse function which does exactly what you
want, but I assume you're doing this as an exercise. Since you've
made an honest attempt, I'll try to help without giving you the
answer.
> (defun revnums (n)
> (let ((count 1) (result (list n)))
> (loop
> (cond ((equal count 1) (return result)))
> (setq count(1- count))
> (setq result (cons count
> result)) (setq n (remove car n)
> n))))
Here are a few things wrong with your code. Firstly, if n
is a list, (list n) will return a list containing the list, e.g.
if n = (1 2 3), (list n) = ((1 2 3)). You probably wanted
result initialized to '() anyway. Secondly, (remove car n)
should be (remove (car n) n), or better just (cdr n) or (rest n).
You can replace (setq n (remove (car n) n)) with (pop n), and
(setq count (1- count)) with (decf count). (cons count result)
should probably be (cons (first n) result).
You should make these changes, put (break "start") at the
start of your loop, and put (break "end") at the end
of your loop, so that you can inspect the values of variables.
that will help you to debug. There are a lot of other changes
you'll have to make to get your code to work.
After you get your function returning the correct value, I
would then structure your code better by replacing let and loop
with do.
> Any suggestions would be great
> Thanks
> Ski
--
Le Hibou (mo bheachd fhe/in: my own opinion)
"What the ... This is Lambic! Where's my culture of amoebic
dysentery?"
-- Gary Larson
(defun my-reverse (a-list)
(do ((n (- 1) (incf n)) (result '() (cons (nth n a-list) result)))
((= n (- (length a-list) 1)) result )))
I think you might want to look at a good treatment of do. Basically, do lets
you iterate over multiple variables simultaneously. This lets you use one
variable to accumulate the results of your iteration of (an)other
variable(s). It's much more compact than the sorts of nested loops one sees
in many other languages, and takes some getting used to if you're more
familiar with, say, C.
FWIW, I'm no lisp wizard, so others here may have a better way to do this,
but it does work. It leaves all the top level elements of a-list intact,
which is what I assume you wanted (i.e., that's what the common lisp
function reverse does).
Raf
Raffael Cavallaro schrieb in Nachricht <··········@news-central.tiac.net>...
>
>(defun my-reverse (a-list)
> (do ((n (- 1) (incf n)) (result '() (cons (nth n a-list) result)))
> ((= n (- (length a-list) 1)) result )))
(defun my-reverse1 (a-list)
(do ((n (- 1) (incf n))
(result '() (cons (nth n a-list) result)))
((= n (- (length a-list) 1))
result)))
Your code is ******really******* slow.
- You don't need a counter variable n. Btw., in your DO loop, (incf n) could
be replaced by (+ n 1),
since DO already does the updating of n in every step.
- You are using NTH over and over. This amounts to n walks over 1/2 length
of the list.
- You are using LENGTH. This amounts to n additional walks over the list.
Find a version that just walks once over the list.
Raffael Cavallaro schrieb in Nachricht <··········@news-central.tiac.net>...
>
>(defun my-reverse (a-list)
> (do ((n (- 1) (incf n)) (result '() (cons (nth n a-list) result)))
> ((= n (- (length a-list) 1)) result )))
(defun my-reverse1 (a-list)
(do ((n (- 1) (incf n))
(result '() (cons (nth n a-list) result)))
((= n (- (length a-list) 1))
result)))
Your code is ******really******* slow.
- You don't need a counter variable n. Btw., in your DO loop, (incf n) could
be replaced by (+ n 1),
since DO already does the updating of n in every step.
- You are using NTH over and over. This amounts to n walks over 1/2 length
of the list.
- You are using LENGTH. This amounts to n additional walks over the list.
Find a version that just walks once over the list.
Rainer Joswig schrieb:
>Your code is ******really******* slow.
Ok, ok, my code is really slow - but did you have to say it *three* times
:^)
(your post showed up three times here)
Anyway, how about:
(defun my-reverse (a-list)
(do ( (whats-left a-list (cdr a-list)) (result '() (cons (pop a-list)
result)))
( ( eq whats-left '()) result)))
>
>- You don't need a counter variable n.
True enough. Mea culpa. I've eliminated it.
>- You are using NTH over and over. This amounts to n walks over 1/2 length
>of the list.
>- You are using LENGTH. This amounts to n additional walks over the list.
>
>Find a version that just walks once over the list.
Good advice - I think I've taken it - please correct me if I still haven't.
Raf
P.S. Rainer, a while back I followed up your post about floating point
performance with a request that you post the raytracing benchmark results
for MCL 4.2. I'm pretty sure you use this version (as well as lisp
implimentations for other platforms) since I've seen your posts on
comp.lang.lisp.mcl. I've used MCL 3.x on an old Quadra, and I'm thinking
about getting a new G3 Mac and MCL 4.2. I'd appreciate any results you could
share with us since I may be doing a fair bit of floating point computation,
and I'd like to use MCL. Thanks.
Raffael Cavallaro schrieb in Nachricht <··········@news-central.tiac.net>...
>>Your code is ******really******* slow.
>
>Ok, ok, my code is really slow - but did you have to say it *three* times
>:^)
>(your post showed up three times here)
Sorry about that. Outlook and me is not a very useful combination. ;-)
>Anyway, how about:
>
> (defun my-reverse (a-list)
> (do ( (whats-left a-list (cdr a-list)) (result '() (cons (pop a-list)
>result)))
> ( ( eq whats-left '()) result)))
Looks much better.
>
>P.S. Rainer, a while back I followed up your post about floating point
>performance with a request that you post the raytracing benchmark results
>for MCL 4.2. I'm pretty sure you use this version (as well as lisp
>implimentations for other platforms) since I've seen your posts on
>comp.lang.lisp.mcl. I've used MCL 3.x on an old Quadra, and I'm thinking
>about getting a new G3 Mac and MCL 4.2. I'd appreciate any results you
could
>share with us since I may be doing a fair bit of floating point
computation,
>and I'd like to use MCL. Thanks.
O.k., I'll run the benchmark later. MCL has a problem with FP code.
You need to do manual changes to the source to avoid excessive float
allocation. MCL is quite fast then. But I would prefer that the compiler
would compile it that way out of the box. Since Digitool is
steadily improving their excellent product, this is definitely
worth being requested by customers (if they need it).
>
>
Raffael Cavallaro schrieb in Nachricht <··········@news-central.tiac.net>...
>
>(defun my-reverse (a-list)
> (do ((n (- 1) (incf n)) (result '() (cons (nth n a-list) result)))
> ((= n (- (length a-list) 1)) result )))
(defun my-reverse1 (a-list)
(do ((n (- 1) (incf n))
(result '() (cons (nth n a-list) result)))
((= n (- (length a-list) 1))
result)))
Your code is ******really******* slow.
- You don't need a counter variable n. Btw., in your DO loop, (incf n) could
be replaced by (+ n 1),
since DO already does the updating of n in every step.
- You are using NTH over and over. This amounts to n walks over 1/2 length
of the list.
- You are using LENGTH. This amounts to n additional walks over the list.
Find a version that just walks once over the list.
Raffael Cavallaro schrieb in Nachricht <··········@news-central.tiac.net>...
>(defun my-reverse (a-list)
> (do ( (whats-left a-list (cdr a-list)) (result '() (push (pop a-list)
>result)))
> ( ( eq whats-left '()) result)))
>
>(defun my-reverse (a-list)
> (do ( (whats-left a-list (cdr a-list)) (result '() (cons (pop a-list)
>result)))
> ( ( eq whats-left '()) result)))
>
>What difference, if any does using PUSH as opposed to CONS make here?
You don't need it. (push item list) is something
like (setf list (cons item list))).
In article <··········@news-central.tiac.net>,
Raffael Cavallaro <·······@pop.tiac.net> wrote:
>(defun my-reverse (a-list)
> (do ( (whats-left a-list (cdr a-list)) (result '() (push (pop a-list)
>result)))
> ( ( eq whats-left '()) result)))
>
>(defun my-reverse (a-list)
> (do ( (whats-left a-list (cdr a-list)) (result '() (cons (pop a-list)
>result)))
> ( ( eq whats-left '()) result)))
>
>What difference, if any does using PUSH as opposed to CONS make here?
By using PUSH, you do the assignment twice. PUSH expands into an
assignment, and then DO also assigns to the iteraction variable.
There's a similar thing going on with the POPs. That assigns to A-LIST,
but the iteration also does so. If you want to use PUSH and POP, the
following would be the way to use it:
(defun my-reverse (a-list)
(do ((result '()))
((null a-list) result)
(push (pop a-list) result)))
Notice that there's no need to use a separate whats-left variable; a-list
is local to this function, so there's no reason not to assign to it
directly.
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Cambridge, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Barry Margolin <······@bbnplanet.com> writes:
> > (do ((whats-left a-list (cdr a-list))
> > (result '() (cons (pop a-list) result)))
> > (( eq whats-left '()) result)))
>
> Notice that there's no need to use a separate whats-left variable; a-list
> is local to this function, so there's no reason not to assign to it
> directly.
Uh, that's not true, actually. There are potential reasons. They are
not functional reasons, but they are reasons of modular coding style
(i.e., to highlight that consuming the list is needed only within the
loop) and also debugging (since it may be very useful when the
debugger is entered mid-loop to see both the original list and the
whats-left part). As far as debugging goes, not all compilers will
show you this, and certainly not in all combinations of coimpiler
optimization settings, but if they do it can be useful, so many
programmers--myself included--often code for it.
Kent M Pitman wrote in message ...
>Barry Margolin <······@bbnplanet.com> writes:
>
>> > (do ((whats-left a-list (cdr a-list))
>> > (result '() (cons (pop a-list) result)))
>> > (( eq whats-left '()) result)))
>>
>> Notice that there's no need to use a separate whats-left variable; a-list
>> is local to this function, so there's no reason not to assign to it
>> directly.
>
>Uh, that's not true, actually. There are potential reasons. They are
>not functional reasons, but they are reasons of modular coding style
>(i.e., to highlight that consuming the list is needed only within the
>loop) and also debugging (since it may be very useful when the
>debugger is entered mid-loop to see both the original list and the
>whats-left part). As far as debugging goes, not all compilers will
>show you this, and certainly not in all combinations of coimpiler
>optimization settings, but if they do it can be useful, so many
>programmers--myself included--often code for it.
For my part, since I'm a pretty lame coder anyway, I prefer to make such
things as obvious as possible, both for clarity (when revisiting old code),
and, as Kent P. says, for debugging. But then, unlike me, Barry M. is no
amateur, so I can see why he'd prefer the more compact and elegant version.
Raf
Raffael Cavallaro schrieb in Nachricht <··········@news-central.tiac.net>...
>
>(defun my-reverse (a-list)
> (do ((n (- 1) (incf n)) (result '() (cons (nth n a-list) result)))
> ((= n (- (length a-list) 1)) result )))
(defun my-reverse1 (a-list)
(do ((n (- 1) (incf n))
(result '() (cons (nth n a-list) result)))
((= n (- (length a-list) 1))
result)))
Your code is ******really******* slow.
- You don't need a counter variable n. Btw., in your DO loop, (incf n) could
be replaced by (+ n 1),
since DO already does the updating of n in every step.
- You are using NTH over and over. This amounts to n walks over 1/2 length
of the list.
- You are using LENGTH. This amounts to n additional walks over the list.
Find a version that just walks once over the list.
* Raffael Cavallaro
| (defun my-reverse (a-list)
| (do ((n (- 1) (incf n)) (result '() (cons (nth n a-list) result)))
| ((= n (- (length a-list) 1)) result )))
yikes.
(defun my-reverse (list)
(do ((reversed (list (pop list))
(cons (pop list) reversed)))
((endp list) reversed)))
#:Erik
--
religious cult update in light of new scientific discoveries:
"when we cannot go to the comet, the comet must come to us."
From: Martti Halminen
Subject: Re: Problem with iteration
Date:
Message-ID: <3515573B.1B77@dpe.fi>
Erik Naggum wrote:
>
> * Raffael Cavallaro
> | (defun my-reverse (a-list)
> | (do ((n (- 1) (incf n)) (result '() (cons (nth n a-list) result)))
> | ((= n (- (length a-list) 1)) result )))
>
> yikes.
>
> (defun my-reverse (list)
> (do ((reversed (list (pop list))
> (cons (pop list) reversed)))
> ((endp list) reversed)))
So as not to frighten all the newbies away from lisp, how about a
simpler version:
(defun my-reverse (list)
(let ((result nil))
(dolist (item list result)
(push item result))))
--
________________________________________________________________
^. Martti Halminen
/ \`. Design Power Europe Oy
/ \ `. Tekniikantie 12, FIN-02150 Espoo, Finland
/\`. \ | Tel:+358 9 4354 2306, Fax:+358 9 455 8575
/__\|___\| ······················@dpe.fi http://www.dpe.fi
In article <················@naggum.no>, Erik Naggum <······@naggum.no> wrote:
>
>(defun my-reverse (list)
> (do ((reversed (list (pop list))
> (cons (pop list) reversed)))
> ((endp list) reversed)))
...has a wee-bit of problem with the boundary condition of
(my-reverse nil ) ==> ( NIL ) ;; as opposed to just NIL.
there is a simpler starting value that could be used...
--
Lyman S. Taylor "Twinkie Cream; food of the Gods"
(·····@cc.gatech.edu) Jarod, "The Pretender"