Reputation: 37
I am learning Scheme and wanted to write a recursive program that reverses a given list.
In one test case however, I noticed that a (b c) e
-> e (b c) a
.
What I'm trying to get is a (b c) e
-> e (c b) a
.
This is what I have:
(define (deep-reverse lst)
(if (null? lst)
'()
(begin
(display (car lst))
(display "\n")
(if (null? (cdr lst))
'()
(append (deep-reverse (cdr lst)) (list (reverse (car lst))))
) //End of inner if
))) //End of begin, outer if, define
When I attempt to run the code with
(deep-reverse '(1 (b c) (a b)))
I get:
1
(b c)
(a b)
mcdr: contract violation
expected: mpair?
given: 1
The issue is with (list (reverse (car lst)))
, although in an isolated test case it works fine. Which leads me to believe that the issue may have to do with append.
Thank you in advance.
Edit: Going from (list (reverse (car lst)))
to (reverse (list(car lst)))
makes the code run without an error but doesn't reverse (a b)
to (b a)
.
Upvotes: 1
Views: 378
Reputation: 12051
As the error message explains, your problem is that you are trying to reverse a number. Firstly, let's remove some of the unnecessary conditions and debugging stuff in your program, arriving at this simpler program. Let's step through this program to see what's going on:
(define (deep-reverse lst)
(if (null? lst)
'()
(append (deep-reverse (cdr lst)) (list (reverse (car lst))))))
We start with
(deep-reverse '(1 (b c) (a b)))
Substituting the argument we get
(if (null? '(1 (b c) (a b)))
'()
(append (deep-reverse (cdr '(1 (b c) (a b))))
(list (reverse (car '(1 (b c) (a b)))))))
Because the condition is #f
, this simplifies to
(append (deep-reverse (cdr '(1 (b c) (a b))))
(list (reverse (car '(1 (b c) (a b))))))
To evaluate the first argument, first find the cdr
, and call deep-reverse
on that. I will skip the steps here but you should easily be able to test that it works correctly.
(append '((b a) (c b)) (list (reverse (car '(1 (b c) (a b))))))
Next we evaluate the car
:
(append '((b a) (c b)) (list (reverse 1)))
And here we see what the problem is: we can't reverse a single number!
The issue is that your deep-reverse
should have two distinct behaviours recursively:
There are two reasons why your current program does not do this properly:
'(((a b) (c d)) ((e f) (g h)))
correctlyThe easy fix is to add a condition to check if it's a pair?
first before attempting to reverse it. If it's not pair?
, then lst
must either be nil
(which we may leave as-is) or a non-list object (which we may also leave as-is)
(define (deep-reverse lst)
(if (pair? lst)
(append (deep-reverse (cdr lst)) (list (deep-reverse (car lst))))
lst))
Finally, I should note that the pattern we are using here is really a foldr
pattern. We can abstract away this pattern with foldr
:
(define (deep-reverse xs)
(cond ((pair? xs)
(foldr (lambda (x y) (append y (list (deep-reverse x)))) '() xs))
(else xs)))
But we note also that this is inefficient, because append
is an expensive operation. Modifying the algorithm to a tail recursive one makes it clear that this is actually a foldl
:
(define (deep-reverse xs)
(cond ((pair? xs)
(foldl (lambda (x y) (cons (deep-reverse x) y)) '() xs))
(else xs)))
which is how such a function might be written in typical idiomatic Scheme, or as pointed out by Will Ness,
(define (deep-reverse xs)
(cond ((pair? xs) (reverse (map deep-reverse xs)))
(else xs)))
Upvotes: 2