How to reverse a list...
Francesco Moi
I'm trying to making a function that reverses a list:
(A B C D E F) ---> (F E D C B A)
My code is:
(loop for x in MyList
(setf MyList2 (append x MyList2)))
But it does not work.
Any suggestion?
Kaz Kylheku
One approach is to iterate over the list, and push the items onto the
front of a new list in the order they are visited. The simplest Common
Lisp idiom for iterating over lists is the dolist loop, and the standard
function for pushing onto a list is push. So the combination of the two
fits this problem well:
(defun imitation-reverse (in-list)
(let (rev-list)
(dolist (item in-list rev-list)
(push item rev-list))))
There is one bit of trickiness in the above, and it's that dolist has
a third parameter (or, more accurately, its first parameter has a third
sub-parameter). When the last loop iteration is done, dolist will evaluate
that third parameter, in this case the expression ``rev-list'', and return
its value. So that gives us a shorthand for returning the result list,
and a standard notation for indicating what the loop is trying to compute.
Nathan J Froyd
APPEND takes two list arguments. What you really want is something like
SNOC:
(defun snoc (item list)
(append (list item) list))
--
Nathan | fro...@rose-hulman.edu | http://www.rose-hulman.edu/~froydnj/
Yes, God had a deadline. So He wrote it all in Lisp.
Lisp. Everything else is just Turing complete.
Raymond Wiker
append works on lists; x is an element of a list.
(append (list x) MyList2) should work, but is not good lisp style (for
several reasons), mainly because there are other idioms that fit
better:
* (defvar *mylist* '(a b c d e f))
*MYLIST*
* (let ((res '()))
(loop for elt in *mylist*
do (push elt res))
res)
(F E D C B A)
* (let ((res '()))
(loop for elt in *mylist*
do (setf res (cons elt res)))
res)
(F E D C B A)
* (let ((res '()))
(loop for elt in *mylist*
do (setf res (append (list elt) res)))
res)
(F E D C B A)
*
--
Raymond Wiker Mail: Raymon...@fast.no
Senior Software Engineer Web: http://www.fast.no/
Fast Search & Transfer ASA Phone: +47 23 01 11 60
P.O. Box 1677 Vika Fax: +47 35 54 87 99
NO-0120 Oslo, NORWAY Mob: +47 48 01 11 60
Try FAST Search: http://alltheweb.com/
Steve Long
Frederic Brunel
In my opinion, an elegant and typical functional way to do this
is to use an auxiliary function taking a second argument to
accumulate the result:
(defun reverse-aux (l acc)
(if (nilp l)
acc
(reverse-aux (cdr l)
(append (list (car l)) acc))))
(defun my-reverse (l)
(reverse-aux l '()))
You could use the `label' special-form to declare the `reverse-aux'
function as a local function within the `my-reverse' function or
set the `acc' argument as an optional one!
Enjoy.
--
Frederic Brunel.
Josh Huber
<snip>
how about:
(defun my-reverse (lst)
(reduce #'(lambda (a b)
(cons b a))
lst :initial-value nil))
--
Josh Huber
Steve Long
improving efficiency here, but none as good as just using REVERSE.
(defun my-reverse (seq-in)
"PowerLisp 2.01 list, string, and general vector reversal (the hard
way)."
(cond
((consp seq-in)
(let ((result))
(dotimes (n (length seq-in) result)
(push (elt seq-in n) result))))
((stringp seq-in)
(let ((result ""))
(dotimes (n (length seq-in) result)
(setf result (concatenate 'string (string (elt seq-in n))
result)))))
((vectorp seq-in)
(let ((result))
(dotimes (n (length seq-in) (apply 'vector result))
(push (elt seq-in n) result))))
(t (error "MY-REVERSE: Arg type ~a not handled." (type-of
seq-in)))))
> (my-reverse '(1 2 3))
> (3 2 1)
> (my-reverse (vector 1 2 3))
> #(3 2 1)
> (my-reverse "123")
> "321"
Barry Margolin
Of course you are! I think there are no other other practical reasons why
someone would feel the need to implement REVERSE themselves, unless he had
some special requirements that the standard REVERSE can't meet (I don't
think the OP mentioned anything like that).
--
Barry Margolin, bar...@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.
Erik Naggum
| In my opinion, an elegant and typical functional way to do this is to use
| an auxiliary function taking a second argument to accumulate the result:
|
| (defun reverse-aux (l acc)
| (if (nilp l)
| acc
| (reverse-aux (cdr l)
| (append (list (car l)) acc))))
|
| (defun my-reverse (l)
| (reverse-aux l '()))
|
| You could use the `label' special-form to declare the `reverse-aux'
| function as a local function within the `my-reverse' function or set the
| `acc' argument as an optional one!
That would probably be elegant only in Scheme.
Please note that (append (list elt) list) is functionally identical to
(cons elt list), except that it copies and wastes the first argument.
This is another way to do it:
(defun reverse-list (list)
(do ((list list (cdr list))
(rev () (cons (car list) rev)))
((endp list) rev)))
///
--
The past is not more important than the future, despite what your culture
has taught you. Your future observations, conclusions, and beliefs are
more important to you than those in your past ever will be. The world is
changing so fast the balance between the past and the future has shifted.
Sashank Varma
france...@europe.com (Francesco Moi) wrote:
>...without using 'reverse' command?
>
>I'm trying to making a function that reverses a list:
>(A B C D E F) ---> (F E D C B A)
how about:
(defun moi-reverse (x)
(nreverse (copy-list x)))
if you go with this, please let us know your teacher's
response
Erik Naggum
| (cond
| ((consp seq-in) ...)
| ((stringp seq-in) ...)
| ((vectorp seq-in) ...)
| (t (error "MY-REVERSE: Arg type ~a not handled."
| (type-of seq-in)))))
This is what the typecase family is for. Incidentally, (reverse ()) is
well-defined.
(etypecase seq-in
(null nil) ;; special case
(cons ...)
(string ...) ;; special case
(vector ...))
Note that a string is a vector of type character and thet it might not
make much of a difference when you have to ensure that you return a
vector of the same type as you received, just like the standard says.
This is not particularly hard to do:
(make-array (length sequence) :element-type (array-element-type sequence))
Since the initial value of the array is irrelevant, you could also use
(copy-seq sequence)
which does this for you and may be just as fast.
Traversing a vector is not particularly hard, either:
(do ((forward 0 (1+ forward))
(backward (1- (length vector)) (1- backward))
(reversed (copy-seq sequence)))
((minusp backward) reversed)
(setf (aref reversed backward) (aref reversed forward)))
(There is no chance that any of this would be useful in homework. :)
Kent M Pitman
Hey, while we're at it, why not use the opportunity to learn a really
obscure operator:
(defun o-meu-reverse (x)
(nreconc (copy-list x) '()))
David Sletten
(defun my-reverse (l)
(cond ((null (cdr l)) l)
(t (cons (car (my-reverse (cdr l)))
(my-reverse (cons (car l) (my-reverse (cdr (my-reverse (cdr l)))) )))) ) )
Wolfhard Buß
> Traversing a vector is not particularly hard, either:
>
> (do ((forward 0 (1+ forward))
> (backward (1- (length vector)) (1- backward))
> (reversed (copy-seq sequence)))
> ((minusp backward) reversed)
> (setf (aref reversed backward) (aref reversed forward)))
>
Probably
(do ((forward 0 (1+ forward))
(backward (1- (length sequence)) (1- backward))
(reversed (copy-seq sequence)))
((<= backward forward) reversed)
(rotatef (aref reversed backward) (aref reversed forward))))
comes close to your intentions.
--
"Das Auto hat keine Zukunft. Ich setze aufs Pferd." Wilhelm II. (1859-1941)
Erik Naggum
> Traversing a vector is not particularly hard, either:
>
> (do ((forward 0 (1+ forward))
> (backward (1- (length vector)) (1- backward))
> (reversed (copy-seq sequence)))
> ((minusp backward) reversed)
> (setf (aref reversed backward) (aref reversed forward)))
* Wolfhard Buß
| Probably
|
| (do ((forward 0 (1+ forward))
| (backward (1- (length sequence)) (1- backward))
| (reversed (copy-seq sequence)))
| ((<= backward forward) reversed)
| (rotatef (aref reversed backward) (aref reversed forward))))
|
| comes close to your intentions.
That's a good variation. What I intended was actually to use
(aref sequence forward), but it got mixed up somehow.
Steve Long
compiler (minimal array support.)
sl
glauber
[...]
> This is another way to do it:
>
> (defun reverse-list (list)
> (do ((list list (cdr list))
> (rev () (cons (car list) rev)))
> ((endp list) rev)))
Nice!
g