Scheme function to reverse a list

问题:

For my programming languages class I'm supposed to write a function in Scheme to reverse a list without using the pre-made reverse function. So far what I got was

(define (reverseList lst)
(COND
((NULL? lst) '())
(ELSE (CONS (reverseList(CDR lst)) (CAR lst)))
))

The problem I'm having is that if I input a list, lets say (a b c) it gives me (((() . c) . b) . a).

How am I supposed to get a clean list without multiple sets of parenthesis and the .'s?

回答1:

The problem with your implementation is that cons isn't receiving a list as its second parameter, so the answer you're building isn't a proper list, remember: a proper list is constructed by consing an element with a list, and the last list is empty.

One possible workaround for this is to use a helper function that builds the answer in an accumulator parameter, consing the elements in reverse - incidentally, this solution is tail recursive:

(define (reverse lst)
  (reverse-helper lst '()))

(define (reverse-helper lst acc)
  (if (null? lst)
      acc
      (reverse-helper (cdr lst) (cons (car lst) acc))))

(reverse '(1 2 3 4 5))
=> '(5 4 3 2 1)

回答2:

You are half way there. The order of the elements in your result is correct, only the structure needs fixing.

What you want is to perform this transformation:

 (((() . c) . b) . a)           ; input
 --------------------
 (((() . c) . b) . a)   ()      ; trans-
  ((() . c) . b)       (a)      ;      for-
   (() . c)          (b a)      ;         mation
    ()             (c b a)      ;               steps
      --------------------
                   (c b a)      ;               result

This is easy to code. The car and cdr of the interim value are immediately available to us. At each step, the next interim-result is constructed by (cons (cdr interim-value) interim-result), and interim-result starts up as an empty list, because this is what we construct here - a list:

(define (transform-rev input)
   (let step  ( (interim-value    input)       ; initial set-up of 
                (interim-result    '() ) )     ;  the two loop variables
     (if (null? interim-value)
       interim-result                  ; return it in the end, or else
       (step  (car interim-value)      ; go on with the next interim value
              (cons                    ;      and the next interim result
                  (... what goes here? ...)
                  interim-result )))))

interim-result serves as an accumulator. This is what's known as "accumulator technique". step represents a loop's step coded with "named-let" syntax.

So overall reverse is

(define (my-reverse lst)
   (transform-rev 
       (reverseList lst)))

Can you tweak transform-rev so that it is able to accept the original list as an input, and thus skip the reverseList call? You only need to change the data-access parts, i.e. how you get the next interim value, and what you add into the interim result.

回答3:

Step through the list and keep appending the car of the list to the recursive call.

(define (reverseList lst)
(COND
((NULL? lst) '())
(ELSE (APPEND (reverseList(CDR lst)) (LIST (CAR      lst))))
))

回答4:

(define (my-reverse L)
 (fold cons '() L)) ;;left fold