list - 合并跳跃对

Question

如何递归合并列表列表中的元素跳跃对？我需要有

'((a b c) (e d f) (g h i))

从

'((a b) c (e d) f (g h) i)

我的尝试

(define (f lst)      
  (if (or (null? lst)            
          (null? (cdr lst))) 
      '()                                                          
      (cons (append (car lst) (list (cadr lst))) 
            (list (append (caddr lst) (cdddr lst))))))

如果我定义有效

(define listi '((a b) c (d e) f))

我从中获得

((a b c) (d e f))

通过简单地做

(f listi)

但它不适用于更长的列表。我知道我需要递归，但我不知道在代码的最后一句中再次插入f的位置。

标签： listrecursionracket

Answer 1

您的算法失败的一个更简单的情况：(f '((1 2) 3))应该导致'((1 2 3))，但您的会导致错误。

我们将首先定义一些术语：

1. “元素”是常规元素，例如1or 'a。

2. “普通列表”只是没有嵌套列表的“元素”列表。例如，'(1 2 3)是一个简单的列表。'((1 2) 3)不是一个简单的列表。“简单列表”是：

   • 一份empty清单
   • 一个cons“元素”和下一个“普通列表”

3. “跳跃对列表”是偶数长度的列表，其中奇数索引有一个“普通列表”，偶数索引有一个元素。例如，'((1) 2 (a) 4)是“跳跃对列表”。“跳跃对列表”是：

   • 一份empty清单
   • 一个cons_
     1. 一份“简单的清单”
     2. 一个cons“元素”和下一个“跳跃对列表”

我们已经完成了术语。在编写函数之前，让我们从一些示例开始：

(f '())              equivalent to (f empty)

                     should output '()
                     equivalent to empty

(f '((1 2) 3))       equivalent to (f (cons (cons 1 (cons 2 empty)) 
                                            (cons 3 
                                                  empty)))

                     should output '((1 2 3))
                     equivalent to (cons (cons 1 (cons 2 (cons 3 empty)))
                                         empty)

(f '((1 2) 3 (4) a)) equivalent to (f (cons (cons 1 (cons 2 empty)) 
                                            (cons 3
                                                  (cons (cons 4 empty)
                                                        (cons 'a 
                                                              empty)))))

                     should output '((1 2 3) (4 a))
                     equivalent to (cons (cons 1 (cons 2 (cons 3 empty)))
                                         (cons (cons 4 (cons 'a empty))
                                               empty))

因此，f是一个使用“跳跃对列表”并返回“普通列表”列表的函数。

现在我们将编写函数f：

(define (f lst)
  ???)

注意的类型lst是“跳跃对列表”，所以我们直接对其进行案例分析：

(define (f lst)      
  (cond
    [(empty? lst) ???]               ;; the empty list case

    [else         ???                ;; the cons case has
                  (first lst)        ;; the "plain list",
                  (first (rest lst)) ;; the "element", and
                  (rest (rest lst))  ;; the next "list of jumping pairs"
                  ???]))             ;; that are available for us to use

从例子：

(f '())              equivalent to (f empty)

                     should output '()
                     equivalent to empty

我们知道空的情况应该返回一个空列表，所以让我们相应地填补这个漏洞：

(define (f lst)      
  (cond
    [(empty? lst) empty]             ;; the empty list case

    [else         ???                ;; the cons case has
                  (first lst)        ;; the "plain list",
                  (first (rest lst)) ;; the "element", and
                  (rest (rest lst))  ;; the next "list of jumping pairs"
                  ???]))             ;; that are available for us to use

从例子：

(f '((1 2) 3))       equivalent to    (f (cons (cons 1 (cons 2 empty)) 
                                               (cons 3 
                                                     empty)))

                     should output '((1 2 3))
                     equivalent to (cons (cons 1 (cons 2 (cons 3 empty)))
                                         empty)

我们知道我们肯定想把“元素”放到“普通列表”的后面，以获得我们想要的结果“普通列表”：

(define (f lst)      
  (cond
    [(empty? lst) empty] ;; the empty list case

    [else ;; the cons case has:
          ???

          ;; the resulting "plain list" that we want
          (append (first lst) (cons (first (rest lst)) empty))

          ;; the next "list of jumping pairs"
          (rest (rest lst))   

          ;; that are available for us to use
          ???]))              

我们还需要处理下一个“跳跃对列表”，但我们已经有办法处理它：f！

(define (f lst)      
  (cond
    [(empty? lst) empty] ;; the empty list case

    [else ;; the cons case has:
          ???

          ;; the resulting "plain list" that we want
          (append (first lst) (cons (first (rest lst)) empty))

          ;; the list of "plain list"
          (f (rest (rest lst)))

          ;; that are available for us to use
          ???]))

然后我们可以返回答案：

(define (f lst)      
  (cond
    [(empty? lst) empty] ;; the empty list case

    [else ;; the cons case returns
          ;; the resulting list of "plain list" that we want
          (cons (append (first lst) (cons (first (rest lst)) empty))
                (f (rest (rest lst))))]))