删除方案中的子序列函数（深度递归）

Question

我正在尝试编写一个名为 removesub* 的函数，它接受两个参数 (l1 and l2)。该函数需要 return 删除第一次出现的子序列的第二个列表。所以，如果第一个列表是'(a b c)，如果第二个列表被移除，第一个a，移除a之后出现的第一个b，并且第一个c 在删除 b 之后出现 - 无论原子嵌套的深度如何。

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

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

您可以在助手中使用复合 return

(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 可以 return 多个具有值

的值

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

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

您可以使用连续传递样式：

(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 作为实现语言。

删除方案中的子序列函数（深度递归）

Remove subsequence function (deep recursion) in scheme

lisp

recursion

scheme

racket

尝试的解决方案 - 方案