方案列表中的替换值

Question

假设我有一个表示布尔表达式的任意列表：

'(a and (b or c)) 和另一个表示文字值的对列表

'((a . #t) (b . #f) (c . #t)))

我想要做的是用第二个列表中的值替换第一个列表中的值，return 一个新列表：

'(#t and (#f or #t))

例如，这段代码采用一个列表和一个关联列表，并成功地替换了其中的值，尽管我试图在给定一个conses列表而不是一个关联列表的情况下做同样的事情。它适用于 '(a b) '((a 1) (b 2)) -> '(1 2)，但我想改为使用 '((a . 1) (b . 2))。这是代码：

(define replace
    (lambda (ls a-list)
     (map (lambda (x)
            (let ((lookup (assq x a-list)))
              (if lookup
                  (cadr lookup)
                  x)))
          ls)))

有人知道怎么做吗？非常感谢！

Answer 1

像这样：

(define bool '(a and (b or c)))
(define pairs '((a . #t) (b . #f) (c . #t)))

(define (value-for-key lst key)
  (cond ((empty? lst) 'none)
        ((eq? key (caar lst))
         (cdar lst))
        (#t (value-for-key (cdr lst) key))))

(define (replace-bool lst vals)
  (cond ((empty? lst) lst)
        ((pair? (car lst)) (cons (replace-bool (car lst) vals)
                                 (replace-bool (cdr lst) vals)))
        (#t (let ((val-for-key (value-for-key vals (car lst))))
                (if (not (eq? val-for-key 'none))
                    (cons val-for-key (replace-bool (cdr lst) vals))
                    (cons (car lst) (replace-bool (cdr lst) vals)))))))

(replace-bool bool pairs)

-> (#t 和 (#f 或 #t))

第一个功能是在键值对和 returns 值对列表中搜索给定键或 'none，如果该键不在该列表中。
第二个函数遍历布尔表达式列表。在键值列表中搜索每个原子元素，如果找到，则将其替换。如果布尔表达式包含嵌套表达式，则递归遍历。

Answer 2

这里真正的问题似乎是需要一个适用于嵌套输入列表的解决方案。为此，可以编写一个 map-nested 过程。这是一个过程，它类似于通常 map 过程的简化版本，但适用于嵌套列表：

(define (map-nested proc xss)
  (if (null? xss)
      '()
      (let ((xs (car xss)))
        (if (pair? xs)
            (cons (map-nested proc xs)
                  (map-nested proc (cdr xss)))
            (cons (proc xs)
                  (map-nested proc (cdr xss)))))))

这与通常的 map 不同的一个方面是 map-nested 仅将一个列表作为输入；一个典型的 map 过程采用任意数量的列表，这些列表可以被映射。

map-nested 的上述实现不是尾递归的，这对于大型、深度嵌套的列表来说可能是个问题。将其重写为迭代（尾递归）过程并不太麻烦：

(define (map-nested proc xss)
  (let iter ((xss xss)
             (result '()))
    (if (null? xss)
        (reverse result)
        (let ((xs (car xss)))
          (if (pair? xs)
              (iter (cdr xss)
                    (cons (map-nested proc xs) result))
              (iter (cdr xss)
                    (cons (proc xs) result)))))))

这里 result 是一个累加器，它跟踪要返回的结果，使递归调用无需保留堆栈帧。请注意，result 必须在返回之前反转，因为输入中的元素被置于 result 的前面，从输入列表的前面开始。这里使用了一个named let形式；这是在 Scheme 和 Racket 中工作的另一个函数中设置本地过程的便捷方法。

要解决OP的问题，我们只需要利用map-nested；以上任一版本均可使用：

;;; `substs` is an a-list of the form `((a . x) (b . y) ...)`
(define (replace-elts xss substs)
  (map-nested (lambda (x)
                (let ((subst-pair (assoc x substs)))
                  (if subst-pair        ; subst-pair is #f if x is not found
                      (cdr subst-pair)  ; otherwise, subst-pair is a dotted pair
                      x)))
              xss))

在这里，map-nested 负责处理输入列表，无论它是否嵌套。给 proc 的过程负责在 substs 中找到替换，假定它是由点对组成的关联列表。如果需要两个元素的适当列表而不是点对，则 cdr 可以简单地更改为 cadr。当 subst 未提供对输入 xss 中值的替换时，该值保持不变。

根据实际使用情况，replace-elts可以通过多种方式更改为更方便或更不方便。

交互示例：

nested-map.rkt> (replace-elts '(a (b (c d) e))
                              '((a . 1) (b . 2) (c . 3) (d . 4) (e . 5)))
'(1 (2 (3 4) 5))

nested-map.rkt> (replace-elts '(a (b (c d) e))
                              '((a . 1) (b . 2) (c . 3) (d . 4)))
'(1 (2 (3 4) e))

nested-map.rkt> (replace-elts '(a and (b or c))
                              '((a . #t) (b . #f) (c . #t)))
'(#t and (#f or #t))

方案列表中的替换值

Substitute values in Scheme lists

scheme

functional-programming

list

substitution

racket