Reverse list in Racket in O(n)

问题:

I need to write a recursive function in Scheme which takes a list of atoms and reverses it in linear time. I am only allowed to use define, lambda, cons, car, cdr, cond, let, and null? . Here is what I have so far:

(define reverse
  (lambda (lat)
    (cond
      ((null? lat) lat)
      (else (cons (reverse (cdr lat)) (cons (car lat) '()))))))

So when I call the function:

(reverse '(a b c d))

I get the following output:

'(() (((() 4) 3) 2) 1)

Any help would be very much appreciated.

回答1:

The problem is that if (reverse (cdr lat)) returns a list eg (3 2) then (cons '(3 2) (1)) turns into ((3 2) 1).

A classical way to do this would be to make a local procedure that takes an accumulator as well as the argument of the global procedure. As you are iterating the list from the beginning to the end you accumulate a list from the end to the beginning making it the exact reverse order from the argument. When the iterated list is null your answer is in the accumulator. As you notice you iterate once each element and when you hit the empty list you return the accumulator it's a perfect O(n)

As a hint:

(define (myreverse lst)
  (define (myreverse-aux lst acc)
    (if (null? <??>)
        <??>
        (myreverse-aux <??> (cons <??> <??>))))
  (myreverse-aux <??> <??>))

Here is a version using foldl

(define (myreverse lst)
  (foldl cons '() lst))