Accumulative Recursion to Replace String Characters With Numbers in Scheme

Question

The question is the following:

1. Use accumulative recursion
2. Function consumes a string and produces a new string
3. Each character that appears consecutively is replaced by the letter and the number of times of its consecutive appearances
4. Example: "hellooo" => "hel2o3"
5. Question is University Level Based

I've tried the following:

(define (abbreviate str)
  (local [(define str-lst (string->list str))
          (define (count-duplicate lst char count)
            (cond
              [(empty? lst) count]
              [(equal? (first lst) char)
               (count-duplicate (rest lst)
                                (first lst)
                                (add1 count))]
              [else (count-duplicate (rest lst)
                                     (first lst)
                                     count)]))
          (define (build-string lst)
            (cond
              [(empty? lst) empty]
              [else (cons (first lst)
                          (cons (string->list (number->string 
                                         (count-duplicate (rest lst)
                                                          (first lst) 1)))
                          (build-string (rest lst))))]))]


    (build-string str-lst)))

But I get the result:

(list #\h (list #\4) #\e (list #\4) #\l (list #\4) #\l (list #\3) #\o (list #\3) #\o (list #\2) #\o (list #\1))

Any help?

Answer 1

I assume, since this is a "university level" question, you're actually learning racket for a class - I assume then that you are using the Advanced Student Language Pack.

My understanding of accumulative recursion is that the program uses some type of memory. Here is a solution I worked on. It's a complete solution to the question and is completely compatible with the Advanced Student Language Pack; code's a bit clunky but you're welcome to refine it of course.

;; abbreviate : string -> string
;; consumes a string and produces a new string, with all occurences of
;; sequences of repeating characters reduced to 1 character and the 
;; number of times the character repeats
;; Example
;; (abbreviate "oooo) should be "o4"
;; (abbreviate "thiis iss a teesstt") should be "thi2s is2 a te2s2t2"
;; (abbreviate "magic") should be "magic"
;; Definitions:
(define (abbreviate a-string)
  (local ((define memory empty)
          (define (count-dupes b)
            (cond ((empty? b) 0)
                  ((duplicate? b) (+ 1 (count-dupes (rest b))))
                  (else 0)))
          (define (skip-dupes c n)
            (cond ((= n 0) c)
                  ((empty? c) c)
                  (else (skip-dupes (rest c) (sub1 n)))))
          (define (duplicate? a)
            (equal? (first a) (first memory)))
          (define (load lst)
            (begin (set! memory (cons (first lst) memory)) (abbreviate-x (rest lst))))
          (define (abbreviate-x lst)
            (cond ((empty? lst) lst)
                  ((empty? memory) (cons (first lst) (load lst)))
                  ((duplicate? lst) (cons (+ 1 (count-dupes lst)) 
                                          (abbreviate-x 
                                            (skip-dupes lst (count-dupes lst)))))
                  (else (cons (first lst) (load lst)))))
          (define (string-adapt d)
            (cond ((empty? d) empty)
                  ((number? (first d)) (append (string->list (number->string (first d)))
                                               (string-adapt (rest d))))
                  (else (cons (first d) (string-adapt (rest d)))))))
    (list->string (string-adapt (abbreviate-x (string->list a-string))))))
;; Test
(check-expect (abbreviate "hellooo wooorldd") "hel2o3 wo3rld2"

Kind Regards

Answer 2

Start by unit-testing the helper procedures, some hints:

• If by accumulative recursion you mean tail recursion, then beware: build-string is not tail recursive, and will have to be entirely rewritten
• count-duplicate is not doing what you expect - it's an error to pass (first lst) as the second parameter in the recursive calls
• You're not counting consecutive characters, you're just counting the number of characters
• The output list is not being correctly constructed - why always stick a character with its frequency together? only do this if the characters are consecutively duplicated
• The expected output is a string, not a list of characters. At some point you'll have to make use of list->string
• Also, at some point you'll have to convert the number of characters found into a character, for example: 3 will become #\3. This is required for creating a string at the end

There are so many mistakes that my advice would be to start over from scratch, solving and testing the subproblems before gluing together the parts. But I'll lend you a hand with the count-duplicate procedure, notice that you're interested only in the number of chars that are consecutive for a given char, this is the correct way to do it:

(define (count-duplicate lst char count)
  (cond [(or (empty? lst) (not (char=? char (first lst))))
         count]
        [else
         (count-duplicate (rest lst) char (add1 count))]))

You'd use it like this:

(count-duplicate (rest '(#\h #\e #\l #\l #\o)) #\h 1)
=> 1

(count-duplicate (rest '(#\h #\h #\h #\l #\o)) #\h 1)
=> 3

Now you have to make sure that for each current character in the original string, you count how many consecutives were found in the rest of the list, and if the number is greater than 1, construct the output list in the right way. Don't forget to advance the recursion count characters after you've found a duplicate, otherwise you'll count the same character several times! (hint: use drop for this).

Answer 3

This works, excluding converting the final list back to a string:

(define (abbreviate str)
  (let scanning ((list (string->list str))
                 (last #f)
                 (numb 1)
                 (rslt '()))
    (if (null? list)
        (reverse (if (= 1 numb) rslt (cons numb rslt)))  ; after reverse, make a string
        (let ((next (car list))
              (rest (cdr list)))
          (if (equal? last next)
              (scanning rest next (+ numb 1) rslt)
              (scanning rest next 1
                        (cons next (if (= 1 numb) rslt (cons numb rslt)))))))))

You can see that it is fully tail recursive and that it accumulates the result as the string is traversed.

> (abbreviate "22")
(#\2 2)
> (abbreviate "")
()
> (abbreviate "hellllloo")
(#\h #\e #\l 5 #\o 2)
> (abbreviate "mississippi")
(#\m #\i #\s 2 #\i #\s 2 #\i #\p 2 #\i)
> (abbreviate "Noooooooooooooooooo way!")
(#\N #\o 18 #\space #\w #\a #\y #\!)

Answer 4

Here's my take at this problem.

The first procedure called prefix will tell you how many consecutive identical letters you have at the beginning of a string. I'm using string->list to work with a list rather than with substring:

(define (prefix str)
  (let ((chars (string->list str)))
    (let loop ((chars chars) (c #\0) (l 0))
      (if (empty? chars)
          (values l c)
          (if (= l 0)
              (loop (cdr chars) (car chars) (add1 l))
              (if (char=? (car chars) c)
                  (loop (cdr chars) c (add1 l))
                  (values l c)))))))

It will return 2 values: the number of occurences, and the char in question:

(prefix "")
0
#\0
(prefix "x")
1
#\x
(prefix "hello")          
1
#\h
(prefix "hhhello")     
3
#\h

The second function rle will just loop over the string using the first function:

(define (rle str)
  (let loop ((str str) (res '()))
    (if (= (string-length str) 0)
        (string-join (reverse res) "")
        (let-values (((l c) (prefix str)))
          (loop (substring str l) 
                (cons 
                 (if (= l 1) 
                     (~a c)
                     (~a c l))
                 res))))))

such as

(rle "hellooo wooorldd")
"hel2o3 wo3rld2"