Каждый раз, когда вы хотите просмотреть список и впоследствии вернуть какое-либо значение, будь то новый список или какой-либо совокупный результат, вы думаете о fold , также называемом «Reduce» в Python и Lisps.Fold - отличная абстракция, поскольку она позволяет писать общий код, применимый для многих вариантов использования, просто настраивая некоторые элементы.Что сходно между поиском суммы из нескольких чисел, поиском товара, поиском минимального целого числа?Все они складываются, потому что вы просматриваете список, а затем возвращаете некоторый результат на основе его содержимого.В Emacs Lisp они выглядят так:
(reduce '+ '(1 2 3 4 5)) ; 15
(reduce '* '(1 2 3 4 5)) ; 120
(reduce 'min '(1 2 3 4 5)) ; 1
Но сгибы даже более общие, чем это.Что сходно между поиском суммы, подсчетом числа четных чисел в списке, удалением каждого нечетного числа и построением списка с каждым числом, увеличенным на 5?Каждая такая функция может быть реализована путем принятия некоторого базового значения, последовательно преобразовывая его, пока вы не получите результат.Вы берете это базовое значение, метафорический шарик глины, называете его «аккумулятор», затем берете один элемент из списка и, основываясь на этом элементе, делаете что-то с этим шариком глины, делая его черновиком великолепной скульптуры.Затем вы берете следующий элемент из списка и делаете что-то новое для вашей скульптуры.Вы повторяете это до тех пор, пока список не станет пустым, и вы не получите шедевр.Как будто каждый элемент списка представляет собой отдельную инструкцию в большом рецепте.Просто имейте в виду, что вы абсолютно свободны делать что-либо с глиной, вам не нужно напрямую использовать элементы списка в результате - технически это означает, что аккумулятор (и, следовательно, результат) может иметьотличается тип .
(reduce '+ '(1 2 3 4 5) :initial-value 0) ; 15
(reduce (lambda (acc x) (if (evenp x) (1+ acc) acc)) '(1 2 3 4 5) :initial-value 0) ; 2
(reduce (lambda (x acc) (if (oddp x) acc (cons x acc))) '(1 2 3 4 5) :initial-value '() :from-end t) ; (2 4)
(reduce (lambda (x acc) (cons (+ x 5) acc)) '(1 2 3 4 5) :initial-value '() :from-end t) ; (6 7 8 9 10)
Примечание о сокращении с конца: списки в Лиспе не являются интеллектуальными массивами, как в Python или Java, они являются связанными списками, поэтому обращаются к или изменяютЭлемент где-то в списке является операцией O (n), в то время как «обращение» к началу списка - это O (1).Другими словами, добавление элемента в конец списка является дорогостоящим, поэтому Лисперс обычно добавляет элементы в начало списка, а затем, наконец, переворачивает список, который называется push / nreverse idiom .Если бы мы делали обычное уменьшение в последних 2 функциях, мы бы взяли 1 к аккумулятору и получили (1), затем 2 к аккумулятору и получили (2 1), пока мы не получим правильный результат, но в обратном порядке.Впоследствии мы могли бы использовать функцию reverse, но, к счастью, reduce Emacs поддерживает :from-end аргумент ключевого слова, поэтому он равен 5, затем 4, затем 3 и т. Д.
Теперь все ясно,что ваша операция складывается, проследите исходный список и посчитайте вхождения каждой клавиши.Прежде чем писать наш фолд, давайте сначала поговорим об алистах.Alist в Lisp - хэш-таблица для бедняков.Вы обычно не возитесь с деталями реализации хэш-таблицы языка программирования, не так ли?Вы работаете с API.В Python этот API выглядит как синтаксис в квадратных скобках (d['a'] = 1) и методы dict (d.keys()).API для списков списков содержит функцию assoc, которая возвращает элемент при условии ключа.
(assoc 'a '((a . 1) (b . 2))) ; (a . 1)
Почему я говорю о деталях реализации?Поскольку вы работаете через assoc и вам все равно, как точно выглядит этот список, вы абстрагируете его.Другая часть API заключается в том, что если вы хотите добавить новый элемент или изменить существующий, вы просто добавляете пунктирную пару в список.Это то, как вы должны работать со списками, независимо от их внутренней структуры.Почему это работает?Например, если я хочу изменить значение для ключа a на 10, я бы просто запустил (cons '(a . 10) my-alist), и my-alist в итоге получило бы '((a . 10) (a . 1) (b . 2)).Но это не проблема, потому что assoc возвращает только первую пару с точками и игнорирует остальные, поэтому вы можете обрабатывать alist точно так же, как и любую другую структуру данных ключ-значение.Имея это в виду, давайте напишем наш первый серьезный фолд.
(reduce (lambda (acc x)
(let* ((key (car x))
(pair (assoc key acc))
(count (cdr pair)))
(if pair
(cons (cons key (1+ count)) acc)
(cons (cons key 1) acc))))
my-alist
:initial-value '())
Что здесь происходит?Мы берем ваши данные и пустой список, который вскоре станет нашим желаемым результатом.На каждом шаге мы берем пару из данных и спрашиваем: содержит ли наш результат информацию об этой паре?Если нет, то мы добавляем его к результату и ставим 1 - мы встретили этот ключ впервые.Однако, если мы найдем информацию об этой паре в нашем результате, то мы должны снова добавить ее к нашему результату, но на этот раз с числом, увеличенным на 1. Повторите эту процедуру для каждого элемента в ваших данных, и вы получите:
(("Alpha" . 4) ("Gamma" . 3) ("Gamma" . 2) ("Rho" . 1) ("Alpha" . 3)
("Beta" . 5) ("Beta" . 4) ("Beta" . 3) ("Alpha" . 2) ("Beta" . 2)
("Gamma" . 1) ("Beta" . 1) ("Alpha" . 1))
Помните, что assoc заботится только о первом появлении ключа?Этот список будет вести себя так же, как если бы он был просто (("Alpha" . 4) ("Gamma" . 3) ("Rho" . 1) ("Beta" . 5)), так что мы здесь хорошо.Тем не менее, можем ли мы изменить наш фолд, чтобы получить последний, более короткий результат?Подожди, что за необходимость слишком усложнять наш фолд, если бы мы могли потом просто подправить результат?В конце концов, что такое компьютерное программирование, если не серия преобразований данных?Нет причины, по которой вы не могли бы просто удалить все «устаревшие» пары из своего списка, просто используйте cl-remove-duplicates с правильными аргументами , и все готово.
Итак, мыГордясь собой, мы написали фолд, столп функционального программирования, но тщательное изучение выявляет неэффективность: мы пересекаем аккумулятор с assoc, чтобы найти пару и ее значение для приращения.assoc принимает O (n), reduce само принимает O (n), поэтому наш алгоритм O (n²) (читайте о порядок роста , если вы не понимаете нотацию Big-O).Понятно, что вместо этого нам лучше работать с надлежащей оптимизированной хэш-таблицей и преобразовывать ее в alist, когда это необходимо.Перепишите наш сгиб:
(reduce (lambda (acc x)
(cl-incf (gethash (car x) acc 0))
acc)
my-alist
:initial-value (make-hash-table :test 'equal))
(gethash k d 0) эквивалентно Python d.get('k', 0), где последний аргумент является значением по умолчанию.cl-incf (эквивалент Common Lisp incf) - это интеллектуальный макрос, который увеличивает свой аргумент на месте (читайте о setf, чтобы понять умные назначения).make-hash-table требует пользовательской тестовой функции, потому что строки нельзя сравнивать со стандартной eql функцией.Чтобы получить список, просто преобразуйте хеш-таблицу результатов нашего фолда с помощью функции ht->alist, которую мы либо берем из библиотеки ht.el Уилфреда, либо пишем сами:
(defun ht->alist (table)
(let (alist)
(maphash (lambda (k v)
(push (cons k v) alist))
table)
alist))