scheme - 替换(可能嵌套的)列表中第一次出现的符号

Question

我想用可能包含列表的列表中的另一个符号(例如'+)替换某个符号(例如'-)的第一次出现.也就是说，

'(((-))) 会变成 '(((+)))

'((-) - b) 到 '((+) - b)

Answer 1

更新:

正如威尔尼斯 pointed out (谢谢!)，我原来的答案是错误的。请参阅下面的更新答案。

原始答案:

似乎延续传递风格在这里会有所帮助。

当此解决方案遍历(可能嵌套的)列表时，它通过延续函数 k 跟踪位置，该函数用于在找到给定符号时“转义”。

#lang racket

(define (replace-first lst old new)
  (let LOOP ([lst lst] [k (λ (x) x)]) ; invariant: (k lst) produces orig list
    (if (null? lst) 
        (k null)
        (let ([fst (car lst)])
          (cond [(pair? fst) (LOOP fst (λ (x) (k (cons x (cdr lst)))))]
                [(eq? fst old) (k (cons new (cdr lst)))]
                [else (LOOP (cdr lst) (λ (x) (k (cons fst x))))])))))

(module+ test
  (require rackunit)
  (check-equal? (replace-first '() '- '+) '())
  (check-equal? (replace-first '(*) '- '+) '(*))
  (check-equal? (replace-first '(-) '- '+) '(+))
  (check-equal? (replace-first '((-)) '- '+) '((+)))
  (check-equal? (replace-first '(((-))) '- '+) '(((+))))
  (check-equal? (replace-first '((-) - b) '- '+) '((+) - b)))

新答案:

我的原始答案仅进入嵌套列表，但不知道如何返回以继续检查列表的其余部分。为了解决这个问题，我添加了一个回溯 thunk，它会记住我们在进入嵌套列表之前的位置，以便我们可以在需要时从那里继续。

#lang racket

(define (replace-first lst old new)
  ; invariant: (k lst) produces orig list
  (let LOOP ([lst lst] [k (λ (x) x)] [back (λ () lst)]) 
    (if (null? lst) 
        (back)
        (let ([fst (car lst)])
          (cond [(pair? fst) 
                 (LOOP fst 
                       (λ (x) (k (cons x (cdr lst))))
                       (λ () (LOOP (cdr lst) (λ (x) (k (cons fst x))) back)))]
                [(eq? fst old) (k (cons new (cdr lst)))]
                [else (LOOP (cdr lst) (λ (x) (k (cons fst x))) back)])))))

(module+ test
  (require rackunit)
  (check-equal? (replace-first '() '- '+) '())
  (check-equal? (replace-first '(*) '- '+) '(*))
  (check-equal? (replace-first '(-) '- '+) '(+))
  (check-equal? (replace-first '((-)) '- '+) '((+)))
  (check-equal? (replace-first '(((-))) '- '+) '(((+))))
  (check-equal? (replace-first '((-) - b) '- '+) '((+) - b))
  (check-equal? (replace-first '((((11 2) 3 4) a) 6) 'a 'b) 
                '((((11 2) 3 4) b) 6))
  (check-equal? (replace-first '((((11 2) 3 4) (c a a)) 6) 'a 'b) 
                '((((11 2) 3 4) (c b a)) 6))
  (check-equal? (replace-first '((((11 2) 3 4) ((c (d e) (f a)))) 6) 'a 'b) 
                '((((11 2) 3 4) ((c (d e) (f b)))) 6))
  (check-equal? (replace-first '((((11 2) a 4) c) 6) 'a 'b) 
                '((((11 2) b 4) c) 6)))