list - 在方案中查找和替换

Question

我需要编写一个查找和替换给定模式的方案程序，并且我已经让它只在一层嵌套上工作，但是当列表中的下一辆车是列表本身时，我的程序无法正确递归它.

这是我到目前为止所拥有的：

(define replace 
    (lambda (source target replacement) 
        (if (eqv? source target)
            replacement
            (if (null? source)
                '() ;;base case

                (if (equal? target (car source))
                    (cons replacement (replace (cdr source) target replacement))

                    (cons (car source)
                    (replace (cdr source) target replacement))
                )
            )
        )
    )
)

Answer 1

使用应替换eqv?为equal?. 使用eqv?不会给出您期望的结果，如下所示：

> (eqv? (list 1 2 3) (list 1 2 3))
#f
> (eqv? '(1 2) '(1 2))
#f ; some Schemes may return #t

关于您的代码，它更易读、更紧凑地编写为一系列cond子句：

(define (replace source target replacement) 
  (cond ((eqv? source target) replacement)
        ((null? source)      '()) ;;base case
        ((equal? target (car source))
         (cons replacement (replace (cdr source) target replacement)))
        ((not (list? (car source)))
         (cons (car source) (replace (cdr source) target replacement)))
        (else
         (cons (replace (car source) target replacement) 
               (replace (cdr source) target replacement)))))

此外，另一种可能更清楚地说明算法的方法（'handle carand cons it to hand of cdr'）是：

(define (replace source target replacement)
  (cond ((null? source)'())
        ((equal? source target) replacement)
        (else (let ((next (car source))
                    (rest (cdr source)))
                (cons (if (not (list? next))
                          next
                          (replace next target replacement))
                      (replace rest target replacement)))))

Answer 2

Your error is that you don't do replace on the car when it's not a match and it's not an atom. It's possible to write this very compact by allowing to follow all pairs.

(define (replace source target replacement) 
  (cond ((equal? source target) replacement) ;; equal, return replacement
        ((not (pair? source)) source)        ;; not equal && not pair, return source
        (else (cons (replace (car source) target replacement) ;; recurse
                    (replace (cdr source) target replacement)))))

Answer 3

在我的初始版本中，我没有检查 (car source) 是否是一个列表，因此它被视为一个单独的标记，以避免我添加了一个额外的条件：

(define replace 
    (lambda (source target replacement) 
        (if (eqv? source target)
            replacement
            (if (null? source)
                '() ;;base case

                (if (equal? target (car source))
                    (cons replacement (replace (cdr source) target replacement))

                    (if (not (list? (car source)))
                        (cons (car source) (replace (cdr source) target replacement))
                        (cons (replace (car source) target replacement) (replace (cdr source) target replacement))))))))