在Scheme中从字符串中删除重复字符

Question

我一直在尝试回答这个问题，但是没有取得太大进展。该问题要求生成一个字符串，其中输入字符串中所有重复字符都被替换为该字符的单个实例。

例如，

(remove-repeats "aaaab") => "ab"
(remove-repeats "caaabb aa") => "cab a"

"因为我正在尝试使用累积递归来完成这个任务，所以到目前为止我已经做了："

(define (remove-repeats s) 
  (local
    [(define (remove-repeats-acc s1 removed-so-far)
      (cond
        [(empty? (string->list s1))""]
        [else 
         (cond
           [(equal? (first (string->list s1)) (second (string->list s1))) 
         (list->string (remove-repeats-acc (remove (second (string->list s1)) (string->list s1)) (add1 removed-so-far)))]
           [else (list->string (remove-repeats-acc (rest (string->list s1)) removed-so-far))])]))]
    (remove-repeats-acc s 0)))

但这似乎不正确。请帮我修改以使其正常工作。

谢谢！

- Bubbles

---

请将您的代码放在代码块中，并适当缩进以便于阅读。 - pfhayes

你可以通过在每行代码前添加至少四个空格以及在适当的位置开始新行来使代码看起来漂亮。 - Tikhon Jelvis

Answer 1

字符串有些烦人，因此我们将其包装在一个处理列表的工作函数中。这样，我们就可以避免到处转换造成的麻烦。

(define (remove-repeats str)
  (list->string (remove-repeats/list (string->list str))))

现在我们可以使用简单的递归来定义 remove-repeats/list 函数：

(define (remove-repeats/list xs)
  (cond
    [(empty? xs) xs]
    [(empty? (cdr xs)) xs]
    [(equal? (car xs) (cadr xs)) (remove-repeats/list (cdr xs))]
    [else (cons (car xs) (remove-repeats/list (cdr xs)))]))

这不是尾递归，但现在添加累加器应该更容易了：

(define (remove-repeats str)
  (list->string (remove-repeats/list-acc (string->list str) '())))

(define (remove-repeats/list-acc xs acc)
  (cond
    [(empty? xs) (reverse acc)]
    [(empty? (cdr xs)) (reverse (cons (car xs) acc))]
    [(equal? (car xs) (cadr xs)) (remove-repeats/list-acc (cdr xs) acc)]
    [else (remove-repeats/list-acc (cdr xs) (cons (car xs) acc))]))

- hzap

Answer 2

这是我喜欢的一个版本，在Typed Racket中：

#lang typed/racket
(: remove-repeats : String -> String)
(define (remove-repeats s)
  (define-values (chars last)
    (for/fold: ([chars : (Listof Char) null] [last : (Option Char) #f])
      ([c (in-string s)] #:when (not (eqv? last c)))
      (values (cons c chars) c)))
  (list->string (reverse chars)))

- Sam Tobin-Hochstadt