Подсчитать вхождение элемента в список на схеме?

Question

Это очень легко, если я могу использовать массив на императивном языке или карту (древовидную структуру) в C ++, например.На схеме я понятия не имею, как начать эту идею?Кто-нибудь может мне помочь в этом?

Спасибо,

Answer 1

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

Портативный, чисто функциональный, но многословный и медленный

Этот подход использует список ассоциаций (alist) для хранения элементов и их количества. Для каждого элемента во входящем списке он ищет элемент в списке и увеличивает значение, если оно существует, или инициализирует его значением 1, если этого не происходит.

(define (bagify lst)
  (define (exclude alist key)
    (fold (lambda (ass result)
            (if (equal? (car ass) key)
                result
                (cons ass result)))
          '() alist))
  (fold (lambda (key bag)
          (cond ((assoc key bag)
                 => (lambda (old)
                      (let ((new (cons key (+ (cdr old) 1))))
                        (cons new (exclude bag key)))))
                (else (let ((new (cons key 1)))
                        (cons new bag)))))
        '() lst))

Увеличение является интересной частью. Чтобы быть чисто функциональными, мы не можем на самом деле изменить какой-либо элемент списка, но вместо этого мы должны исключить изменение ассоциации, а затем добавить эту ассоциацию (с новым значением) к результату. Например, если у вас был следующий список:

((foo . 1) (bar . 2) (baz . 2))

и хотите добавить 1 к значению baz, вы создаете новый список, исключающий baz:

((foo . 1) (bar . 2))

затем добавьте новое значение baz обратно:

((baz . 3) (foo . 1) (bar . 2))

Второй шаг - это то, что делает функция exclude, и, вероятно, самая сложная часть функции.

Портативный, емкий, быстрый, но не функционирующий

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

(define (bagify lst)
  (let ((ht (make-hash-table)))
    (define (process key)
      (hash-table-update/default! ht key (lambda (x) (+ x 1)) 0))
    (for-each process lst)
    (hash-table->alist ht)))

Чисто-функциональный, емкий, быстрый, но непереносимый

Этот подход использует специфичные для Racket хеш-таблицы (которые отличаются от таблиц SRFI 69), которые поддерживают чисто функциональный рабочий процесс. Как еще одно преимущество, эта версия также является самой краткой из трех.

(define (bagify lst)
  (foldl (lambda (key ht)
           (hash-update ht key add1 0))
         #hash() lst))

Вы даже можете использовать for понимание для этого:

(define (bagify lst)
  (for/fold ((ht #hash()))
            ((key (in-list lst)))
    (hash-update ht key add1 0)))

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

Answer 2

В Racket вы можете сделать

(count even? '(1 2 3 4))

Но, если серьезно, сделать это со списками в Scheme намного проще, чем то, что вы упоминаете.Список либо пуст, либо пара содержит первый элемент и остальные.Следуйте этому определению в коде, и вы получите «написать себя».

Вот подсказка для начала, основанная на HtDP (это хорошая книга, чтобы перейти кузнать об этих вещах).Начните только с функции «header» - она ​​должна получить предикат и список:

(define (count what list)
  ...)

Добавьте типы для входных данных - what - это некоторое значение, а list - это список

;; count : Any List -> Int
(define (count what list)
  ...)

Теперь, учитывая тип list и определение списка как пустого списка или пары из двух вещей, нам нужно проверить, какой это список:

;; count : Any List -> Int
(define (count what list)
  (cond [(null? list) ...]
        [else ...]))

Первый случай должен быть очевиден: сколько what элементов находится в пустом списке?

Во втором случае вы знаете, что это непустой список, поэтомуу вас есть две части информации: его голова (которую вы получаете с помощью first или car) и хвост (который вы получаете с rest или cdr):

;; count : Any List -> Int
(define (count what list)
  (cond [(null? list) ...]
        [else ... (first list) ...
              ... (rest list) ...]))

Все выТеперь нужно выяснить, как объединить эти две части информации для получения кода.Последний бит информации, который делает его очень простым: так как хвост (непустого) списка сам по себе является списком, то вы можете использовать count для подсчета содержимого в нем.Следовательно, вы можете также сделать вывод, что вам следует использовать (count what (rest list)) там.

Answer 3

В функциональных языках программирования, таких как Scheme, вы должны думать немного иначе и использовать способ составления списков.Вместо того, чтобы перебирать список, увеличивая индекс, вы рекурсивно просматриваете список.Вы можете удалить заголовок списка с помощью car (один элемент), вы можете получить хвост с помощью cdr (сам список) и вы можете склеить голову и хвост с помощью cons.Схема вашей функции будет выглядеть следующим образом:

• Вы должны "сдать" элемент, который вы ищете, и текущий счетчик для каждого вызова функции
• Если вы нажмете пустой список, вы закончили со списком и можете вывести результат
• Если автомобиль списка равен элементу, который вы ищете, рекурсивно вызвать функцию с помощью cdrlist и счетчик + 1
• Если нет, рекурсивно вызвать функцию с помощью cdr списка и того же значения счетчика, что и раньше

Answer 4

В Схеме вы обычно используете списки ассоциаций в качестве хеш-таблицы / словаря бедного человека.Единственная оставшаяся проблема для вас - как обновить связанный элемент.