Накопительная рекурсия для замены строковых символов числами в схеме

Я предполагаю, что, поскольку это вопрос «университетского уровня», вы на самом деле изучаете ракетку для класса - тогда я предполагаю, что вы используете языковой пакет для продвинутых студентов.

Мое понимание накопительной рекурсии заключается в том, что программа использует некоторый тип памяти. Вот решение, над которым я работал. Это полное решение вопроса, полностью совместимое с Advanced Student Language Pack; код немного неуклюжий, но вы, конечно, можете его улучшить.

;; 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"

С уважением

Начните с модульного тестирования вспомогательных процедур, несколько советов:

• Если под накопительной рекурсией вы подразумеваете хвостовую рекурсию, будьте осторожны: build-string не является хвостовой рекурсией, и ее придется полностью переписать.
• count-duplicate не делает то, что вы ожидаете - передача (first lst) в качестве второго параметра в рекурсивных вызовах является ошибкой
• Вы не считаете последовательные символы, вы просто считаете количество символов
• Неправильно строится список вывода - зачем всегда склеивать символ с его частотой? делайте это только в том случае, если символы последовательно дублируются
• Ожидаемый результат — это строка, а не список символов. В какой-то момент вам придется использовать list->string
• Кроме того, в какой-то момент вам придется преобразовать количество найденных символов в символ, например: 3 станет #\3. Это необходимо для создания строки в конце

Ошибок так много, что я бы посоветовал начать с нуля, решая и проверяя подзадачи, прежде чем склеивать части. Но я помогу вам с процедурой count-duplicate, обратите внимание, что вас интересует только количество символов, которые последовательны для данного символа, это правильный способ сделать это:

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

Вы бы использовали это так:

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

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

Теперь вы должны убедиться, что для каждого текущего символа в исходной строке вы подсчитываете, сколько последовательных символов было найдено в остатке списка, и если число больше чем 1, правильно составить выходной список. Не забудьте продвинуть рекурсию на count символов после того, как вы нашли дубликат, иначе вы будете считать один и тот же символ несколько раз! (подсказка: используйте для этого drop).

Это работает, за исключением преобразования окончательного списка обратно в строку:

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

Вы можете видеть, что он является полностью хвостовой рекурсией и накапливает результат по мере обхода строки.

> (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 #\!)

Вот мой взгляд на эту проблему.

Первая процедура, называемая prefix, сообщит вам, сколько последовательных одинаковых букв у вас есть в начале строки. Я использую string->list для работы со списком, а не с подстрокой:

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

Он вернет 2 значения: количество вхождений и соответствующий символ:

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

Вторая функция rle будет просто перебирать строку, используя первую функцию:

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

Такие как

(rle "hellooo wooorldd")
"hel2o3 wo3rld2"