Регистрация | Войти
Lisp — программируемый язык программирования
Предыдущая Оглавление Следующая

12. Они назвали его Lisp неспроста: обработка списков

Списки в языке Lisp играют важную роль как по историческим, так и по практическим причинам. Изначально списки были основным составным типом данных в языке Lisp, и в течении десятилетий они были единственным составным типом данных. В наши дни, программист на Common Lisp может использовать как типы vector, hash table, самостоятельно определённые типы и структуры, так и списки.

Списки остаются в языке потому, что они являются прекрасным решением для определённого рода проблем. Одна из них - проблема представления кода, как данных для трансформации и генерации кода в макросах - является специфичной для языка Lisp, и это объясняет то, как другие языки обходятся без списков в стиле Lisp. Вообще говоря, списки - прекрасная структура данных для представления любых неоднородных и/или иерархических данных. Кроме того они достаточно легковесны и поддерживают функциональный стиль программирования - ещё одна важная часть наследия Lisp.

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

Списков нет

Мальчик с ложкой: Не пытайся согнуть список. Это невозможно. Вместо этого... попытайся понять истину.

Нео: Какую истину?

Мальчик с ложкой: Списков нет.

Нео: Списков нет?

Мальчик с ложкой: И тогда ты поймёшь: это не списки, которые сгибаются; это только ты сам. 1)

Ключом к пониманию списков, является осознание того, что они, по большей части, иллюзия, построенная на основе объектов более примитивных типов данных. Эти простые объекты - пары значений, называемые cons-ячейкой, от имени функции CONS, используемой для их создания.

CONS принимает 2 аргумента и возвращает новую cons-ячейку, содержащую 2 значения 2). Эти значения могут быть ссылками на объект любого типа. Если второе значение не NIL и не другая cons-ячейка, то ячейка печатается как два значения в скобках, разделённые точкой (так называемая точечная пара).

(cons 1 2) ==> (1 . 2)

Два значения в cons-ячейке называются CAR и CDR - по имени функций, используемых для доступа к ним. На заре времён эти имена были мнемониками, по крайней мере для людей, работающих над первой реализацией Lisp на IBM 704. Но даже тогда они были всего лишь позаимствованы из мнемоник ассемблера, используемых для реализации этих операций. Тем не менее, это не так уж плохо, что названия этих функций несколько бессмысленны, применительно к конкретной cons-ячейке лучше думать о них просто как о произвольной паре значений без какого-либо особого смысла. Итак:

(car (cons 1 2)) ==> 1
(cdr (cons 1 2)) ==> 2

Оба CAR и CDR могут меняться функцией SETF: если дана cons-ячейка, то возможно присвоить значение обеим её составляющим. 3)

(defparameter *cons* (cons 1 2))
*cons*                 ==> (1 . 2)
(setf (car *cons*) 10) ==> 10
*cons*                 ==> (10 . 2)
(setf (cdr *cons*) 20) ==> 20
*cons*                 ==> (10 . 20)

Т.к. значения в cons-ячейке могут быть ссылками на любой объект, вы можете строить большие структуры, связывая cons-ячейки между собой. Списки строятся связыванием cons-ячеек в цепочку. Элементы списка содержатся в CAR cons-ячеек, а связи со следующими cons-ячейками содержатся в их CDR. Последняя ячейка в цепочке имеет CDR со значением NIL, которое - как я говорил в главе 4. - представляет собой как пустой список, так и булево значение ложь.

Такая компоновка отнюдь не уникальна для Lisp, она называется однонаправленный список. Несколько языков, не входящих в семейство Lisp, предоставляют расширенную поддержку для этого скромного типа данных.

Таким образом, когда я говорю, что какое-то значение является списком, я имею в виду, что оно либо NIL, либо ссылка на cons-ячейку. CAR cons-ячейки является первым элементом списка, а CDR является ссылкой на другой список (который в свою очередь также является cons-ячейкой), содержащий остальные элементы, или значение NIL. Lisp-печаталка понимает это соглашение и печатает такие цепочки cons-ячеек как списки в скобках, нежели как точечные пары.

(cons 1 nil)                   ==> (1)
(cons 1 (cons 2 nil))          ==> (1 2)
(cons 1 (cons 2 (cons 3 nil))) ==> (1 2 3)

Когда мы говорим о структурах из cons-ячеек, нам могут помочь несколько диаграмм. Эти диаграммы изображают cons-ячейки как пары блоков:

Изображение

Блок слева представляет CAR, а блок справа - CDR. Значения, хранимые в ячейках также представлены в виде отдельных блоков или в виде стрелки выходящей из блока, для представления ссылки на значение. 4) Например, список (1 2 3), который состоит из трёх cons-ячеек, связанных вместе с помощью их CDR, может быть изображён так:

Изображение

Однако, в основном при работе со списками вы не обязаны иметь дело с отдельными ячейками, т.к. существуют функции, которые создают списки и используются для манипулирования ими. Например, функция LIST строит cons-ячейки и связывает их вместе, следующие LISP-выражения эквивалентны CONS-выражениям, приведённым выше:

(list 1)     ==> (1)
(list 1 2)   ==> (1 2)
(list 1 2 3) ==> (1 2 3)

Аналогично, когда вы думаете в терминах списков, вы не должны использовать бессмысленные имена CAR и CDR; вы должны использовать FIRST и REST - синонимы для CAR и CDR при рассмотрении cons-ячеек, как списков.

(defparameter *list* (list 1 2 3 4))
(first *list*)        ==> 1
(rest *list*)         ==> (2 3 4)
(first (rest *list*)) ==> 2

Как и cons-ячейки, списки могут содержать значения любых типов.

(list "foo" (list 1 2) 10) ==> ("foo" (1 2) 10)

Структура списка при этом выглядит так:

Изображение

Т.к. элементами списка могут быть другие списки, то с помощью списков можно представлять деревья произвольной глубины и сложности. Таким образом, они идеально подходят для представления гетерогенных иерархических данных. Например, XML-процессоры, основанные на Lisp, как правило представляют XML-документы в виде списков. Другим очевидным примером данных с древовидной структурой является сам код на языке Lisp. В главах 30 и 31 вы напишете библиотеку для генерации HTML-кода, которая использует списки списков для представления кода, который необходимо сгенерировать. В следующей главе я расскажу больше об использовании cons-ячеек для представления других типов данных.

Common Lisp предоставляет обширную библиотеку функций для работы со списками. В разделах Функции для работы со списками и Отображение вы узнаете о наиболее важных из них. Данные функции будет проще понять в контексте идей, взятых из парадигмы функционального программирования.

Функциональное программирование и списки

Суть функционального программирования в том, что программы состоят исключительно из функций без побочных эффектов, которые вычисляют свои значения исключительно на основе своих аргументов. Преимущество функционального стиля программирования в том, что он облегчает понимание программы. Устранение побочных эффектов ведёт к устранению практически всех возможностей удалённого воздействия. Т.к. результат функции определяется её аргументами, поведение функции легче понять и протестировать. Например, когда вы видите выражение (+ 3 4), вы знаете, что результат целиком задаётся определением функции + и переданными аргументами 3 и 4. Вам не надо беспокоиться о том, что могло произойти в программе до этого, т.к. нет ничего, что могло бы изменить результат вычисления выражения.

Функции, работающие с числами, естественным образом являются функциональными, т.к. числа неизменяемы. Списки же, как вы видели раннее, могут меняться, при применении функции SETF над ячейками списка. Тем не менее, списки могут рассматриваться как функциональные типы данных, если считать, что их значение определяется элементами, которые они содержат. Так, любой список вида (1 2 3 4) функционально эквивалентен любому другому списку, содержащему эти четыре значения, независимо от того, какие cons-ячейки используются для представления списка. И любая функция, которая принимает списки в качестве аргументов и возвращает значение, основываясь исключительно на содержании списка, могут считаться функциональными. Например, если функции REVERSE передать список (1 2 3 4), она всегда вернёт (4 3 2 1). Различные вызовы REVERSE с функционально-эквивалентными аргументами вернут функционально-эквивалентные результаты. Другой аспект функционального программирования, который я рассматриваю в разделе "Отображение", это использование функций высших порядков: функций, которые используют другие функции, как данные, принимая их в качестве аргументов или возвращая в качестве результата.

Большинство функций Common Lisp для работы со списками написаны в функциональном стиле. Позднее мы обсудим как совмещать функциональный подход к программированию с другими подходами, но сначала вы должны понять некоторые тонкости функционального подхода применительно к спискам.

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

(append (list 1 2) (list 3 4)) ==> (1 2 3 4)

С точки зрения функционального подхода, задача функции APPEND - вернуть список (1 2 3 4) не изменяя ни одну из cons-ячеек в списках-аргументах (1 2) и (3 4). Очевидно, что это можно сделать создав новый список, состоящий из четырёх новых cons-ячеек. Однако в этом есть лишняя работа. Вместо этого APPEND на самом деле создаёт только две новые cons-ячейки, чтобы хранить значения 1 и 2, соединяя их вместе и делая ссылку из CDR второй ячейки на первый элемент последнего аргумента - списка (3 4). После этого функция возвращает cons-ячейку содержащую 1. Ни одна из входных cons-ячеек не была изменена, и результатом, как и требовалось, является список (1 2 3 4). Единственная хитрость в том, что результат, возвращаемый функцией APPEND имеет общие cons-ячейки со списком (3 4). Структура результата выглядит так:

Изображение

В общем случае, функция APPEND должна копировать все, кроме последнего, аргументы-списки, и она может вернуть результат, который имеет общие структуры с последним аргументом.

Другие функции также используют полезную особенность списков иметь общие структуры. Некоторые, как и APPEND, всегда возвращают результаты, которые имеют общие структуры со своими аргументами. Другим функциям позволено возвращать результаты с общими структурами, но это зависит от их реализации.

"Разрушающие" операции

Если бы Common Lisp был строго функциональным языком, больше не о чем было бы говорить. Однако, т.к. после создания cons-ячейки есть возможность изменить её значение применив функцию SETF над её CAR и CDR, мы должны обсудить как стыкуются побочные эффекты и общие структуры.

Из-за функционального наследия языка Lisp, операции, которые изменяют существующие объекты называются разрушающими - в функциональном программировании изменение состояния объекта "разрушает" его, т.к. объект больше не представляет того же значения, что до применения функции. Однако использование одного и того же термина для обозначения всего класса операций, изменяющих состояние существующих объектов, ведёт к некоторой путанице, т.к. существует 2 сильно отличающихся класса таких операций: операции-для-побочных-эффектов и утилизирующие операции. 5)

Операции-для-побочных-эффектов это те, которые используются ради их эффектов. В этом смысле, всякое использование SETF является разрушающим, как и использование функций, которые вызывают SETF чтобы изменить состояние объектов, например VECTOR-PUSH или VECTOR-POP. Но это несколько некорректно объявлять операции разрушающими, т.к. они не предназначены для написания программ в функциональном стиле, т.е. они не могут быть описаны с использованием терминов функциональной парадигмы. Тем не менее, если вы смешиваете нефункциональные операции-для-побочных-эффектов с функциями возвращающими результаты с общими структурами, то надо быть внимательным, чтобы случайно не изменить эти общие структуры. Например, имеем:

(defparameter *list-1* (list 1 2))
(defparameter *list-2* (list 3 4))
(defparameter *list-3* (append *list-1* *list-2*))

После вычисления, у вас три списка, но list-3 и list-2 имеют общую структуру, как показано на предыдущей диаграмме.

*list-1*                  ==> (1 2)
*list-2*                  ==> (3 4)
*list-3*                  ==> (1 2 3 4)

Посмотрим, что случится если мы изменим list-2:

(setf (first *list-2*) 0) ==> 0
*list-2*                  ==> (0 4)     ; как и ожидалось
*list-3*                  ==> (1 2 0 4) ; а вот этого возможно вы и не хотели

Из-за наличия общих структур, изменения в списке list-2 привели к изменению списка list-3: первая cons-ячейка в list-2 является также третьей ячейкой в list-3. Изменение значения FIRST списка list-2 изменило значение CAR в cons-ячейке, изменив оба списка.

Совсем по-другому обстоит дело с утилизирующими операциями, которые предназначены для запуска в функциональном коде. Они используют побочные эффекты лишь для оптимизации. В частности, они повторно используют некоторые cons-ячейки своих аргументов для получения результатов. Но в отличие от таких функций, как APPEND, которые используют cons-ячейки, включая их без изменений в результирующий список, утилизирующие операции используют cons-ячейки как сырьё, изменяя их CAR и CDR для получения желаемого результата. Таким образом утилизирующие операции спокойно могут быть использованы, когда их аргументы не пригодятся после их выполнения.

Чтобы понять как работают функции утилизации сравним неразрушающую операцию REVERSE, которая возвращает инвертированный аргумент, с функцией NREVERSE, которая является утилизирующей функцией и делает то же самое. Т.к. REVERSE не меняет своих аргументов, она создаёт новую cons-ячейку для каждого элемента списка-аргумента. Но предположим, вы напишите:

(setf *list* (reverse *list*))

Присвоив результат вычисления переменной *list*, вы удалили ссылку на начальное значение *list*. Если на cons-ячейки в начальном списке больше никто не ссылается, то они теперь доступны для сборки мусора. Тем не менее в большинстве реализаций Lisp более эффективным является повторно использовать эти ячейки, чем создавать новые, а старые превращать в мусор.

NREVERSE именно это и делает. N - сокращение для "не создающая", в том смысле, что она не создаёт новых cons-ячеек. Конкретные побочные эффекты NREVERSE явно не описываются, она может проводить любые модификации над CAR и CDR любых cons-ячеек аргумента, но типичная реализация может быть такой: проход по списку с изменением CDR каждой cons-ячейки так, чтобы она указывала на предыдущую cons-ячейку, в конечном счёте результатом будет cons-ячейка, которая была последней в списке аргументе, а теперь является головой этого списка. Никакие новые cons-ячейки при этом не создаются и сборка мусора не производится.

Большинство утилизирующих функций, таких как NREVERSE, имеют своих неразрушающих двойников, которые вычисляют тот же результат. В общем случае утилизирующие функции имеют такое же имя, как их недеструктивные двойники с подставленной первой буквой N. Но есть и исключения, например часто используемые: NCONC - утилизирующая версия APPEND и DELETE, DELETE-IF, DELETE-IF-NOT, DELETE-DUPLICATED - версии семейства функций REMOVE.

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

Однако ещё большую неразбериху вносит небольшой набор утилизирующих функций со строго определёнными побочными эффектами, на которые можно положиться. В этот набор входят NCONC, утилизирующая версия APPEND, и NSUBSTITUTE и её -IF и -IF-NOT варианты - утилизирующие версии группы функций SUBSTITUTE.

Как и APPEND, NCONC возвращает соединение своих аргументов, но строит такой результат следующим образом: для каждого непустого аргумента-списка, NCONC устанавливает в CDR его последней cons-ячейки ссылку на первую cons-ячейку следующего непустого аргумента-списка. После этого она возвращает первый список, который теперь является головой результата-соединения. Таким образом:

(defparameter *x* (list 1 2 3))
(nconc *x* (list 4 5 6)) ==> (1 2 3 4 5 6)
*x*                      ==> (1 2 3 4 5 6)

На функцию NSUBSTITUTE и её варианты можно положиться в следующем её поведении: она пробегает по списковой структуре аргумента-списка и устанавливает с помощью функции SETF новое значения в CAR его cons-ячеек. После этого она возвращает переданный ей аргумент-список, который теперь имеет то же значение, как если бы был вычислен с помощью SUBSTITUTE. 6)

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

Комбинирование утилизации с общими структурами

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

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

На практике, утилизирующие функции используются в нескольких определённых случаях. Наиболее частый случай - построение списка, который будет возвращён из функции добавлением элементов в его конец (как правило с использованием функции PUSH), а потом инвертирование данного списка. При этом список хранится в локальной для данной функции переменной. 7)

Это является эффективным способом построения списка, потому что каждый вызов PUSH создаёт только одну cons-ячейку, а вызов NREVERSE быстро пробегает по списку, переназначая CDR ячеек. Т.к. список создаётся в локальной переменной внутри функции, то нет никакой возможности, что какой-то код за пределами функции имеет общие структуры с данным списком. Вот пример функции, которая использует такой приём для построения списка, который содержит числа от 0 до n 8):

(defun upto (max)
  (let ((result nil))
    (dotimes (i max)
      (push i result)
)

    (nreverse result)
)
)


(upto 10) ==> (0 1 2 3 4 5 6 7 8 9)

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

(setf foo (delete nil foo))

Эта конструкция присваивает переменной foo её старое значение с удалёнными элементами, равными NIL. Однако, здесь утилизирующие функции должны применяться осмотрительно: если foo имеет общие структуры с другими списками, то использование DELETE вместо REMOVE может разрушить структуры этих списков. Например, возьмём два списка list-2 и list-3, рассмотренные раннее, они разделяют свои последние 2 cons-ячейки.

*list-2* ==> (0 4)
*list-3* ==> (1 2 0 4)

Вы можете удалить 4 из list-3 так:

(setf *list-3* (delete 4 *list-3*)) ==> (1 2 0)

Но DELETE скорее всего произведёт удаление тем, что установит CDR третьей ячейки списка в NIL, отсоединив таким образом четвёртую ячейку от списка. Т.к. третья ячейка в list-3 является также первой ячейкой в list-2, этот код изменит также и list-2:

*list-2* ==> (0)

Если вы используете REMOVE вместо DELETE, то результат будет построен с помощью создания новых ячеек, не изменяя ячеек list-3. В этом случае list-2 не будет изменён.

Эти два случая использования вместе составляют около 80% от общего числа случаев использования утилизирующих функций. Другие случаи использования возможны, но требуют внимательного отслеживания того возвращают ли функции списки с общими структурами или нет.

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

Важный момент, на который следует обратить внимание: функции сортировки списков SORT, STABLE-SORT и MERGE из главы 11 также являются утилизирующими функциями когда они применяются к спискам10). Эти функции не имеют неразрушающих аналогов, так что если вам необходимо отсортировать списки не разрушая их, вы должны передать в сортирующую функцию копию списка, сделанную с помощью COPY-LIST. В любом случае, вы должны сохранить результат функции, т.к. исходный аргумент-список будет разрушен. Например:

CL-USER> (defparameter *list* (list 4 3 2 1))
*LIST*
CL-USER> (sort *list* #'<)
(1 2 3 4)                      ; кажется то, что надо
CL-USER> *list*
(4)                            ; упс!

Функции для работы со списками

Теперь вы готовы взглянуть на библиотеку функций для работы со списками, которую предоставляет Common Lisp.

Вы уже видели базовые функции для извлечения элементов списка: FIRST и REST. Хотя вы можете получить любой элемент списка комбинируя вызовы REST (для продвижения по списку) и FIRST (для выделения элемента), это может быть утомительным занятием. Поэтому Lisp предоставляет функции от SECOND до TENTH извлекающие соответствующие элементы списка. Более общая функция NTH принимает два аргумента: индекс и список, и возвращает n-ый (начиная с нуля) элемент списка. Также существует функция NTHCDR, принимающая индекс и список и возвращающая результат n-кратного применения REST к списку. Таким образом, (nthcdr 0 ...) просто возвращает исходный список, а (nthcdr 1 ...) эквивалентно вызову REST. Имейте в виду, что ни одна из этих функций не является более производительной по сравнению с эквивалентной комбинацией FIRST и REST, т.к. нет иного способа получить n-ый элемент списка без n-кратного вызова CDR11).

28 составных CAR/CDR функций составляют ещё одно семейство, которое вы можете время от времени использовать. Имя каждой функции получается подстановкой до 4 букв A или D между C и R, каждая A представляет вызов CAR, а каждая D - CDR. Таким образом:

(caar list)   === (car (car list))
(cadr list)   === (car (cdr list))
(cadadr list) === (car (cdr (car (cdr list))))

Обратите внимание, что многие из этих функций имеют смысл только применительно к спискам, содержащим другие списки. Например, CAAR возвращает CAR от CAR исходного списка, таким образом, этот список должен иметь своим первым элементом список. Другими словами, эти функции для работы скорее с деревьями нежели со списками:

(caar (list 1 2 3))                  ==> ошибка
(caar (list (list 1 2) 3))           ==> 1
(cadr (list (list 1 2) (list 3 4)))  ==> (3 4)
(caadr (list (list 1 2) (list 3 4))) ==> 3

В настоящее время, эти функции не используются так часто, как раньше. Даже упёртые Lisp-хакеры старой закалки стремятся избегать этих длинных комбинаций. Однако они присутствуют в старом Lisp-коде, поэтому необходимо представлять, как они работают12).

Функции FIRST-TENTH, CAR, CADR и т.д. могут также быть использованы как аргумент к SETF, если вы пишите в нефункциональном стиле.

Другие функции для работы со списками
ФункцияОписание
LAST Возвращает последнюю cons-ячейку в списке. Если вызывается с целочисленным аргументом n, возвращает n ячеек.
BUTLAST Возвращает копию списка без последней cons-ячейки. Если вызывается с целочисленным аргументом n, исключает последние n ячеек.
NBUTLAST Утилизирующая версия BUTLAST; может изменять переданный список-аргумент, не имеет строго заданных побочных эффектов.
LDIFF Возвращает копию списка до заданной cons-ячейки.
TAILP Возвращает TRUE если переданный объект является cons-ячейкой, которая является частью списка.
LIST* Строит список, содержащий все переданные аргументы кроме последнего, после этого присваивает CDR последней cons-ячейки списка последнему аргументу. Т.е. смесь LIST и APPEND.
MAKE-LISTСтроит список из n элементов. Начальные элементы списка NIL или значение заданное аргументом :initial-element.
REVAPPENDКомбинация REVERSE и APPEND; инвертирует первый аргумент как REVERSE и добавляет второй аргумент. Не имеет строго заданных побочных эффектов.
NRECONC Утилизирующая версия предыдущей функции; инвертирует первый аргумент как это делает NREVERSE и добавляет второй аргумент. Не имеет строгих побочных эффектов.
CONSP Предикат для тестирования является ли объект cons-ячейкой.
ATOM Предикат для тестирования является ли объект не cons-ячейкой.
LISTP Предикат для тестирования является ли объект cons-ячейкой или NIL
NULL Предикат для тестирования является ли объект NIL. Функционально эквивалентен функции NOT, но стилистически лучше использовать NULL при тестировании является ли список NIL, NOT для проверки булевого выражения FALSE

Отображение

Другой важный аспект функционального стиля программирования - это использование функций высших порядков, т.е. функций, которые принимают функции в качестве аргументов или возвращают функции. Вы видели несколько примеров функций высших порядков, таких как MAP, в предыдущей главе. Хотя MAP может использоваться как со списками, так и с векторами (т.е. с любым типом последовательностей), Common Lisp также предоставляет 6 функций отображения специально для списков. Разница между этими шестью функциями в том как они строят свой результат и в том применяют ли они переданные функции к элементам списка или к cons-ячейкам списка.

MAPCAR функция наиболее похожая на MAP. Т.к. она всегда возвращает список, она не требует уточнения типа результата, как MAP. Вместо этого, первый аргумент MAPCAR - функция, которую необходимо применить, а последующие аргументы - списки, чьи элементы будут поставлять аргументы для этой функции. Другими словами MAPCAR ведёт себя, как MAP: функция применяется к элементам аргументов-списков, беря от каждого списка по элементу. Результат каждого вызова функции собирается в новый список. Например:

(mapcar #'(lambda (x) (* 2 x)) (list 1 2 3)) ==> (2 4 6)
(mapcar #'+ (list 1 2 3) (list 10 20 30))    ==> (11 22 33)

MAPLIST работает как MAPCAR, только вместо того, чтобы передавать функции элементы списка, она передаёт cons-ячейки13). Таким образом, функция имеет доступ не только к значению каждого элемента списка (через функцию CAR, применённую к cons-ячейке), но и к хвосту списка (через CDR).

MAPCAN и MAPCON работают как MAPCAR и MAPLIST, разница состоит в том, как они строят свой результат. В то время как MAPCAR и MAPLIST строят новый список, содержащий результаты вызова функций, MAPCAN и MAPCON строят результат склеиванием результатов (которые должны быть списками), как это делает NCONC. Таким образом, каждый вызов функции может предоставлять любое количество элементов, для включения в результирующий список 14). MAPCAN, как MAPCAR, передаёт элементы списка отображающей функции, а MAPCON, как MAPLIST, передаёт cons-ячейки.

Наконец, функции MAPC и MAPL - управляющие структуры, замаскированные под функции, они просто возвращают свой первый аргумент-список, так что они используются только из-за побочных эффектов передаваемой функции. MAPC действует как MAPCAR и MAPCAN, а MAPL как MAPLIST и MAPCON.

Другие структуры

Хотя cons-ячейки и списки обычно трактуются как синонимы, это не всегда так - как я говорил раннее, вы можете использовать списки списков для представления деревьев. Так же как функции из этой главы позволяют вам интерпретировать структуры, построенные из cons-ячеек, как списки, другие функции позволяют использовать cons-ячейки для представления деревьев, множеств, и двух типов отображений ключ-значение. Мы рассмотрим большинство этих функций в следующей главе.

1)Перифраз из к/ф "Матрица" Оригинальная цитата
2)CONS сокращения для глагола construct - конструировать
3)Когда место переданное в SETF это CAR или CDR, вызов SETF разворачивается в вызов функции RPLACA или RPLACD; некоторые лисперы старой школы, те самые, что до сих пор используют SETQ, будут использовать RPLACA или RPLACD непосредственно, но современный стиль учит использовать SETF для CAR и CDR
4)Как правило, простые объекты, такие как числа, изображаются внутри соответствующего блока, а более сложные объекты - снаружи, со стрелкой выходящей из блока, означающей ссылку. Это хорошо согласуется с тем, как работают многие реализации Common Lisp: хотя все объекты концептуально хранятся как ссылки, некоторые простые неизменяемые объекты могут храниться в cons-ячейках непосредственно
5)Термин "операция для побочных эффектов" используется в стандарте языка, название второго класса - моё изобретение; большинство пособий по Lisp используют термин разрушающие операции для обоих классов, я же пытаюсь развеять неразбериху
6)Строковые функции NSTRING-CAPITALIZE, NSTRING-DOWNCASE, и NSTRING-UPCASE действуют также: они возвращают такой же результат, как их аналоги без N, но при этом изменяют свои аргументы
7)При анализе кода из Common Lisp Open Code Collection (CLOCC), выясняется, что среди множества библиотек, написанных разными авторами, сочетание PUSH и NREVERSE составляет около половины всех использований утилизирующих функций
8)Конечно же имеются и другие пути достигнуть такого результата. Например, макрос LOOP делает это очень просто и похоже генерирует код, который даже эффективнее связки PUSH/NREVERSE
9)Использования этого случая насчитывает около 30% от всех случаев использования утилизирующий функций в CLOCC
10)SORT и STABLE-SORT могут также применяться к векторам ради их побочных эффектов, но т.к. они возвращают отсортированный вектор, то вы должны использовать эти функции только ради возвращаемого ими значения из соображений единого подхода и логичности
11)NTH приблизительно эквивалентна функции ELT, но работает только на списках. В противоположность ELT, NTH принимает индекс как первый аргумент. Другая разница между ними состоит в том, что ELT сигнализирует об ошибке при попытке доступа к элементу в позиции, превышающей или равной длине списка, в то время как NTH вернёт NIL
12)В частности, они использовались для извлечения различных частей выражения, переданного в макрос до того, как был изобретён неструктурированный список параметров FIXME. Например, вы могли разложить выражение
(when (> x 10) (print x))
таким образом:
;; условие
(cadr '(when (> x 10) (print x))) ==> (> X 10)

;; тело как список
(cddr '(when (> x 10) (print x))) ==> ((PRINT X))
13)Т.е. MAPLIST более примитивная из двух функций: если у вас есть только MAPLIST вы можете построить на её основе MAPCAR, но построить MAPLIST на основе MAPCAR невозможно
14)В диалектах Lisp, которые не имеют фильтрующей функции, такой как REMOVE возможным способом фильтрации списка является применение MAPCAN:
(mapcan #'(lambda (x) (if (= x 10) nil (list x)))  list) === (remove 10 list)
Предыдущая Оглавление Следующая
@2009-2013 lisper.ru