Как реализовать счетчик для каждого числа в списке со схемой?

Question

Хорошо, я хочу подсчитать, сколько раз каждый [номер] появлялся в списке, используя Схему.

Как я могу это сделать? Я также хотел бы сохранить счетчик заданного числа и восстановить новый список.

Например, у меня есть следующий список ((1 2)(2 5)(5 7)(7 8)(6 8)(4 6)(3 4)(1 3)(4 8))

Я думал сначала сгладить список, а затем установить счетчик для каждого числа (не знаю, как это сделать). А затем восстановить новый список, соответствующий исходному номеру. (это может быть сложно? Мне нужно хранить временную переменную?)

Скажем, из этого примера число 1 появилось дважды, число 2 появилось дважды, число 3 дважды и т. Д., Поэтому я хотел бы воссоздать новый список примерно так:

(1 2) (2 2) (3 2) (4 3) (5 2) (7 2) (6 2) (8 3)

Есть идеи, как мне этого добиться?

Обновление:

Я думал реализовать вспомогательный счетчик приращений как-то так?

 (define inc-counter 
    (let ((counter 0)) 
      (lambda () (set! counter (+ counter 1))))) 

Answer 1

A хороший ответ в основном зависит от вашей реализации (по модулю R6RS). В случае схемы PLT, вот краткое определение, которое делает это. Это позволяет избежать сглаживания списка - вам нужно только сканировать каждый элемент, поэтому нет смысла создавать новую копию, когда сканирование дерева так просто. Кроме того, эта функция сортирует результирующий список (так как он будет весь зашифрован при выходе из хеш-таблицы). Даже если вы используете совершенно другую реализацию, ее легко перевести:

(define (counts x)
  (define t (make-hash))
  (define (scan x)
    (if (list? x)
      (for-each scan x)
      (hash-set! t x (add1 (hash-ref t x 0)))))
  (scan x)
  (sort (hash-map t list) < #:key car))

(Обратите внимание, что если это какой-либо вопрос HW, то этот код слишком практичен, чтобы быть полезным в качестве ответа ...)

Answer 2

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

Например, вы можете написать факториал так:

(define (factorial num accum) <br> (if (= num 0) accum (factorial (- num 1) (* accum num)))

И назовите это с помощью (факториал 10 1). В конце значение аккумулятора является результатом функции. В вашем примере вы бы написали небольшую вспомогательную функцию, которая вызывала бы flatten и отслеживала, сколько раз каждый номер появлялся.

Answer 3

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

Answer 4

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