list - 我将如何在 Dr. Racket 中编写一个函数，该函数使用 2 个可能的符号列表并将它们替换为其他符号？

Question

我如何在 Dr. Racket 中编写一个函数，该函数使用 2 个可能的符号列表('c 或 'v)并将它们替换为其他符号？如果符号是 'c，那么它会被替换为 'c 'v如果符号是 'v，那么它会被替换为 'v 'c

到目前为止，这是我的代码:

(define (awesome c)
  (cond
    [(equal? c 'c) (list 'c 'v)]  
    [else (list 'v 'c)]))

(define (substitute los)
  (map awesome los))

如果我输入:

(substitute (list 'c 'v 'c 'c))

我想要的输出是

(list 'c 'v 'v 'c 'c 'v 'c 'v)

相反，我得到:

(list (list 'c 'v) (list 'v 'c) (list 'c 'v) (list 'c 'v))

为什么会这样？如何更正我的代码以获得正确的输出？谢谢。

Answer 1

一个简单的解决方案

输入中的每个符号都会在输出中生成一个包含两个符号的列表。使用 append 组合列表，例如:

scratch.rkt> (append '(c v) '(v c) '(c v) '(c v))
'(c v v c c v c v)

因为 map 正在创建一个包含子列表的列表，所以使用 apply 将 append 应用到子列表:

(define (substitute los)
  (apply append (map awesome los)))

示例交互:

scratch.rkt> (substitute (list 'c 'v 'c 'c))
'(c v v c c v c v)

增加一些灵 active

您可以通过使用术语重写规则列表来采取更灵活的方法。这将允许您在不更改代码的情况下更改替换规则。术语重写规则可以表示为列表的列表，用箭头将输入术语与重写分开:

(define cv-rules '((c -> c v)
                   (v -> v c)))

定义几个函数很有用，这些函数可以获取术语的规则和规则的重写列表。将这些操作抽象为函数使得以后更改规则的表示更容易，并有助于保持代码清晰:

(define (get-rule term rules)
  (assoc term rules))

(define (get-rewrites rule)
  (cddr rule))

此get-rewrites 函数可用于另一个根据规则重写术语的函数。在这里，任何没有特定规则的符号仅在列表中单独返回:

(define (rewrite-term x rules)
  (let ((rule (get-rule x rules)))
    (if rule
        (get-rewrites rule)
        (list x))))

现在可以将 rewrite-term 函数与重写规则一起映射到输入上。和以前一样，映射结果是一个子列表列表，因此 append 在返回之前应用于结果:

(define (rewrite terms rules)
  (apply append (map (lambda (x) (rewrite-term x rules)) terms)))

现在您可以通过定义一组新的重写规则轻松更改替换的方式。

交互示例:

scratch.rkt> (rewrite '(c v c c) cv-rules)
'(c v v c c v c v)
scratch.rkt> (rewrite '(c v c x c) cv-rules)
'(c v v c c v x c v)

递归重写

通过对 rewrite-term 函数稍作改动，您可以将重写规则递归地应用于嵌套的术语列表。当要重写的术语本身是一个没有重写规则的非空列表时，将对该术语调用 rewrite。请注意，所有重写在返回之前都包含在列表中。这个新函数对于原始规则的行为与以前一样，但也允许更复杂的规则:

(define (rewrite-term x rules)
  (let ((rule (get-rule x rules)))
    (cond (rule (get-rewrites rule))
          ((pair? x) (list (rewrite x rules)))
          (else
           (list x)))))

交互示例:

scratch.rkt> (define cv2-rules '((c -> v)
                                 (v -> (c v))))
scratch.rkt> (rewrite '(c v c c) cv2-rules)
'(v (c v) v v)
scratch.rkt> (rewrite '(v (c v) v v) cv2-rules)
'((c v) (v (c v)) (c v) (c v))
scratch.rkt> (rewrite '((c v) (v (c v)) (c v) (c v)) cv2-rules)
'((v (c v)) ((c v) (v (c v))) (v (c v)) (v (c v)))