删除方案中的子序列功能(深度递归) [英] Remove subsequence function (deep recursion) in scheme

问题描述

我正在尝试编写一个名为removesub*的函数，该函数接受两个参数(l1 and l2).该函数需要返回第二个列表，并且删除第一次出现的子序列.因此，如果第一个列表是'(a b c)，则第一个a，如果第二个列表被删除，则删除后的第一个b出现在删除后的a上，而第一个c出现在删除后b被删除-不管原子嵌套多深.

Im trying to write a function called removesub* which accepts two arguments (l1 and l2). The function needs to return the second list with the first occurence of the subsequence removed. So, if the first list is '(a b c), the first a if the second list is removed, the first b that appears after the removed a is removed, and the first c that appears after the removed b is removed - no matter how deep the atoms are nested.

工作示例

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

输出:(w (x b) (() ((y z))) a)

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

My current attempt doesnt seem to work because I have no way of sharing the l1 argument between nested recursive calls i.e. ((pair? (car l2)) (cons (removesub* l1 (car l2)) (removesub* l1 (cdr l2)))) splits l1 into two separate instances resulting in the following result. How can I share the l1 value so every recursive calls knows if the others have found the first instance of a value in l1?

工作示例

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

输出:(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)))))))

推荐答案

您需要将生成的符号传递给下一个迭代.有很多方法可以做到这一点.

You need to pass the resulting symbols to search for to the next iteration. THere are many ways to do this.

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

(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，然后将结果的两个部分都用于下一个.

Notice I do car first then use both parts of the result to do the next.

方案/球拍可以使用一个值返回多个值

(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处理的缺点

Not really a semantic difference over the first, but it might be a tad faster since in theory the results can stay on the stack rather than each result having to create a cons that can be GC-ed as fast as the stack unrolls.

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

(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实现在运行之前实际上对您的代码所做的事情差不多.

This works by the helper has a continuation argument. This is close to what many Scheme implementations actually do to your code before running.

您可以使用突变

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

Probably the fastest and easiest, but then you need to use #!r6rs or another standard Scheme rather than #!racket as implementation language.

这篇关于删除方案中的子序列功能(深度递归)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！