如何仅使用基本操作递归地反转列表? [英] How to recursively reverse a list using only basic operations?

问题描述

我想知道如何仅使用基本操作(例如 cons、first、rest、empty? 等)来反转列表.

I was wondering how to reverse a list using only basic operations such as cons, first, rest, empty?, etc.

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

No helper functions or accumulators allowed, and the function only takes one input - a list.

有人告诉我这是可能的，但我无法理解它.

I was told it was possible, though I can't wrap my head around it.

这就是我目前已经概念化的内容.我不知道如何为列表的其余部分形成递归.

This is what I have conceptualized so far. I don't know how to form the recursion for the rest of the list.

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

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

Apparently it is possible to do something similar with a function that swaps the first and last of a list, though I don't fully understand it either. Here is the code for it:

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

推荐答案

(注意:答案在本文底部) 第二个功能，

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

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

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

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

这给了我们实现

(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 部分，然后反转它并在最后一个元素之前添加.简单. :)

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 年更新:这是基于 代码 由 @Rörd 来自 注释，因此它具有类似的可读性，参数解构代替了 Haskell 的模式匹配:

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

这篇关于如何仅使用基本操作递归地反转列表?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！