O(n) 中 Racket 中的反向列表

Question

我需要在 Scheme 中编写一个递归函数，它接受一个原子列表并在线性时间内反转它。我只能使用 define、lambda、cons、car、cdr、cond、let 和 null？ .这是我目前所拥有的：

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

所以当我调用函数时：

(reverse '(a b c d))

我得到以下输出：

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

非常感谢任何帮助。

Answer 1

问题是如果 (reverse (cdr lat)) return 是一个列表，例如 (3 2) 那么 (cons '(3 2) (1)) 变成 ((3 2) 1)。

实现此目的的经典方法是创建一个本地过程，该过程采用累加器以及全局过程的参数。当您从头到尾迭代列表时，您会从头到尾累积一个列表，使其与参数的顺序完全相反。当迭代列表为空时，您的答案在累加器中。正如您注意到的那样，您对每个元素进行了一次迭代，当您点击空列表时，您 return 累加器是一个完美的 O(n)

提示：

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

这是一个使用foldl

的版本

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

O(n) 中 Racket 中的反向列表

Reverse list in Racket in O(n)

lisp

scheme

racket