替换球拍列表中一定数量的重复元素

Question

我正在尝试定义 “Gödel, Escher, Bach” (Douglas Hofstadter) 的“MIU 系统”的规则 3，它说：

Replace any III with a U

示例：

MIIIIU→MUIU andMIIIIU→MIUU

主要代码：


    (define (rule-tree lst)
    (if (<= 3 (counter lst #\I))
        (append (delete #\I lst) (list #\U))
        (append lst empty)))
    
    (define (delete x lst)
      (cond [(empty? lst) lst]
            [(eq? (first lst) x) (delete x (rest lst))]
            [else (append (list (first lst)) (delete x (rest lst)))]))
    
    (define (counter lst target)
      (if (empty? lst)
          0
          (+ (counter (rest lst) target) 
             (let ((x (first lst)))
               (if (list? x)
                   (counter x target) 
                   (if (eqv? x target) 1 0))))))

用这个表达式没问题:

>(rule-tree '(#\M #\I #\I #\I))
'(#\M #\U)

但我不知道如何确定在找到3个“I”时“U”所处的位置。任何建议都会很有帮助:)

Answer 1

这里是另一种递归版本，其中repl2编码信息“我们刚刚遇到一个#\I”，而repl3编码信息“我们刚刚遇到两个#\I”:

(define (repl lst)
  (cond ((empty? lst) lst)
        ((eqv? (first lst) #\I) (repl2 (rest lst)))
        (else (cons (first lst) (repl (rest lst))))))

(define (repl2 lst)
  (cond ((empty? lst) (list #\I))
        ((eqv? (first lst) #\I) (repl3 (rest lst)))
        (else (cons #\I (cons (first lst) (repl (rest lst)))))))

(define (repl3 lst)
  (cond ((empty? lst) (list #\I #\I))
        ((eqv? (first lst) #\I) (cons #\U (repl (rest lst))))
        (else (cons #\I (cons #\I (cons (first lst) (repl (rest lst))))))))

当然，这个解决方案是某种 hack，无法扩展到更多的重复次数。但是看看这个解决方案的结构并简单地概括我们可以产生一个通用解决方案的三个函数：

(define (repl lst n from to)
  (define (helper lst k)
    (cond ((empty? lst) (repeat from (- n k)))
          ((eqv? (first lst) from)
           (if (= k 1)
               (cons to (helper (rest lst) n))
               (helper (rest lst) (- k 1))))
          (else (append (repeat from (- n k))
                        (cons (first lst) (helper (rest lst) n))))))    

(define (repeat x n)
  (if (= n 0)
      '()
      (cons x (repeat x (- n 1)))))

我们定义了一个函数repl，它接受一个列表、要替换的副本数 (n)、要替换的元素 (from) 和必须替换的元素取代（to）。然后我们定义一个辅助函数来完成所有的工作，它的参数是要处理的列表和必须找到的副本数 (k).

每次函数遇到副本时，它都会检查我们是否已完成副本数并替换元素，重新开始其工作，否则它会减少要查找的副本数并继续。

如果它找到一个不同于 from 的元素，它会使用 repeat 之前“消耗”的元素重新创建列表（可能为 0），然后继续其工作。

请注意，当 lst 为 null 时，先前版本的辅助函数在最终情况下有错误。我们必须 return 可能跳过的 from 元素，而不是简单地 returning 空列表。

替换球拍列表中一定数量的重复元素

Replacing a certain number of repeated elements in a list in Racket

scheme

list

racket