如何仅使用基本操作来递归地反转列表? [英] 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更新:这是方案代码，由

2020 update: here's the Scheme code by @Rörd from the comments, such that it is similarly readable, with arguments destructuring in place of Haskell's pattern matching (with some variables renamed):

(define (rev lst)
  (if (or (null? lst)
          (null? (cdr lst)))
      lst
      (apply (lambda (first . rest)
               (apply (lambda (last . revd-core)
                        (cons last (rev (cons first (rev revd-core)))))
                      (rev rest)))
             lst)))

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