如何仅使用基本操作递归反转列表？

Question

我想知道如何仅使用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))))))))

Answer 1

(注意:答案在这篇文章的底部)第二个功能,

(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))))))))

(在评论中使用Haskell翻译)你会问它做什么？if替代子句的数据流图是

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

(按照从左到右的箭头).所以,

[] -> []
[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] -/

到目前为止它确实交换了列表的结尾元素.让我们通过自然归纳来证明这一点,

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] -/

所以它被证明了.因此,我们需要设计一个数据流图,在反转(N-1)长度列表的假设下,它将反转一个N长度列表:

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

这给了我们实施

(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)

注释中的Haskell转换非常自然地遵循该图.它实际上是可读的:a是最后一个元素,b是反向的"核心"(即没有第一个和最后一个元素的输入列表),所以我们反转反转的核心,在第一个元素前面加上输入列表的butlast部分,然后反转它并添加最后一个元素.简单.:)