recursion - 删除方案中的子序列函数(深度递归)

Question

我正在尝试编写一个名为 removesub* 的函数，它接受两个参数 (l1 和 l2)。该函数需要返回第二个列表，其中删除了第一次出现的子序列。因此，如果第一个列表是 '(a b c)，则第一个 a 如果第二个列表被删除，则第一个 b 出现在removed a 被移除，并且在被移除的 b 之后出现的第一个 c 被移除 - 无论原子嵌套有多深。

Working Example

Input: (removesub* '(a b) '(w (x b) ((a) ((y z))) b a))

Output: (w (x b) (() ((y z))) a)

我目前的尝试似乎不起作用，因为我无法在嵌套递归调用之间共享 l1 参数，即 ((pair? (car l2)) (cons (removesub* l1 (car l2)) (removesub * l1 (cdr l2)))) 将 l1 拆分为两个单独的实例，结果如下。 我如何共享 l1 值，以便每个递归调用都知道其他人是否已在 l1 中找到值的第一个实例？

Working Example

Input: (removesub* '(a b) '(w (x b) ((a) ((y z))) b a))

Output: (w (x b) (() ((y z))) b)

尝试的解决方案 - 方案

(define removesub*
  (lambda (l1 l2)
    (cond
      ((or (null? l1) (null? l2)) l2)
      ((pair? (car l2)) (cons (removesub* l1 (car l2)) (removesub* l1 (cdr l2))))
      ((eq? (car l1) (car l2)) (removesub* (cdr l1) (cdr l2)))
      (else (cons (car l2) (removesub* l1 (cdr l2)))))))

Answer 1

您需要将要搜索的结果符号传递给下一次迭代。有很多方法可以做到这一点。

您可以在助手中使用复合返回

(define (removesub* elements-in-order haystack)
  ;; just use a pair to pass result and the 
  ;; elements to continue searching for
  (define (result eio h)
    (cons eio h))

  (cdr
   (let rec ((eio elements-in-order)
             (h haystack))    
     (cond ((or (not (pair? eio))
                (not (pair? h)))
            (result eio h))
           ((pair? (car h))
            (let* ((r (rec eio (car h)))
                   (r2 (rec (car r) (cdr h))))
              (result (car r2) (cons (cdr r) (cdr r2)))))
           ((eq? (car eio) (car h))
            (rec (cdr eio) (cdr h)))
           (else
            (let ((r (rec eio (cdr h))))
              (result (car r) (cons (car h) (cdr r)))))))))

注意我先做 car 然后使用结果的两个部分来做下一步。

Scheme/Racket 可以返回多个带值的值

(define (removesub* elements-in-order haystack)
  (define (helper eio h)    
    (cond ((or (not (pair? eio))
               (not (pair? h)))
           (values eio h))
          ((pair? (car h))
           (let*-values ([(eiocar hcar) (helper eio (car h))]
                         [(eiocdr hcdr) (helper eiocar (cdr h))])
             (values eiocdr (cons hcar hcdr))))
          ((eq? (car eio) (car h))
           (helper (cdr eio) (cdr h)))
          (else
           (let-values ([(eiocdr hcdr) (helper eio (cdr h))])
             (values eiocdr (cons (car h) hcdr))))))

  (let-values ([(eio result) (helper elements-in-order haystack)])
    result))

与第一个相比语义上并没有真正的区别，但它可能会快一点，因为理论上结果可以保留在堆栈中，而不是每个结果都必须创建一个可以像堆栈展开一样快地进行 GC 处理的缺点.

您可以使用延续传递样式:

(define (removesub* elements-in-order haystack)  
  (let cps ((eio elements-in-order)
            (h haystack)
            (c (lambda (eio h) h)))    
    (cond ((or (not (pair? eio))
               (not (pair? h)))
           (c eio h))
          ((pair? (car h))
           (cps eio
                (car h)
                (lambda (eio hcar)
                  (cps eio
                       (cdr h)
                       (lambda (eio hcdr)
                         (c eio (cons hcar hcdr)))))))
          ((eq? (car eio) (car h))
           (cps (cdr eio) (cdr h) c))
          (else
           (cps eio
                (cdr h)
                (lambda (eio res)
                  (c eio (cons (car h) res))))))))

帮助者的作品有一个延续论点。这与许多 Scheme 实现在运行前对您的代码实际执行的操作很接近。

你可以使用突变

可能是最快和最简单的，但是您需要使用 #!r6rs 或其他标准 Scheme 而不是 #!racket 作为实现语言。