Как найти количество повторяющихся символов в списке в схеме

Question

Я пытаюсь сделать функцию в Схеме, которая возвращает, сколько раз символ повторяется в списке. Например, если у меня есть (список 2 6 'a' b 'a' a 2) , результат должен быть ((2. 2) (6. 1) (a. 3) (b. 1))

его не нужно было писать самым эффективным способом, просто хотите быть простым и понятным для понимания.

Заранее спасибо за помощь мне :)

Answer 1

Поскольку это, кажется, домашние задания, не отвечал никакого кода вообще, и мы ничего не знаем о ваших ограничений и вашего текущего знания схемы, это трудно ответить.

В принципе, вы можете сделать это эффективно с помощью хэш-карты или менее эффективно с помощью двух вложенных циклов. Я объясню вам последнее, чтобы вы начали.

Предполагаю, что вы знаете, как пройти через список.

Поэтому в основном вам нужно

• 1) петли над списком
  • 2) для каждого элемента списка (назовем его е)
    • 3) цикл по списку раз более того, считая, сколько (е) вы найдете
    • 4) собрать (е) и результат вашего цикла подсчета

Результаты этапа 4) должны быть собраны в списке результатов.

Если вы сделаете это, то результат будет что-то вроде

'((2 . 2) (6 . 1) (a . 3) (b . 1) (a . 3) (a . 3) (2 . 2)) 

что близко ... но не правильно, потому что вы рассчитывали некоторые элементы в несколько раз.

Так что в дополнение к вышесказанному вам нужен способ отслеживания каждого элемента, с которым вы столкнулись, и шаги 3) и 4) необходимо выполнить, только если вы столкнулись с новым элементом. Отслеживание может осуществляться через другой список или просто путем проверки текущего списка результатов в зависимости от вашего кода.

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

EDIT

ОК, так как GoZoner разместил код, у меня есть 2 альтернативных вариантов для вас. Надеюсь, вы изучите все это и сделаете свой собственный разум, вместо того, чтобы просто копировать его.

Во-первых, описанная мной версия; в отличие от версии GoZoner, он не использует изменяемых списков, но медленнее, чем изменяемом версия:

(define (how-many lst) 
    (let loop ((lst2 lst) (res '())) 
    (if (empty? lst2) 
     (reverse res) 
     (let ((c (car lst2))) 
      (loop (cdr lst2) 
       (if (assoc c res) 
        res 
        (cons (cons c (count (lambda (e) (eq? e c)) lst)) res))))))) 

=> '((2 . 2) (6 . 1) (a . 3) (b . 1)) 

Если вы хотите использовать изменяемую структуру (и я бы тоже), я рекомендую изменяемые хэш-таблицу ,В следующем примере в Ракетка но тривиально адаптироваться к R6RS схеме hash tables при необходимости:

(define (how-many lst) 
    (let ((res (make-hash))) 
    (for-each (lambda (e) (hash-update! res e add1 0)) lst) 
    (hash->list res))) 

=> '((6 . 1) (a . 3) (b . 1) (2 . 2)) 

Просто обратите внимание, что хэш-таблица не соблюдает порядок, так что вы получите тот же результат, но пар будет вероятно, в другой порядок (и даже варьироваться от одного вызова к другому).

Answer 2

Что-то вроде этого:

(define (character-count list) 
    (assert (list? list)) 
    (let looking ((list list) (rslt '())) 
    (cond ((null? list) rslt) 
      ((assoc (car list) rslt) => 
      (lambda (pair) 
      (set-cdr! pair (+ 1 (cdr pair))) 
      (looking (cdr list) rslt))) 
      (else (looking (cdr list) 
         (cons (cons (car list) 1) rslt)))))) 
> (character-count '(2 a 2 a b c 2)) 
((c . 1) (b . 1) (a . 2) (2 . 3)) 

я получаю 'A' ?!