For a homework assignment, I have to write a LISP function that will
rotate a list to the left. For example, entering:
rotate-left(a b c)
is supposed to return:
(b c a)
My attempt is the following:
(defun ROTATE-LEFT(r)
(append (rest r) (first r))
)
However, when I type:
(ROTATE-LEFT '(a b c))
it returns:
(B C . A)
How can I get rid of that period? That is my only problem. I am using
GCL in Unix. Thanks for any help you can provide.
Trent
On Mon, 19 Feb 2001 02:39:09 GMT, Trent <··········@aol.comNOSPAM>
wrote:
>For a homework assignment, I have to write a LISP function that will
>rotate a list to the left. For example, entering:
>
>rotate-left(a b c)
>
>is supposed to return:
>(b c a)
>
>My attempt is the following:
>(defun ROTATE-LEFT(r)
> (append (rest r) (first r))
>)
This bracket must stand a line up. That's the cause of problem.
Well, also note that :
----------------( CLHS )---------------------
The arguments to append are lists. The result is a list that is the
concatenation of the arguments.
-------------------------------------------------
You are trying to append non-list (first r) to list.
>
>However, when I type:
>(ROTATE-LEFT '(a b c))
>
>it returns:
>(B C . A)
Arseny Slobodjuck wrote:
>
> On Mon, 19 Feb 2001 02:39:09 GMT, Trent <··········@aol.comNOSPAM>
> wrote:
>
> >For a homework assignment, I have to write a LISP function that will
> >rotate a list to the left. For example, entering:
> >
> >rotate-left(a b c)
> >
> >is supposed to return:
> >(b c a)
> >
> >My attempt is the following:
> >(defun ROTATE-LEFT(r)
> > (append (rest r) (first r))
> >)
> This bracket must stand a line up. That's the cause of problem.
> Well, also note that :
> ----------------( CLHS )---------------------
> The arguments to append are lists. The result is a list that is the
> concatenation of the arguments.
> -------------------------------------------------
> You are trying to append non-list (first r) to list.
> >
> >However, when I type:
> >(ROTATE-LEFT '(a b c))
> >
> >it returns:
> >(B C . A)
Thanks. I think I got it. My solution is:
(defun ROTATE-LEFT(r)
(append (rest r) (list (first r))))
It seems to work :)
--
Check out my videogame and PC game reviews at:
www.gamesdomain.com
www.mpog.com
www.strategy-gaming.com
www.gamepen.com
Latest Article: Fallout
http://www.gamesdomain.com/gdreview/adventure/falloutback.html
Trent wrote:
>
>
> Arseny Slobodjuck wrote:
>>
>> On Mon, 19 Feb 2001 02:39:09 GMT, Trent <··········@aol.comNOSPAM>
>> wrote:
>>
>> >For a homework assignment, I have to write a LISP function that will
>> >rotate a list to the left. For example, entering:
>> >
>> >rotate-left(a b c)
>> >
>> >is supposed to return:
>> >(b c a)
>> >
>> >My attempt is the following:
>> >(defun ROTATE-LEFT(r)
>> > (append (rest r) (first r))
>> >)
>> This bracket must stand a line up. That's the cause of problem.
>> Well, also note that :
>> ----------------( CLHS )---------------------
>> The arguments to append are lists. The result is a list that is the
>> concatenation of the arguments.
>> -------------------------------------------------
>> You are trying to append non-list (first r) to list.
>> >
>> >However, when I type:
>> >(ROTATE-LEFT '(a b c))
>> >
>> >it returns:
>> >(B C . A)
>
> Thanks. I think I got it. My solution is:
> (defun ROTATE-LEFT(r)
> (append (rest r) (list (first r))))
>
> It seems to work :)
Yes - and now do it without consing a new list.
Write a "nrotate-left" that modifies the list directly.
Regards,
Jochen
"Jochen Schmidt" <···@dataheaven.de> wrote in message
···················@ID-22205.news.dfncis.de...
> >
> > Thanks. I think I got it. My solution is:
> > (defun ROTATE-LEFT(r)
> > (append (rest r) (list (first r))))
> >
> > It seems to work :)
>
> Yes - and now do it without consing a new list.
>
> Write a "nrotate-left" that modifies the list directly.
>
> Regards,
> Jochen
Shouldn't it be
(defun ROTATE-LEFT(r)
(when r (append (rest r) (list (first r)))))
so that (rotate-left nil) returns nil instead of (nil)?
As for the second part, how's this:
(defun NROTATE-LEFT (lst)
(if (rest lst)
(let ((y (rest lst)))
(setf (rest lst) nil)
(setf (rest (last y)) lst)
y)
lst))
Geoff
Jochen Schmidt wrote:
>
> Write a "nrotate-left" that modifies the list directly.
What about
(defun nrotate-left (a)
(when a
(progn (rplacd (last a) (cons (car a) nil)) (cdr a))))
?
(Please don't beat me too hard...)
--
Vladimir Zolotych ······@eurocom.od.ua
"Geoff Summerhayes" <·············@hNoOtSmPaAiMl.com> writes:
> rplacd, right, I'll have to remember that. So that would change mine to...
>
> (defun NROTATE-LEFT (lst)
> (if (rest lst)
> (let ((y (rest lst)))
> (rplacd lst nil)
> (rplacd (last y) lst)
> y)
> lst))
If we are going to go down this path, in this modern day and age, it is
IMHO preferable to use setf of car/cdr (or first/rest) instead of
rplaca/rplacd. So this would get you to this version:
(defun nrotate-left (list)
(if (rest list)
(let ((result (rest list)))
(setf (rest list) nil
(rest (last result)) list)
result)
list))
Now we may note that the sequence of assignments might be better
expressed as a rotation between places:
cdr of last-cons <= list
list <= cdr of list
cdr of list <= nil (which is cdr of last-cons)
all done in parallel, and hence we can write:
(defun nrotate-left (list)
(when (rest list)
(rotatef (rest (last list)) list (rest list)))
list)
(Though I personally would prefer to use cdr instead of rest here,
because we are in fact doing operations that violate the list
abstraction).
Of course the last version seems far too clever for its own good... ;->
Regs, Pierre.
--
Pierre R. Mai <····@acm.org> http://www.pmsf.de/pmai/
The most likely way for the world to be destroyed, most experts agree,
is by accident. That's where we come in; we're computer professionals.
We cause accidents. -- Nathaniel Borenstein
"Pierre R. Mai" <····@acm.org> wrote in message
···················@orion.bln.pmsf.de...
> "Geoff Summerhayes" <·············@hNoOtSmPaAiMl.com> writes:
>
> > (defun NROTATE-LEFT (lst)
> > (if (rest lst)
> > (let ((y (rest lst)))
> > (rplacd lst nil)
> > (rplacd (last y) lst)
> > y)
> > lst))
<snip>
>
> (defun nrotate-left (list)
> (if (rest list)
> (let ((result (rest list)))
> (setf (rest list) nil
> (rest (last result)) list)
> result)
> list))
Tested these against each other, doesn't seem to make much difference
except for style.
>
> (defun nrotate-left (list)
> (when (rest list)
> (rotatef (rest (last list)) list (rest list)))
> list)
<snip>
> Of course the last version seems far too clever for its own good... ;->
Cute! A quick test seems to indicate it runs slower though.
I haven't tried them compiled yet. I will when I get home.
Geoff
"Geoff Summerhayes" <·············@hNoOtSmPaAiMl.com> writes:
> > > (defun NROTATE-LEFT (lst)
> > > (if (rest lst)
> > > (let ((y (rest lst)))
> > > (rplacd lst nil)
> > > (rplacd (last y) lst)
> > > y)
> > > lst))
> <snip>
> >
> > (defun nrotate-left (list)
> > (if (rest list)
> > (let ((result (rest list)))
> > (setf (rest list) nil
> > (rest (last result)) list)
> > result)
> > list))
>
> Tested these against each other, doesn't seem to make much difference
> except for style.
It was style that I was commenting about. Worrying about
micro-performance in these functions seems ill-placed, since you
shouldn't use them in any case in places where this kind of
performance matters. If you really have to rotate a set of elements
one step at a time in a tight inner-loop, you should probably use some
other datastructure and/or algorithm.
Regs, Pierre.
--
Pierre R. Mai <····@acm.org> http://www.pmsf.de/pmai/
The most likely way for the world to be destroyed, most experts agree,
is by accident. That's where we come in; we're computer professionals.
We cause accidents. -- Nathaniel Borenstein
"Pierre R. Mai" <····@acm.org> wrote in message
···················@orion.bln.pmsf.de...
>
> It was style that I was commenting about. Worrying about
> micro-performance in these functions seems ill-placed, since you
> shouldn't use them in any case in places where this kind of
> performance matters. If you really have to rotate a set of elements
> one step at a time in a tight inner-loop, you should probably use some
> other datastructure and/or algorithm.
>
I know, Knuth's "Premature optimization..."
OTOH, it strikes me that the only point of writing a destructive
version of a working algorithm is for timing considerations.
All in all you're probably right, I'm trying to fly before I've
learned to walk. I'm still trying to get enough of the vocabulary
down to actually attempt something useful.
Geoff
"Geoff Summerhayes" <·············@hNoOtSmPaAiMl.com> writes:
> "Pierre R. Mai" <····@acm.org> wrote in message
> ···················@orion.bln.pmsf.de...
> >
> > It was style that I was commenting about. Worrying about
> > micro-performance in these functions seems ill-placed, since you
> > shouldn't use them in any case in places where this kind of
> > performance matters. If you really have to rotate a set of elements
> > one step at a time in a tight inner-loop, you should probably use some
> > other datastructure and/or algorithm.
> >
>
> I know, Knuth's "Premature optimization..."
> OTOH, it strikes me that the only point of writing a destructive
> version of a working algorithm is for timing considerations.
> All in all you're probably right, I'm trying to fly before I've
> learned to walk.
I fear you misunderstood Pierre. I's ok to make optimizations to
functions. But the point is that list may be not the right data
structure for your purpose and optimizing it will not give you what
better data structure would give you. In other words -- optimize
algorithms and do microptimizations where they are really necessary
(and don't write inefficient code intentionally).
In the case at hand -- appending to the end of the list is a bad thing
to do since the time it takes to do it grows linearly with the size of
the list. Using queues in this situation would make it a constant time
operation.
> I'm still trying to get enough of the vocabulary down to actually
> attempt something useful.
This is the good and the bad thing about Lisp -- one can write poorly
performing but working Lisp[1] program real fast.
Footnotes:
[1] This applies to Common Lisp order of magnitude more than to
Scheme. And in some cases it does not apply to Scheme at all.
--
Janis Dzerins
If million people say a stupid thing it's still a stupid thing.
Geoff Summerhayes wrote:
>> (defun nrotate-left (list)
>> (when (rest list)
>> (rotatef (rest (last list)) list (rest list)))
>> list)
>
> <snip>
>
>> Of course the last version seems far too clever for its own good... ;->
>
> Cute! A quick test seems to indicate it runs slower though.
> I haven't tried them compiled yet. I will when I get home.
This whole thing can only be seen as a toy to play a bit around with
list-structures. Yes i've started this subthread of writing a non-copying
version of the rotate-left example someone mentioned. I've not provided a
implementation because it was thought as an exercice to the first poster.
If you _really_ wanted to do this kind of thing you should use a vector
instead of a list. You then represent the beginning of the vector as a
index-counter that wraps around after reaching the end of the vector. So
rotating the datastructure would be no more than an "incf" (or decf) of the
index-counter. With this construct you can rotate by more than one element
in constant time by simply adding/subtracting more than one to the
index-counter.
Regards,
Jochen
"Pierre R. Mai" <····@acm.org> writes:
> "Geoff Summerhayes" <·············@hNoOtSmPaAiMl.com> writes:
>
> > rplacd, right, I'll have to remember that. So that would change mine to...
> >
> > (defun NROTATE-LEFT (lst)
> > (if (rest lst)
> > (let ((y (rest lst)))
> > (rplacd lst nil)
> > (rplacd (last y) lst)
> > y)
> > lst))
>
> If we are going to go down this path, in this modern day and age, it is
> IMHO preferable to use setf of car/cdr (or first/rest) instead of
> rplaca/rplacd.
I'm looking at this post out of context--I didn't see the original. But
I'd go farther and say:
If we are going down this path, in this modern day and age, then I'm
suspicious of the ultimate intent. The likelihood of this apparently
general-purpose operator having any correct and tasteful (i.e., good
style) application in any modern program seems to me very low.
That's not to say a good programmer shouldn't be able to reason about such
things. Just that in practice this presupposes certain things about
data structures and sharing that I think are just not typical of anything
I'd ever teach anyone to do or wnat to see them do on any program I ever
was working with them on. The result of this kind of thing making a
mistake is nearly impossible to debug.