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

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

Благодаря,

В 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). Единственной оставшейся проблемой для вас будет обновление связанного элемента.

  • Различия между INDEX, PRIMARY, UNIQUE, FULLTEXT в MySQL?
  • Какова наилучшая схема базы данных для поддержки значений, которые подходят только для определенных строк?
  • Почему foldl определенно задан в Racket?
  • Какой лучший способ узнать LISP?
  • «Приложение: не процедура» в двоичных арифметических процедурах
  • Как создать весь DDL схемы Oracle (сценарий)?
  • Сколько примитивов требуется для создания LISP-машины? Десять, семь или пять?
  • В чем разница между eq ?, eqv ?, equal ?, и = в схеме?
  • В чем разница между цитатой и списком?
  • Как сгенерировать диаграммы UML (особенно диаграммы последовательности) из кода Java?
  • Точечная запись в схеме
  • Interesting Posts

    Загрузить файл на ftp

    Windows 10: Не удается найти приложения через окно поиска

    Создать несколько ZIP-файлов, которые не зависят друг от друга?

    Как перейти от общедоступной сети к частной сети

    Как установить Flash-плагин для Firefox на Ubuntu в автономном режиме?

    Как создать многострочные таблицы в Microsoft Word 2007?

    Ошибка получения родительского элемента для элемента: ресурс не найден, который соответствует указанному имени ‘android: TextAppearance.Material.Widget.Button.Borderless.Colored’

    stdio.h не стандартно в C ++?

    Переключение между вкладками Google Chrome с помощью AppleScript

    Windows (7, 8, 10). Является ли чистая установка лучше, чем обновление, и если да, то почему? (быть конкретной)

    Каков предел для параметров QueryString / GET / URL

    Точность использования оперативной памяти Windows 8 Task Manager

    Как избежать исключения «Circular view path» с использованием теста Spring MVC

    Преобразование с плавающей запятой 32-бит в 16 бит

    UIImage Сохранение изображения с именем файла на iPhone

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