5

我想知道如何仅使用基本操作（例如 cons、first、rest、empty？等）来反转列表。

不允许使用辅助函数或累加器，并且该函数只接受一个输入 - 一个列表。

有人告诉我这是可能的，尽管我无法理解它。

这是我到目前为止所概念化的。我不知道如何为列表的其余部分形成递归。

(defunc rev-list (x)
  (if (or (equal (len x) 0) (equal (len x) 1))
      x
      (cons (first (rev-list (rest x)))
            ???)))

显然，可以使用交换列表的第一个和最后一个的函数来做类似的事情，尽管我也不完全理解它。这是它的代码：

(define swap-ends (x)
  (if (or (equal (len x) 0) (equal (len x) 1))
      x
      (cons (first (swap-ends (rest x))) 
            (swap-ends (cons (first x) 
                             (rest (swap-ends (rest x))))))))
4

3 回答 3

5

(note: the answer is at the bottom of this post) The 2nd function,

(define (swap-ends x)                                   ; swap [] = []
  (if (or (equal (length x) 0) (equal (length x) 1))    ; swap [x] = [x]
      x                                                 ; swap (x:xs) 
      (cons (first (swap-ends (rest x)))                ;    | (a:b) <- swap xs 
            (swap-ends (cons (first x)                  ;    = a : swap (x : b)
                             (rest (swap-ends (rest x))))))))

(with Haskell translation in the comments) what does it do, you ask? The data flow diagram for if's alternative clause is

                   /-> first ----------------------> cons
x --> first ------/-------------> cons --> swap --/
  \-> rest -> swap ---> rest ---/

(follow the arrows from left to right). So,

[] -> []
[1] -> [1]
                     /-> 2 -----------------------> [2,1]
[1,2] --> 1 --------/------------> [1] --> [1] --/
      \-> [2] -> [2] ---> [] ---/

                           /-> 3 -------------------------> [3,2,1]
[1,2,3] --> 1 ------------/----------> [1,2] --> [2,1] --/
        \-> [2,3] -> [3,2] -> [2] --/

                             /-----> 4 ----------------------------> [4,2,3,1]
[1,2,3,4] --> 1 ------------/---------------> [1,3,2] -> [2,3,1] -/
          \-> [2,3,4] -> [4,3,2] -> [3,2] -/

So far it indeed does swap the end elements of a list. Let's prove it by the natural induction,

true(N-1) => true(N):

                       /-> N --------------------------------------> [N,2..N-1,1]
[1..N] --> 1 ---------/-----------> [1,3..N-1,2] -> [2,3..N-1,1] -/
       \-> [2..N] -> [N,3..N-1,2]   /
                    -> [3..N-1,2] -/

So it is proven. Thus, we need to devise a data flow diagram which, under the supposition of reversing an (N-1)-length list, will reverse an N-length list:

[1..N] --> 1 ------------------------------------\
       \-> [2..N] -> [N,N-1..2] -> N -------------\------------------\
                     \-> [N-1,N-2..2] -> [2..N-1] -> [1..N-1] -> rev -> cons

Which gives us the implementation

(define (rev ls)                                 ; rev [] = []
  (cond                                          ; rev [x] = [x]
    ((null? ls) ls)                              ; rev (x:xs) 
    ((null? (rest ls)) ls)                       ;   | (a:b) <- rev xs 
    (else                                        ;   = a : rev (x : rev b)
      (cons (first (rev (rest ls)))
            (rev (cons (first ls)
                       (rev (rest (rev (rest ls))))))))))

(rev '(1 2 3 4 5))     ; testing
;Value 13: (5 4 3 2 1)

The Haskell translation in the comments follows the diagram quite naturally. It is actually readable: a is the last element, b is the reversed "core" (i.e. the input list without its first and last element), so we reverse the reversed core, prepend the first element to get the butlast part of the input list, then reverse it and prepend the last element. Simple. :)

2020 update: here's a Scheme version based on the code by @Rörd from the comments, such that it is similarly readable, with arguments destructuring in place of Haskell's pattern matching:

(define (bind lst fun)
  (apply fun lst))

(define (rev lst)
  (if (or (null? lst)
          (null? (cdr lst)))
    lst
    (bind lst
      (lambda (first . rest)
         (bind (rev rest)
           (lambda (last . revd-core)
              (cons last (rev (cons first (rev revd-core))))))))))
于 2013-10-23T08:38:23.667 回答
2 
(define (reverse x)
  (let loop ((x x) (y '()))
    (if (null? x)
        y
        (let ((temp (cdr x)))
          (set-cdr! x y)
          (loop temp x))))))

真正有效地做到这一点的少数方法之一。但仍然是一个辅助程序。

其他方式，但不是尾递归，并且如果追加不使用 set-cdr！对于大型列表，它确实无法使用。

(define (reverse L)
  (if (null? l)
      '()
       (append (reverse (cdr L)) (list (car L)))))
于 2013-10-23T02:54:51.770 回答
1

你有last和butlast在你的环境中吗？如果是这样，可以像这样定义过程（尽管正如 Oscar 指出的那样，这不是您通常想要解决问题的方式）：

(define (rev lst)
  (if (null? lst)
      '()
      (cons (car (last lst))
            (rev (butlast lst)))))

以下是last和的定义butlast。如果它们不是您的默认环境的一部分，听起来它们对您的任务没有任何好处，但是当您开始时，最好通读并考虑大量递归过程。

(define (butlast lst)
  (if (or (null? lst) (null? (cdr lst)))
      '()
      (cons (car lst) (butlast (cdr lst)))))

(define (last lst)
  (if (or (null? lst) (null? (cdr lst)))
      lst
      (last (cdr lst))))
于 2013-10-22T23:43:16.810 回答