替换第 n 次出现的 old

Question

我正在尝试用 lst 替换第 n 次出现的 old 和 new，作为一个列表，可以是原子列表或列表列表。当 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 a) 时，我递减的 n 计数器没有返回。有没有办法通过n计数器？

Answer 1

当您用新值替换旧值时，您 return (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...))

Answer 2

为了将当前 n 从处理 car 传递到 cdr，您需要让助手 return 同时获得结果和当前 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))

这种技术称为延续传球风格。你可以在没有 return 当前 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版本的区别只是风格。由于许多 Scheme 实现实际上将代码转换为 CPS，因此执行的代码几乎相同。作为最后一个示例，我删除了多个值并使用 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)))

基本上这个 cons 很多临时对，而多值和 CPS 版本将值保存在堆栈中。因此，差异在于性能。在抽象形式上，它们是完全相同的代码。

替换第 n 次出现的 old

Replacing every nth occurence of old

scheme

racket

r5rs