scheme - Lisp 中的嵌套列表问题

Question

所以我必须编写一个方法，它接受一个列表，如 (nested '(4 5 2 8)) 并返回 (4 (5 () 2) 8)。

我认为我需要编写 3 个支持方法来完成此操作。第一个获取列表的大小:

(define (sizeList L)
   (if (null? L) 0
      (+ 1 (sizeList (cdr L)))))

 input : (sizeList '(1 2 3 4 5 6 7))
 output: 7

第二个从列表中删除元素:

 (define (drop n L)
   (if (= (- n 1) 0) L
      (drop (- n 1) (cdr L))))

 input : (drop 5 '(1 2 3 4 5 6 7))
 output: (5 6 7)

第三个删除列表的最后一个元素:

 (define (remLast E)
     (if (null? (cdr E)) '()
        (cons (car E) (remLast (cdr E)))))

 input : (remLast '(1 2 3 4 5 6 7))
 output: (1 2 3 4 5 6)

对于嵌套方法，我想我需要做第一个元素的 car，然后用 drop 递归，然后删除最后一个元素但是对于我的生活我不知道该怎么做或者也许我只是不断地弄乱括号？有什么想法吗？

Answer 1

各种递归解决方案是可能的，但问题是更直观的解决方案性能非常差，因为它们的成本取决于输入列表大小的平方。

例如考虑这个简单的解决方案:

; return a copy of list l without the last element
(define (butlast l)
  (cond ((null? l) '())
        ((null? (cdr l)) '())
        (else (cons (car l) (butlast (cdr l))))))

; return the last element of list l
(define (last l)
  (cond ((null? l) '())
        ((null? (cdr l)) (car l))
        (else (last (cdr l)))))

; nest a linear list
(define (nested l)
  (cond ((null? l) '())
        ((null? (cdr l)) l)
        (else (list (car l) (nested (butlast (cdr l))) (last l)))))

在 nested 的每次递归调用中，都会调用 butlast 和 last:这意味着对于列表的前半部分我们必须扫描列表的两倍，这需要 O(n²) 的操作次数。

是否有可能找到一个递归解决方案，其中的操作数量只随列表的大小线性增长？答案是肯定的，这个解决方案的关键是反转列表，并在列表和它的反向上并行工作，通过一个辅助函数从两个列表中获取一个元素并在它们的 cdr< 上重复出现，并同时使用一个计数器在两个列表的前半部分都被考虑时停止处理。下面是该算法的一个可能实现:

(define (nested l)
  (define (aux l lr n)
    (cond ((= n 0) '())
          ((= n 1) (list (car l)))
          (else (list (car l) (aux (cdr l) (cdr lr) (- n 2)) (car lr)))))
  (aux l (reverse l) (length l)))

请注意，参数 n 从 (length l) 开始，并在每次递归时减 2:这允许管理具有偶数的列表的两种情况或奇数个元素。 reverse 是反转列表的原始函数，但如果您不能使用此原始函数，则可以通过以下方式使用递归算法实现它:

(define (reverse l)
  (define (aux first-list second-list)
    (if (null? first-list)
        second-list
        (aux (cdr first-list) (cons (car first-list) second-list))))
  (aux l '()))