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

Question

我将如何在 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))

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

标签： listlispracket

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)

添加一些灵活性

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

(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)))