| Author |
backwards list question
|
|
| Joey Fox 2006-04-20, 4:04 am |
| i know this procedure works because I tried it, created it from
trial-and-error:
(define (backwards-list deep-list)
(cond ( (null? deep-list) '())
( (not (list? deep-list)) deep-list)
(else (reverse (cons (backwards-list (car deep-list))
(backwards-list (reverse
(cdr deep-list))))))))
but could someone explain to me why it works?
also, when you visualize what these procedures are doing, is there some
trick like drawing out a special kind of tree diagram? in class we only
learned how to trace simple recursion. so i don't know how to trace
two-call recursion.
| |
| pschombe@uci.edu 2006-04-20, 4:04 am |
| I don't know how your trial and error version works, but I can explain
this version if it doesn't strike you as obvious:
(define (backwards-list deep-list)
(reverse (map (lambda (x) (if (list? x) (backwards-list x) x))
deep-list)))
| |
| Joey Fox 2006-04-20, 4:04 am |
|
pschombe@uci.edu wrote:
> I don't know how your trial and error version works, but I can explain
> this version if it doesn't strike you as obvious:
>
> (define (backwards-list deep-list)
> (reverse (map (lambda (x) (if (list? x) (backwards-list x) x))
> deep-list)))
no it doesn't strike me as obvious. the part i don't get is why it
doesn't over reverse and scramble the order.
| |
| pschombe@uci.edu 2006-04-20, 4:04 am |
| The idea with the map version is that I know how to reverse a
non-nested list using reverse. The only difference between reverseing
a nested list and a non-nested list is that I must reverse any sublists
in the nested-list structure first. The map is used to reverse any
sub-lists. Once the sublists are reversed the containing list can be
reversed. Note that this map version is clear but not the most
efficient solution.
| |
| Joey Fox 2006-04-20, 4:04 am |
|
pschombe@uci.edu wrote:
> The idea with the map version is that I know how to reverse a
> non-nested list using reverse. The only difference between reverseing
> a nested list and a non-nested list is that I must reverse any sublists
> in the nested-list structure first. The map is used to reverse any
> sub-lists. Once the sublists are reversed the containing list can be
> reversed. Note that this map version is clear but not the most
> efficient solution.
why isn't it efficient?
i don't understand the delayed nature of the map version. does
everything build up into a long expression that gets unwound at the
end? or something else?
| |
| Jens Axel Søgaard 2006-04-20, 4:04 am |
| Joey Fox wrote:
> pschombe@uci.edu wrote:
>
>
> no it doesn't strike me as obvious. the part i don't get is why it
> doesn't over reverse and scramble the order.
This essentially does the same thing:
(define (back xs)
(cond
[(null? xs) '()]
[(list? xs) (reverse (map back xs))]
[else xs]))
Is that easier to understand?
--
Jens Axel Søgaard
| |
| Joey Fox 2006-04-20, 8:05 am |
|
> This essentially does the same thing:
>
> (define (back xs)
> (cond
> [(null? xs) '()]
> [(list? xs) (reverse (map back xs))]
> [else xs]))
>
> Is that easier to understand?
i don't understand. why is the nil list ever used, since it's not being
consed together? does that nil list get used for anything?
| |
| Jens Axel Søgaard 2006-04-20, 8:05 am |
| Joey Fox wrote:
>
>
> i don't understand. why is the nil list ever used, since it's not being
> consed together? does that nil list get used for anything?
Well, it is used. The first clause says, that if xs is the empty the
list, then the result is ().
But removing it works too :-)
(define (back xs)
(cond
[(list? xs) (reverse (map back xs))]
[else xs]))
If xs is the empty list, we have that
(reverse (map back xs))
= (reverse ())
= ()
--
Jens Axel Søgaard
| |
| Joey Fox 2006-04-20, 8:05 am |
|
>
> Well, it is used. The first clause says, that if xs is the empty the
> list, then the result is ().
right. that part i get. but the thing is, that never gets incorporated
into the final results. otherwise the list would be changed from the
original, no? when using cons, an empty list is needed at the end. when
using map, i assert it never gets incorporated into the solution. can
you prove me wrong?
>
> But removing it works too :-)
>
> (define (back xs)
> (cond
> [(list? xs) (reverse (map back xs))]
> [else xs]))
exactly. so that's another reason why i think that that branch either
never gets called, or never gets incorporated into the solution. if it
was called before, then this version would give an error message
because it doesn't return something in all cases. because this version
doesn't return an error message, i'm lead to believe that it was never
called. but i could be wrong, i just don't know how to prove one way or
another.
| |
| Jens Axel Søgaard 2006-04-20, 8:05 am |
| Joey Fox wrote:
>
> right. that part i get. but the thing is, that never gets incorporated
> into the final results. otherwise the list would be changed from the
> original, no? when using cons, an empty list is needed at the end.
> when using map, i assert it never gets incorporated into the solution.
> can you prove me wrong?
There is only one case: namely when back is called directly with
the empty list.
(define (back xs)
(cond
[(null? xs) 'FOO]
[(list? xs) (reverse (map back xs))]
[else xs]))
(back '())
>
>
> exactly. so that's another reason why i think that that branch either
> never gets called, or never gets incorporated into the solution. if it
> was called before, then this version would give an error message
> because it doesn't return something in all cases.
The else-clause catches all cases where xs is not a list.
--
Jens Axel Søgaard
| |
| Jens Axel Søgaard 2006-04-20, 8:05 am |
| Jens Axel Søgaard wrote:
> There is only one case: namely when back is called directly with
> the empty list.
>
> (define (back xs)
> (cond
> [(null? xs) 'FOO]
> [(list? xs) (reverse (map back xs))]
> [else xs]))
>
> (back '())
Oops. Forgot about the case where the empty list
is an element:
> (back '((1 2) () (3)))
((3) FOO(2 1))
--
Jens Axel Søgaard
| |
| Joey Fox 2006-04-20, 7:06 pm |
|
> The else-clause catches all cases where xs is not a list.
doh! i see now.
appreciate all the explanation.
|
|
|
|