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

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

Благодаря,

4 Solutions collect form web for “Считать количество элементов в списке на схеме?”

В Racket вы могли бы сделать

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

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

Вот подсказка для начала, основанная на 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 ...])) 

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

Во втором случае вы знаете, что это непустой список, поэтому у вас есть две части информации: ее голова (которую вы используете с помощью 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)) там.

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

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

В этом подходе используется список ассоциаций (alist) для хранения элементов и их счетчиков. Для каждого элемента входящего списка он просматривает элемент в 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)) 

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

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

и хотел добавить 1 к ценности baz , вы создаете новый alist, который исключает 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))) 

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

В этом подходе используются hash-таблицы, специфичные для 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, чем какой-либо конкретный отказ от схемы для выполнения чисто функциональных задач. Благодаря правильной библиотеке эта задача может быть реализована легко и функционально.

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

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

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

  • Рекурсивный диапазон в Lisp добавляет период?
  • Функциональное программирование: что такое «неправильный список»?
  • «Приложение: не процедура» в двоичных арифметических процедурах
  • Различия между INDEX, PRIMARY, UNIQUE, FULLTEXT в MySQL?
  • Неожиданное сохранение данных
  • Смущает разница между let и let * в Scheme
  • Разница между схемой / базой данных в MySQL
  • Какой пакет lang подходит для SICP в Dr.Racket?
  • Как отменить конкретную миграцию?
  • Точечная запись в схеме
  • Какова наилучшая схема базы данных для поддержки значений, которые подходят только для определенных строк?
  • Interesting Posts

    Как сделать раздел в частичном представлении в MVC3?

    Почему производители процессоров перестали увеличивать тактовую частоту своих процессоров?

    Как редактировать атрибуты / данные различных столбцов в представлении сведений о проводнике Windows

    Инициализировать компонент инициализации компонента из реквизита

    Как resize шрифта в текстовых редакторах Eclipse для Java?

    Есть ли причина для вызова delete в C ++, когда программа все равно выходит?

    Должен ли я использовать константы над определениями?

    Django MEDIA_URL и MEDIA_ROOT

    Почему мне нужно использовать class Rfc2898DeriveBytes (в .NET) вместо прямого использования пароля в качестве ключа или IV?

    Пакетное преобразование XLS в XLSX

    Пакетное преобразование .doc в .docx (и эквивалентное для других офисных форматов)?

    Отключить главную кнопку в Android ICS (4.0)

    Как использовать Objective-C #define из Swift

    Удаление объявлений из Foxit Reader

    Показывать данные о наведении указателя на круг

    Давайте будем гением компьютера.