Hi, I don't understand why my function doesn't work like it's supposed to,
and yes I fairly new to LISP.
(I use Emacs-LISP under Win32).
See expected output at bottom...
The function, reverse-all, takes an argument - a list wich can contain any
amount of lists as elements etc.
and should reverse the list and any list(s) in the list.
/* CODE */
(defun reverse-all (l)
(setq reversed_list '()) ; reset
list-varible
(setq l_length (length l)) ; l_length is
length of list
(setq count_1 0) ; reset counter
x
(while (< count_1 l_length) ; repeat for every
element x in list
(setq element_1 (nth count_1 l)) ; element_1 = list[x]
(cond ((consp element_1) (setq reversed_list (append reversed_list
(list (reverse-all element_1)))))
; if
list[x]==LIST -> reverse-all & append
(t (setq reversed_list (append
reversed_list (list element_1)))))
; else
append list[x] to reversed_list[x]
(setq count_1 (1+ count_1)) ; increment counter by
1
)
(reverse reversed_list)
)
/* TEST RUN */
(reverse-all '(a b c)) ; ->(c b a) <- correct answer
RETURNS; (c b a)
(reverse-all '(a (b c) d e)) ; ->(e d (c b) a) <- correct
answer
RETURNS: ((b c) a)
(reverse-all '(a1 b1 c1 d1 (b2 c2) e f)) ; ->(f e (c2 b2) d1 c1 b1 a1) <-
correct answer
RETURNS: ((c2 b2) d1 c1 b1 a1))
(reverse-all '(a1 b1 c1 d1 (b2 c2)(b3 c3) e1 f1))
any help appriciated.
/Niclas
Here are some programming tips that may be helpful:
- A top-level SETQ in a DEFUN does not create a local variable.
It assigns a global variable. A consequence is that on recursive
call, the inner call's value will "bash" the outer call's value since
there is only one variable storage cell involved, not two, as you might
have erroneously expected.
- I don't recommend using _'s at all. Use hyphens. They are the norm
in most Lisp programmer's code and it's polite to people with carpal
tunnel syndrome not to make them have to reach the shift key to use
your chosen names.
- The name l_length is overly complex. You don't have any other length
there. Just using "length" would be adequate. Ditto, count_1 could be
"count" (or perhaps better "position"). HOWEVER, you don't really want
to use a count and multiple calls to NTH. Consider instead using
a single variable named REMAINING-ELEMENTS which you initialize to
L and which later in the loop you set to (REST L) until there are no more
REMAINING-ELEMENTS.
- Don't ever use (SETQ something (APPEND something (LIST x))) in a loop
and then do a (REVERSE something) at the end; instead consider doing
(SETQ something (CONS x something)) and noticing that the something is
already backward (and hence requires no reversal) at the end. The good
thing about this is that CONS works in O(1) time, while APPEND works in
O(n) time where n is the length of the thing being appended to. A series
of calls to APPEND will be algorithmically slower than a series of calls
to CONS. If you don't know about big-O notation for the expression of
the time it takes something to execute, ask your instructor.
- Good luck with your homework. I hope these tips help you clean your
program up. I deliberately tried not to write actual code for you.
It's good for you to think about things and revise it yourself.
"Niclas Lars�n" <·············@swipnet.se> writes:
> Hi, I don't understand why my function doesn't work like it's supposed to,
> and yes I fairly new to LISP.
> (I use Emacs-LISP under Win32).
> See expected output at bottom...
>
> The function, reverse-all, takes an argument - a list wich can contain any
> amount of lists as elements etc.
> and should reverse the list and any list(s) in the list.
> /* CODE */
>
> (defun reverse-all (l)
> (setq reversed_list '()) ; reset
> list-varible
> (setq l_length (length l)) ; l_length is
> length of list
> (setq count_1 0) ; reset counter
> x
> (while (< count_1 l_length) ; repeat for every
> element x in list
> (setq element_1 (nth count_1 l)) ; element_1 = list[x]
> (cond ((consp element_1) (setq reversed_list (append reversed_list
> (list (reverse-all element_1)))))
ok i think i see a better way to do this.
don't try explicit iteration. the usual way to handle nested lists is
to use recursion.
peter norvig had a very good suggestion about how to consider doing
recursion upon nested lists
<URL:http://x68.deja.com/[ST_rn=ps]/getdoc.xp?AN=604838482&CONTEXT=965939595.82051095&hitnum=0>
(i am sure there is a shorter url, but i don't know how it's done)
if the input is a an atom, leave it alone.
if the input is a list, reverse it, and run reverse-all on all its
elements (which may well be lists)
(defun reverse-all (list)
(cond
((consp list)
(mapcar #'reverse-all (reverse list)))
(t list)))
this seems to pass my simple demo cases (in emacs)
(reverse-all '(foo bar))
(bar foo)
(reverse-all '(foo bar (qux big)))
((big qux) bar foo)
--
J o h a n K u l l s t a m
[········@ne.mediaone.net]
sysengr
0) Try to set your mailer to not wrap the lines :)
1) You are running into a problem with using global variables inside
your function instead of local ones, so that will be helped by
introducing some LET forms to your code.
When you use global variables, the recursive calls to the function
clobber the values and you get bizarre behavior like what you noticed.
If you replace the first three SETQ forms with a LET binding form, and
put the closing parenthesis of the binding form at the end of your
program, you will get correct behavior.
Some other observations:
2) You almost certainly don't want to use NTH to access elements of a
list. Lists are not vectors and don't have random access to elements.
In Common Lisp I would use something like dolist or loop to iterate over
the elements. Hmmm, it seems that Emacs Lisp has DOLIST.
3) Append is also quite expensive. Since you are already accumulating
the reversed list, I would just use PUSH or SETQ and CONS.
These changes lead to a much simpler program:
(defun reverse-all (l)
(let ((reversed-list '())) ; accumulate answer
(dolist (i l)
(if (consp i)
(push (reverse-all i) reversed-list) ; recurse on conses
(push i reversed-list))) ; otherwise accumulate
reversed-list ))
--
Thomas A. Russ, USC/Information Sciences Institute ···@isi.edu
> Hi, I don't understand why my function doesn't work like it's supposed to,
> and yes I fairly new to LISP.
mmm ... yes ... try to not program C or Pascal when writing lisp. You
probably don't need any assignmnent to variables at all, in this example.
> (I use Emacs-LISP under Win32).
> See expected output at bottom...
> The function, reverse-all, takes an argument - a list wich can contain any
> amount of lists as elements etc.
> and should reverse the list and any list(s) in the list.
That is, it must be recursive, since you'lll have to traverse a tree. A
typical example is when simply copying a complete tree, which would be done
recursively as:
(defun my-copy-tree (tree-node)
(if (atom tree-node) ;i.e., nil, or not a cons
tree-node ;leaf-node: recursion ends
(cons (my-copy-tree (car tree-node))
(my-copy-tree (cdr tree-node)))))
Now before you rush to hack this to reverse-all, try see if you can make
sense of this recursive version of reverse (which only reverses the top-level
structure of the list).
(defun my-reverse (list)
(if (atom list) list
(nconc (my-reverse (cdr list)) (list (car list)))))
If so, reverse-all should be easy. Cheers,
Philip
ps: look Ma, no assignments
--
When C++ is your hammer, everything looks like a thumb. (Steven Haflich)
-----------------------------------------------------------------------------
Philip Lijnzaad, ········@ebi.ac.uk \ European Bioinformatics Institute,rm A2-24
+44 (0)1223 49 4639 / Wellcome Trust Genome Campus, Hinxton
+44 (0)1223 49 4468 (fax) \ Cambridgeshire CB10 1SD, GREAT BRITAIN
PGP fingerprint: E1 03 BF 80 94 61 B6 FC 50 3D 1F 64 40 75 FB 53