Make a destructive reverse! function in scheme

问题:

I need to create a program that will reverse a list destructively. For example lets say..

scm> (define L (list 1 2 3 4))
scm> (reverse! L)
(4 3 2 1)
scm> L
(1)

Where L becomes the last element of the reversed list. I know I am supposed to use set-cdr! somehow but cannot figure out how to implement it.

回答1:

Because this looks like homework, I can't give you a straight answer. I'll show you the general structure of the solution, so you can figure out the details and fill-in the blanks:

(define (reverse! lst)
  (let loop ((lst lst)
             (acc '()))
    (if (null? lst)
        acc
        (let ((tail <?1?>))
          (set-cdr! <?2?> <?3?>)
          (loop tail lst)))))

(define lst (list 1 2 3 4))
lst
> (1 2 3 4)

(reverse! lst)
> (4 3 2 1)

lst
> (1)

In the above code:

• The original list is traversed using a named let for simplicity, given that another parameter is needed
• A new acc parameter is defined, to serve as the accumulator for the reversed list
• When the recursion ends, the answer in the accumulator is returned

Now, for the recursive step:

• In <?1?> we need to obtain a reference to the rest of the list and save it, given that we're going to modify it
• The key point lies in the line (set-cdr! <?2?> <?3?>). You'll have to set the next element of the current list to the previously accumulated, reversed list
• Finally, the recursion proceeds with the new accumulated values

Notice that in the end, the lst reference got modified in-place and now is pointing to the last element of the list. If you need lst to point to the reversed list, then simply do this:

(define lst (list 1 2 3 4))
lst
> (1 2 3 4)

(set! lst (reverse! lst))
lst
> (4 3 2 1)

The procedure described reverses a list destructively and doesn't create a new list (no cons operations are used.)

回答2:

You should read the section on mutators from the The Scheme Programming Language book. Also, look into the the case function in Scheme. Essentially, you can use the set! function to fundamentally change a definition and also give another output.

回答3:

How de fella UCB.

here is my solution for your HilAcke.

(define (reverse! L)
     (define (helper prev cur)
           (if (null? cur)
               prev
               (let ((next (cdr cur)))
                   (set-cdr! cur prev)
                   (helper cur next))))
     (helper '() L))

then after defined you can check with the usual

 (define L (list 1 2 3 4))
 (define LR (reverse! L))
 LR
 > (4 3 2 1)

回答4:

So I was wondering how to do this today since I needed it for a test. For every list with more than 1 element I keep the first cons in the argument as the first in the result. I make a fresh cons to hold the new last value with a dummy value, then I reverse the link for elements 2..n-1. In the end i set the car of the first cons and the new last. The result is the result of the last set-cdr!.

(define (reverse! lst)
  (if (or (null? lst)
          (null? (cdr lst)))
      'soup ; an undefined value. You may use something else
      (let ((last (list 1)))
        (let loop ((prev last) (cur (cdr lst)))
          (let ((next (cdr cur)))
            (if (pair? next)
                (begin
                  (set-cdr! cur prev)
                  (loop cur next))
                (begin
                  (set-car! last (car lst))
                  (set-car! lst (car cur))
                  (set-cdr! lst prev))))))))

Example:

(define test '(() (2) (3 4) (5 6 7) (8 9 10 11 12 13 14 16)))
(for-each reverse! test)
test ; ==> (() (2) (4 3) (7 6 5) (16 14 13 12 11 10 9 8))