替换列表中每个出现的元素，仅当它跟在指定元素之后时

Question

我正在尝试编写一个函数 replaceAfter(A X Y L) 仅当 X 出现在 A 之后时才用 Y 替换 L 中每次出现的 X。

示例：

replaceAfter d m t '(f d s d m p m h d m u m) -> '(f d s d t p m h m t u m)

这是我到目前为止想出的：

(define replaceAfter
    (lambda(A X Y L)
        (cond
            ( (null? L)          '() )
            ( (if (and (equal? (car L) A) (equal? (car (cdr L)) X) ) (cons (cons (car L) Y) (replaceAfter A X Y (cdr (cdr L))))) )
            (#t (cons (car L) (relaceAfter A X Y (cdr L))))
        )
    )
)

Answer 1

您应该从第二个分支中删除 IF。此外，这两个 CONSes 目前正在制作一个类似于 ((1 . 2) . 3) 而不是 (1 . (2 . 3)) 的列表。

(define (replace-after a x y l)
  (cond 
    ((< (length l) 2) l)
    ((and (equal? (car l) a)
          (equal? (cadr l) x))
     (cons (car l) (cons y (replace-after a x y (cddr l)))))
    (else (cons (car l) (replace-after a x y (cdr l))))))

Answer 2

这最容易通过执行迭代的子过程实现，在构建结果列表时逐步消耗列表 l。使用cons代替append不仅是性能上的提升，还有一个积极的作用，即结果列表的第一个元素是需要与a进行比较的前一个元素：

(define replace-after
  (lambda (a x y l)
    ; ---- sub procedure  
    (define iter
      (lambda (lst result)
        (if (null? lst)
            (reverse result)
            (let ((current (car lst)))
              (iter (cdr lst)
                    (cons (if (and (not (null? result))    ; there is a previous element
                                   (equal? (car result) a) ; previous is a
                                   (equal? current x))     ; current is x
                              y
                              current)
                          result))))))
    ; call iter
    (iter l '())))

当然你需要在最后反转结果，但这是在 Scheme 中进行的规范方式。

如果您添加一点 display 语句，您将看到它是如何工作的：

> (replace-after 'd 'm 't '(f d s d m p m h d m u m))
lst (f d s d m p m h d m u m)  - result ()
lst (d s d m p m h d m u m)  - result (f)
lst (s d m p m h d m u m)  - result (d f)
lst (d m p m h d m u m)  - result (s d f)
lst (m p m h d m u m)  - result (d s d f)
lst (p m h d m u m)  - result (t d s d f)
lst (m h d m u m)  - result (p t d s d f)
lst (h d m u m)  - result (m p t d s d f)
lst (d m u m)  - result (h m p t d s d f)
lst (m u m)  - result (d h m p t d s d f)
lst (u m)  - result (t d h m p t d s d f)
lst (m)  - result (u t d h m p t d s d f)
lst ()  - result (m u t d h m p t d s d f)
'(f d s d t p m h d t u m)

请注意，结果与您在问题中所写的不同，但我相信这个是正确的。

您的规范中唯一不清楚的情况如下：

> (replace-after 'd 'm 'd '(d m m))
lst (d m m)  - result ()
lst (m m)  - result (d)
lst (m)  - result (d d)
lst ()  - result (d d d)
'(d d d)

这实际上应该 return '(d d d) 还是 (d d m)？

Answer 3

(define replace-after
  (lambda (d m t lst)
    (let loop ((todo lst)
               (done '())
               (replace #f))
      (if (null? todo)
          (reverse done)
          (let ((item (car todo)))
            (loop (cdr todo)
                  (cons (if (and replace (eq? m item)) t item) done)
                  (eq? item d)))))))

替换列表中每个出现的元素，仅当它跟在指定元素之后时

Replacing every occurrence of an element in a list, only when it follows a specified element

lisp

recursion

scheme

functional-programming