Removing repeated characters from a string in scheme
I've been trying this question for a long time but am not getting very far with it. The question is asking to produce a string where all the repeated characters from the inputed string are replaced by a single instance of the character.
For example,
(remove-repeats "aaaab") => "ab"
(remove-repeats "caaabb aa") => "cab a"
Since I 'm trying to do this using accumulative recursion, so far I have:
(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开发者_JAVA技巧 (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)))
But this doesn't seem to be right. Please help me modify this to work.
Thank You!!
Strings are a bit annoying to work with, so we wrap it around a worker function that deals with lists instead. This way we can avoid messing around with conversions everywhere.
(define (remove-repeats str)
(list->string (remove-repeats/list (string->list str))))
Now we can define the remove-repeats/list function using a straightforward recursion:
(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)))]))
This isn't tail-recursive, but now it should be easier to add accumulator:
(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))]))
Here's a version I'm fond of, in 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)))
精彩评论