代码之家 › 专栏 › 技术社区 › Seol

每n次更换旧的

r5rs racket scheme

Seol · 技术社区 · 8 年前

我试图用lst替换每n次出现的旧的,新的,作为一个列表,它可以是原子列表或列表列表。当lst是列表列表时,我很难将第n次出现的旧项替换为新项。

(define (replace lst n old new)
  (cond ((null? lst) '())
        ((and (= n 1) (eq? (car lst) old)) (cons new (cdr lst)))
        ((not (atom? (car lst)))
          (cons (replace (car lst) n old new) (replace (cdr lst) n old new)))
        ((and (atom? (car lst)) (eq? (car lst) old)) (cons old (replace (cdr lst) (- n 1) old new)))
        (else (cons (car lst) (replace (cdr lst) n old new)))))

调用上述函数

(replace '(a b c a d e f g a t y a g) '3 'a 'o)

给我(a b c a d e f g o t y a g),但当我输入列表时,我无法获得正确的输出

(replace '((a a) b c a d e f g a t y a g) '3 'a 'o)

这可能是因为当我的函数进入列表(a)时,递减的my n计数器不会返回。有办法通过n计数器吗?

2 回复 | 直到 8 年前

Sylwester 8 年前

为了传递电流 n 从处理 car 到 cdr 您需要让助手返回结果和当前 n 。例如,以下内容将树中的每个匹配项替换为其项目编号:

(define (replace-with-index haystack needle)
  (define  (result n value) value)
  (let loop ((lst haystack) (n 0) (k result))
    (if (null? lst)
        (k n '())
        (let ((a (car lst)) (d (cdr lst)) (nn (+ n 1)))
          (cond ((equal? needle a)
                 (loop d nn (lambda (cn r) (k cn (cons n r)))))
                ((not (pair? a))
                 (loop d nn (lambda (cn r) (k cn (cons a r)))))
                (else
                 (loop a n (lambda (cn ar)
                             (loop d cn (lambda (cn dr)
                                          (k cn (cons ar dr))))))))))))

(replace-with-index '(a (a b (h e)) (c d (h e) l l)) '(h e)) 
; ==> (a (a b 3) (c d 6 l l))

这种技术被称为连续传球方式。您可以通过让它返回两个当前 n 和结果:

(define (replace-with-index haystack needle)  
  (define (helper lst n)
    (if (null? lst)
        (values n '())
        (let ((a (car lst)) (d (cdr lst)) (nn (+ n 1)))
          (cond ((equal? needle a)
                 (let-values ([(cn r) (helper d nn)])
                   (values cn (cons n r))))
                ((not (pair? a))
                 (let-values ([(cn r) (helper d nn)])
                   (values cn (cons a r))))
                (else
                 (let*-values ([(an ar) (helper a n)]
                               [(dn dr) (helper d an)])
                   (values dn (cons ar dr))))))))
  (let-values ([(n r) (helper haystack 0)])
    r))

这个版本和CPS版本的区别只是风格。由于许多方案实现实际上将代码转换为CP,因此执行的代码几乎相同。作为最后一个示例,我删除了多个值,并使用以下形式的封装 cons 。

(define (replace-with-index haystack needle)
  ;; abstraction
  (define nrbox cons)
  (define nrbox-n car)
  (define nrbox-r cdr)

  (define (helper lst n)
    (if (null? lst)
        (cons n '())
        (let ((a (car lst)) (d (cdr lst)) (nn (+ n 1)))
          (cond ((equal? needle a)
                 (let ((nr (helper d nn)))
                   (nrbox (nrbox-n nr) (cons n (nrbox-r nr)))))
                ((not (pair? a))
                 (let ((nr (helper d nn)))
                   (nrbox (nrbox-n nr) (cons a (nrbox-r nr)))))
                (else
                 (let* ((anr (helper a n))
                        (dnr (helper d (nrbox-n anr))))
                   (nrbox (nrbox-n dnr) (cons (nrbox-r anr) (nrbox-r dnr)))))))))
  (nrbox-r (helper haystack 0)))

基本上是这个 缺点 许多临时对,而多值和CPS版本将值保留在堆栈上。因此,不同之处在于性能。在抽象形式上,它们是完全相同的代码。

soegaard 8 年前

用新值替换旧值时,返回 (cons new (cdr lst)) 。问题是您没有替换中的任何剩余事件 (cdr lst) 。

尝试以下操作 (cons new (replace (cdr lst) original-n old new ) 。你需要原件 n ,因此您可以执行以下操作:

(define (replace lst n old new)
  (replace-helper lst n n old new))

(define replace-helper lst original-n n old new)
    ...your existing solution where replace has been
       renamed to replace-helper...))