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

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的alternative子句的数据流图是

                   /-> 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 部分，然后反转它并前置最后一个元素。 简单。 :)

2020 年更新:这是一个基于 code 的 Scheme 版本通过 @Rörd来自 the comments , 因此它具有类似的可读性，用参数解构代替 Haskell 的模式匹配:

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