Message posted to comp.lang.lisp.franz before I realized that this was
a better place to post. Sorry about the crossposting.
I'm writing a function that should reverse a nested list. For example:
(reverse-list '(a b (c d (e) f (g (h i)) j) k))
should return:
(K (J ((I H) G) F (E) D C) B A)
It's an assignment so I'm not looking for complete code, that would be
cheating and I enjoy figuring out these things myself. I would be
happy just to get some pointers on how I should go about writing this
double-recursively. Just some pseudo-code. It would help loads.
Thanks,
Jakob
solipsist wrote:
> I'm writing a function that should reverse a nested list. For example:
>
> (reverse-list '(a b (c d (e) f (g (h i)) j) k))
>
> should return:
>
> (K (J ((I H) G) F (E) D C) B A)
>
> It's an assignment so I'm not looking for complete code, that would be
> cheating and I enjoy figuring out these things myself. I would be
> happy just to get some pointers on how I should go about writing this
> double-recursively. Just some pseudo-code. It would help loads.
Suppose you have a function `reverse-list', that reverses a "flat"
list by iterating through it and pushing each item onto the front of
an output list. Each time you process an item, check whether it's a
list: if so, add `(reverse-list item)' instead of `item' to the output
list.
Jeremy.
solipsist wrote:
> Message posted to comp.lang.lisp.franz before I realized that this was
> a better place to post. Sorry about the crossposting.
>
>
> I'm writing a function that should reverse a nested list. For example:
>
> (reverse-list '(a b (c d (e) f (g (h i)) j) k))
>
> should return:
>
> (K (J ((I H) G) F (E) D C) B A)
>
> It's an assignment so I'm not looking for complete code, that would be
> cheating and I enjoy figuring out these things myself. I would be
> happy just to get some pointers on how I should go about writing this
> double-recursively. Just some pseudo-code. It would help loads.
>
>
> Thanks,
>
> Jakob
As you CDR down the list, processing each top-level element, you need to
reverse each of them too rather than placing them 'as is' into the
result. The reverse of a non-NULL atom is itself. The reverse of an
embedded list is your total-reverse function applied to it.
David Sletten
Hi,
Thanks David and Jeremy for very speedy and informative replies! As usual,
it was far simpler than I originally thought, as it usually is with Lisp :).
Our code:
(defun reverse-list (list)
(cond
((endp list) nil)
((listp (car list)) (cons (reverse (reverse-list (car list)))
(reverse-list (cdr list))))
(t (cons (car list) (reverse-list (cdr list))))))
Only problem is that it only operates on this kind of list:
(reverse-list '((a b (c d (e) f (g (h i)) j) k)))
In other words, we need to put the list within in a list, but it appears to
be what our instructors want so it's fine. But still, it would be nice to
make it more generic so that it could process:
(reverse-list '((a b (c d (e) f (g (h i)) j) k)))
I tried checking for a top-level list with a COND and LISTP statement but it
would mess up the program logic:
(defun reverse-list (list)
(cond
((endp list) nil)
((listp list) (reverse (reverse-list list)))
((listp (car list)) (cons (reverse (reverse-list (car list)))
(reverse-list (cdr list))))
(t (cons (car list) (reverse-list (cdr list))))))
There's probably a better way to do it. Thanks once again.
Thanks,
Jakob
"David Sletten" <·····@slytobias.com> skrev i meddelandet
·······················@twister.socal.rr.com...
> solipsist wrote:
>
> > Message posted to comp.lang.lisp.franz before I realized that this was
> > a better place to post. Sorry about the crossposting.
> >
> >
> > I'm writing a function that should reverse a nested list. For example:
> >
> > (reverse-list '(a b (c d (e) f (g (h i)) j) k))
> >
> > should return:
> >
> > (K (J ((I H) G) F (E) D C) B A)
> >
> > It's an assignment so I'm not looking for complete code, that would be
> > cheating and I enjoy figuring out these things myself. I would be
> > happy just to get some pointers on how I should go about writing this
> > double-recursively. Just some pseudo-code. It would help loads.
> >
> >
> > Thanks,
> >
> > Jakob
>
> As you CDR down the list, processing each top-level element, you need to
> reverse each of them too rather than placing them 'as is' into the
> result. The reverse of a non-NULL atom is itself. The reverse of an
> embedded list is your total-reverse function applied to it.
>
> David Sletten
solipsist wrote:
> Hi,
>
> Thanks David and Jeremy for very speedy and informative replies! As usual,
> it was far simpler than I originally thought, as it usually is with Lisp :).
> Our code:
>
> (defun reverse-list (list)
> (cond
> ((endp list) nil)
> ((listp (car list)) (cons (reverse (reverse-list (car list)))
> (reverse-list (cdr list))))
> (t (cons (car list) (reverse-list (cdr list))))))
>
Well, I don't know what your instructor will allow, but this seems like
cheating a bit to me. You shouldn't be using the built-in REVERSE
function...Also I think this function is working differently than you
realize. That's why you are puzzled about its failure to handle '(a b (c
d (e) f (g (h i)) j) k).
Here's a hint so you can take one more stab at it. Let's consider
defining the basic REVERSE function. We want to look at each top-level
element and put it into a new list. Here is the basic procedure (but it
doesn't do what we want):
(defun reverse? (l)
(cond ((null l) '())
(t (cons (car l) (reverse? (cdr l)))) ))
This simply copies the original list (aka, COPY-LIST). The CONSing takes
place as the recursive calls resolve themselves in reverse order. So
(reverse? '(a b c)) => (cons 'a (cons 'b (cons 'c '())))
Even though A is the first element, the CONS that puts it in the list is
the last one to execute. Instead we want it to be the first:
(cons 'c (cons 'b (cons 'a '())))
The way to do this is to work with a second parameter known as an
'accumulator'--it accumulates the result for us:
(defun reverse (l result)
(cond ((null l) result)
(t (reverse (cdr l) (cons (car l) result)))) )
Now, given (reverse '(a b c) '()), RESULT successively is:
(a)
(b a)
(c b a) ;Done
This may look odd calling REVERSE with two arguments. In order to
maintain the normal interface we can define an auxiliary function to do
the real work:
(defun reverse (l)
(reverse-aux l '()))
(defun reverse-aux (l result) ...)
Now try using these ideas to create your TOTAL-REVERSE function. You
have 3 possibilities with each recursive call:
1. You are at the end of the list.
2. The CAR is an atom.
3. The CAR is a list.
You have to do something different in each case.
> Only problem is that it only operates on this kind of list:
>
> (reverse-list '((a b (c d (e) f (g (h i)) j) k)))
>
> In other words, we need to put the list within in a list, but it appears to
> be what our instructors want so it's fine. But still, it would be nice to
> make it more generic so that it could process:
>
> (reverse-list '((a b (c d (e) f (g (h i)) j) k)))
>
> I tried checking for a top-level list with a COND and LISTP statement but it
> would mess up the program logic:
>
> (defun reverse-list (list)
> (cond
> ((endp list) nil)
> ((listp list) (reverse (reverse-list list)))
> ((listp (car list)) (cons (reverse (reverse-list (car list)))
> (reverse-list (cdr list))))
> (t (cons (car list) (reverse-list (cdr list))))))
>
>
> There's probably a better way to do it. Thanks once again.
>
> Thanks,
>
> Jakob
David Sletten wrote:
*snip*
> This may look odd calling REVERSE with two arguments. In order to
> maintain the normal interface we can define an auxiliary function to do
> the real work:
> (defun reverse (l)
> (reverse-aux l '()))
>
> (defun reverse-aux (l result) ...)
In order to avoid polluting the namespace, you can make a local function
definition using (labels), like this:
(defun reverse (l)
(labels ((reverse-aux (l result) ...))
reverse-aux l '()))
Labels takes a list of function definitions, as you can see.
--
.sig missing, please inform if found.
Reward.
Correction:
> In other words, we need to put the list within in a list, but it
> appears to be what our instructors want so it's fine. But still, it
> would be nice to make it more generic so that it could process:
>
> (reverse-list '((a b (c d (e) f (g (h i)) j) k)))
Should be: (reverse-list '(a b (c d (e) f (g (h i)) j) k))
Jakob
"solipsist" <··········@hotmail.com> skrev i meddelandet
·················@news.island.liu.se...
>
> Hi,
>
> Thanks David and Jeremy for very speedy and informative replies! As usual,
> it was far simpler than I originally thought, as it usually is with Lisp
:).
> Our code:
>
> (defun reverse-list (list)
> (cond
> ((endp list) nil)
> ((listp (car list)) (cons (reverse (reverse-list (car list)))
> (reverse-list (cdr list))))
> (t (cons (car list) (reverse-list (cdr list))))))
>
> Only problem is that it only operates on this kind of list:
>
> (reverse-list '((a b (c d (e) f (g (h i)) j) k)))
>
> In other words, we need to put the list within in a list, but it appears
to
> be what our instructors want so it's fine. But still, it would be nice to
> make it more generic so that it could process:
>
> (reverse-list '((a b (c d (e) f (g (h i)) j) k)))
>
> I tried checking for a top-level list with a COND and LISTP statement but
it
> would mess up the program logic:
>
> (defun reverse-list (list)
> (cond
> ((endp list) nil)
> ((listp list) (reverse (reverse-list list)))
> ((listp (car list)) (cons (reverse (reverse-list (car list)))
> (reverse-list (cdr list))))
> (t (cons (car list) (reverse-list (cdr list))))))
>
>
> There's probably a better way to do it. Thanks once again.
>
> Thanks,
>
> Jakob
>
> "David Sletten" <·····@slytobias.com> skrev i meddelandet
> ·······················@twister.socal.rr.com...
> > solipsist wrote:
> >
> > > Message posted to comp.lang.lisp.franz before I realized that this was
> > > a better place to post. Sorry about the crossposting.
> > >
> > >
> > > I'm writing a function that should reverse a nested list. For example:
> > >
> > > (reverse-list '(a b (c d (e) f (g (h i)) j) k))
> > >
> > > should return:
> > >
> > > (K (J ((I H) G) F (E) D C) B A)
> > >
> > > It's an assignment so I'm not looking for complete code, that would be
> > > cheating and I enjoy figuring out these things myself. I would be
> > > happy just to get some pointers on how I should go about writing this
> > > double-recursively. Just some pseudo-code. It would help loads.
> > >
> > >
> > > Thanks,
> > >
> > > Jakob
> >
> > As you CDR down the list, processing each top-level element, you need to
> > reverse each of them too rather than placing them 'as is' into the
> > result. The reverse of a non-NULL atom is itself. The reverse of an
> > embedded list is your total-reverse function applied to it.
> >
> > David Sletten
>
>
>
>
I guess that your instructor is wanting you to use the
slinky technique.
http://slinky.org/
I hope you have actually played with this toy a child. If
you haven't then what follows will not make any sense at
all.
The toy is metal spring. It cascades down stairs. Each turn
of the spring flows from a higher step to a lower step.
Then when the last turn lands on the lower step its moment
makes it carry on to the step below that. All we care about
is that when the slinky goes down a step it ends up
upside-down. It has been reversed.
So write a function with two arguments higher-step and
lower-step. Start with your whole list in higher-step. Each
recursive call moves the top element from the higher-step
and adds it to the lower-step. When you have finished,
everything is on the lower-step, and miraculously reversed!
Use `trace' to see it go:
* (slinky '(a b c d e) nil)
0: (SLINKY (A B C D E) NIL)
1: (SLINKY (B C D E) (A))
2: (SLINKY (C D E) (B A))
3: (SLINKY (D E) (C B A))
4: (SLINKY (E) (D C B A))
5: (SLINKY NIL (E D C B A))
5: SLINKY returned (E D C B A)
4: SLINKY returned (E D C B A)
3: SLINKY returned (E D C B A)
2: SLINKY returned (E D C B A)
1: SLINKY returned (E D C B A)
0: SLINKY returned (E D C B A)
(E D C B A)
I hope that helps, that is usually the point of reverse
exercises.
Alan Crowe
Edinburgh
Scotland
Alan Crowe wrote:
> I guess that your instructor is wanting you to use the
> slinky technique.
>
> http://slinky.org/
>
> I hope you have actually played with this toy a child. If
> you haven't then what follows will not make any sense at
> all.
>
> The toy is metal spring. It cascades down stairs. Each turn
> of the spring flows from a higher step to a lower step.
> Then when the last turn lands on the lower step its moment
> makes it carry on to the step below that. All we care about
> is that when the slinky goes down a step it ends up
> upside-down. It has been reversed.
>
> So write a function with two arguments higher-step and
> lower-step. Start with your whole list in higher-step. Each
> recursive call moves the top element from the higher-step
> and adds it to the lower-step. When you have finished,
> everything is on the lower-step, and miraculously reversed!
>
> Use `trace' to see it go:
>
> * (slinky '(a b c d e) nil)
>
> 0: (SLINKY (A B C D E) NIL)
> 1: (SLINKY (B C D E) (A))
> 2: (SLINKY (C D E) (B A))
> 3: (SLINKY (D E) (C B A))
> 4: (SLINKY (E) (D C B A))
> 5: (SLINKY NIL (E D C B A))
> 5: SLINKY returned (E D C B A)
> 4: SLINKY returned (E D C B A)
> 3: SLINKY returned (E D C B A)
> 2: SLINKY returned (E D C B A)
> 1: SLINKY returned (E D C B A)
> 0: SLINKY returned (E D C B A)
> (E D C B A)
>
> I hope that helps, that is usually the point of reverse
> exercises.
>
> Alan Crowe
> Edinburgh
> Scotland
That's a nice analogy, Alan. One can easily visualize the coils of the
Slinky cascading downwards into a reversed state.
We haven't heard back from Jakob yet, but I'll go ahead and post what I
was hinting at:
(defun reverse-all (l)
(reverse-aux l '()))
(defun reverse-aux (l result)
(cond ((null l) result)
((atom (car l)) (reverse-aux (cdr l) (cons (car l) result)))
(t (reverse-aux (cdr l) (cons (reverse-all (car l)) result)))) )
Here we explicitly examine each of the 3 possibilities I mentioned:
1. End of list (L is NIL).
2. CAR of L is an atom...just CONS it.
3. CAR of L is a list...REVERSE-ALL of it then CONS it.
Here's another option, where the 'main' function actually does more
work. The auxiliary function is correspondingly simpler:
(defun reverse-all (l)
(cond ((atom l) l)
(t (reverse-aux l '()))))
(defun reverse-aux (l result)
(cond ((null l) result)
(t (reverse-aux (cdr l) (cons (reverse-all (car l)) result)))) )
Note that these two implementations of REVERSE-ALL will respond
differently here:
(reverse-all 'a)
Finally, we can bundle everything all together. Notice that this
implementation of REVERSE-AUX is also slightly different. Its input is
initially L, but then it handles both CARs and CDRs--so OBJ may be
either an atom or a list. This is why I don't use ENDP.
(defun reverse-all (l)
(labels ((reverse-aux (obj result)
(cond ((null obj) result)
((atom obj) obj)
(t (reverse-aux (cdr obj)
(cons (reverse-all (car obj))
result)))) ))
(reverse-aux l '())))
And for those who aren't sick of REVERSE yet, here's a way to implement
it without an accumulator:
(defun mega-reverse (l)
(cond ((null (cdr l)) l) ; done if l is () or (a)
(t (cons (car (mega-reverse (cdr l)))
(mega-reverse (cons (car l)
(mega-reverse
(cdr (mega-reverse (cdr l)))) )))) ))
In a nutshell, the main T clause effectively does this:
(cons (car (last l)) (reverse (butlast l)))
Try it with TRACE and _VERY SHORT_ sample lists.
David Sletten
> I'm writing a function that should reverse a nested list. For
> example:
>
> (reverse-list '(a b (c d (e) f (g (h i)) j) k))
>
> should return:
>
> (K (J ((I H) G) F (E) D C) B A)
>
> It's an assignment so I'm not looking for complete code, that would
> be cheating and I enjoy figuring out these things myself. I would be
> happy just to get some pointers on how I should go about writing
> this double-recursively. Just some pseudo-code. It would help loads.
Since I note that you already posted your code, here's my solution:
(defun reverse-list (thing)
(cond ((atom thing) thing)
(t (append (reverse-list (cdr thing))
(list (reverse-list (car thing)))))))
CL-USER> (reverse-list '(a b (c d (e) f (g (h i)) j) k))
(K (J ((I H) G) F (E) D C) B A)
CL-USER> (reverse-list '((a b (c d (e) f (g (h i)) j) k)))
((K (J ((I H) G) F (E) D C) B A))
I know it's not efficient because of the append, but I think it
captures the idea of taking the list apart and putting it back
together.
Note that you don't have to test for nil, since nil is an atom.
Probably the hardest part of the problem is figuring out how to get
the list structure right when you put things back together, and not
wind up with extraneous nils or dotted lists.
--
Fred Gilham gilham @ csl . sri . com
King Christ, this world is all aleak, / And life preservers there are none,
And waves that only He may walk / Who dared to call Himself a man.
-- e. e. cummings, from Jehovah Buried, Satan Dead
As Fred pointed out about you having posted your code, and it being safe
to post solutions, I'm relatively new to Lisp, but here's mine:
(defun reverse-list (thing)
(labels ((rec (in out)
(cond (in (rec (cdr in) (cons (reverse-list (car in))
out)))
(t out))))
(cond ((atom thing) thing)
(t (rec thing '())))))