7. car, cdr, cons: основные функции

В Лиспе самыми основными функциями являются car, cdr и cons. Функция cons используется чтобы создать список, а функции car и cdr, используются для того, чтобы список разделить.

Изучая функцию copy-region-as-kill, мы увидели cons, также как и два варианта cdr, точнее setcdr и nthcdr. (See section 8.5 copy-region-as-kill.)

Необычные имена
7.1 car и cdr		Функции для извлечения частей списка.
7.2 cons		Создание списка.
7.3 nthcdr		Повторный вызов cdr.
7.4 setcar		Изменяем первый элемент списка.
7.5 setcdr		Изменяем остаток списка.
7.6 Упражнения

Необычные имена

Имя функции cons довольно разумно --- оно произошло от сокращения слова `construct' (конструировать). С другой стороны происхождение названий функций car и cdr довольно интересно --- car это сокращение от фразы `Contents of the Address part of the Register' (Содержание Адресной части Регистра); а cdr (произносится как 'куд-ер) --- это сокращение от фразы `Contents of the Decrement part of the Register' (Содержание Декрементной части Регистра). Эти фразы относятся к специфическим частям аппаратного обеспечения на очень древних компьютерах, на которых был впервые реализован Лисп. Кроме того, что они давно устарели, эти фразы совсем не уместны вот уже более 30 лет для всех изучающих Лисп. Тем не менее, хотя некоторые храбрые ученые начали использовать более подходящие имена для этих функций, но все равно старые термины еще используются. В особенности, поскольку эти термины используются в исходных текстах Emacs Лиспа, то мы тоже будем использовать их в этом введении.

7.1 car и cdr

car от списка --- это первый элемент в списке. То есть car от списка (роза фиалка маргаритка лютик) равен роза.

Если вы читаете это в Emacs, то вы можете проверить это сами вычислив следующее:

(car '(роза фиалка маргаритка лютик))

После вычисление выражения в эхо-области появится роза. (Не сама конечно;))

Ясно, что более подходящим именем для функции car было бы first, и многие это часто предлагают.

car не удаляет первый элемент из списка --- он только возвращает нам его. После того, как к списку применили функцию car, этот список все еще точно такой же как и был. На жаргоне, функция car `non-destructive'(не разрушающая). Эта характеристика оказывается очень важной.

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

Вы можете проверить это вычислив следующую форму как обычно:

(cdr '(роза фиалка маргаритка лютик))

Когда вы сделаете это, то в эхо-области появится список (фиалка маргаритка лютик).

Как и car, функция cdr не удаляет никаких элементов из списка --- она только сообщает какой второй и последующие элементы.

Кстати в этом примере список цветов цитирован. Если бы это было не так, то интерпретатор Лиспа попробовал бы вычислить список вызвав розу как функцию. А в этом примере мы совсем бы этого не хотели.

Конечно более подходящим именем для cdr было бы название rest (остальные).

(Вот вам и урок --- когда вы выбираете названия для новой функции, то очень внимательно относитесь к этому, поскольку вы можете запутаться в именах, которые длинее, чем вы ожидаете. Причиной того, что в данном документе сохраняются такие имена, является то, что их используют исходные коды Emacs Lisp , и если бы я не использовал их, то вам было бы тяжело читать исходный код; но не пытайтесь избежать использования этих выражений. Люди придут после вас будут вам очень благодарны).

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

(car '(сосна ель дуб клен)) (cdr '(сосна ель дуб клен))

С другой стороны, в списке составленном из списков, первый элемент --- это список. car возвратит этот первый элемент списка. Например, следующий список содержит три вложенных списка --- список плотоядных, список травоядных, и список морских млекопитающихся:

(car '((лев тигр гепард) (газель антилопа зебра) (кит дельфин морж)))

В этом случае первым элементом, или car списка является список плотоядных (лев тигр гепард), а cdr списка является список ((газель антилопа зебра) (кит дельфин морж)).

(cdr '((лев тигр гепард) (газель антилопа зебра) (кит дельфин морж)))

Еще раз стоит повторить, что car и cdr не деструктивные --- то есть они не изменяют список к которому их применяют. Это очень важно для их применения.

Также в первой главе, обсуждая атомы, я сказал, что в Лиспе "определенного рода атомы, такие как массивы, можно разделить на составные части; но механизм этого отличен от того, как разделяются списки. Когда дело касается Лиспа, то атомы списка неразделимы." (See section 1.1.1 Атомы Лиспа.) Функции car и cdr используются для разделения списков и считаются основными в Лиспе. Так с их помощью нельзя разделить или добраться до части массива, массив считается атомом. Обратной им функцией является другая основная функция --- cons, которая может создать список, но не массив. (Доступ к массивам осуществляется с помощью специфических для массивов функций. See section `Arrays' in The GNU Emacs Lisp Reference Manual.)

7.2 cons

Функция cons создает, или конструирует списки; действуя обратно car и cdr. Например, cons может создать четырех-элементный список из трех-элементного списка (ель дуб клен):

(cons 'сосна '(ель дуб клен))

Вычислив это выражение, вы увидите в эхо-области

(сосна ель дуб клен)

cons помещает новый элемент в начало списка; то есть добавляет, или заталкивает элементы в список.

cons должна иметь список к которому будет прикреплять значения.(5) Вы не может начать с нуля. Если вы строите список, то вы должны сначала обеспечить хотя бы пустой список. Ниже приведен ряд применения функции cons, с помощью которых создается список из цветов. Если вы читаете это в Info в Emacs, то вы может вычислить каждое из выражений как обычно --- возвращенное значение печатается в тексте после `=>', что означает `вычислилось к'.

(cons 'лютик ()) => (лютик) (cons 'маргаритка '(лютик)) => (маргаритка лютик) (cons 'фиалка '(маргаритка лютик)) => (фиалка маргаритка лютик) (cons 'роза '(фиалка маргаритка лютик)) => (роза фиалка маргаритка лютик)

В первом примере, пустой список показан как (), при этом создается список из одного элемента лютик. Как вы можете видеть, в созданом списке нет пустого списка. Результатом является список (лютик). Пустой список не считается элементом списка, потому что в пустом списке ничего нет. В общем говоря, пустой список невидим.

Второй пример, (cons 'маргаритка '(лютик)) создает новый двух-элементный список, помещая маргаритку перед лютиком; а третий пример создает трех-элементный список, помещая фиалку перед маргариткой и лютиком.

7.2.1 Найти длину списка: length

Как найти длину списка.

7.2.1 Найти длину списка: length

Вы можете выяснить сколько в элементов списке с помощью функции length, как это показано в следующих примерах:

(length '(лютик)) => 1 (length '(маргаритка лютик)) => 2 (length (cons 'фиалка '(маргаритка лютик))) => 3

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

Можно с помощью функции length сосчитать число элементов в пустом списке:

(length ()) => 0

Как мы и ожидали, число элементов в пустом списке равно нулю.

Давайте проведем интересный эксперимент --- выясним, что произойдет, если вы попробуете найти длину там, где совсем нет списков; то есть попробуйте вызвать length без всяких аргументов, даже не передав пустого списка:

(length )

Как вы увидите, если вы вычислите это, то в эхо-области появится сообщение об ошибке:

Wrong number of arguments: #<subr length>, 0

Это значит, что в функция получила неправильное число параметров --- ноль, когда она ожидала несколько аргументов. В нашем случае, ожидался один аргумент --- список, чью длину функция и будет измерять. (Заметим, что один --- это один аргумент, даже если внутри списка много элементов).

Та часть сообщения об ошибке, которая гласит `#<subr length>' --- это имя функции. Она записана с помощью специальной записи: `#<subr', что означает, что эта функция написана на C, а не на Emacs Lisp. (`subr' это сокращение от `subroutine' (подпрограмма)). See section `What Is a Function?' in The GNU Emacs Lisp Reference Manual, для получения дополнительной информации о подпрограммах.

7.3 nthcdr

Функция nthcdr связана с функцией cdr. Она выполняет функцию cdr над списком несколько раз.

Если вы возьмете cdr от списка (сосна ель дуб клен), то вам вернут (ель дуб клен). Если вы повторите cdr, уже над этим укороченным списком, то вы получите (дуб клен). (Конечно, повторив cdr на первоначальном списке, вы снова получите (ель дуб клен), поскольку cdr не изменяет свой аргумент. Вам необходимо вычислить cdr от cdr и т.д.). Если вы будете продолжать выполнять это, то постепенно вам вернут пустой список, который на этот раз будет обозначен как nil, а не как ().

Повторим эти действия --- ниже приведена серия повторяющихся вызовов функции cdr, текст после `=>' показывает что возвращалось в результате.

(cdr '(сосна ель дуб клен)) =>(ель дуб клен) (cdr '(ель дуб клен)) => (дуб клен) (cdr '(дуб клен)) =>(клен) (cdr '(клен)) => nil (cdr 'nil) => nil (cdr ()) => nil

Вы можете взять несколько cdr, не печатая промежуточные значения, например:

(cdr (cdr '(сосна ель дуб клен))) => (дуб клен)

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

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

(nthcdr 2 '(сосна ель дуб клен)) => (дуб клен)

Используя первоначальный четырехэлементный список, мы рассмотрим, что произойдет, когда в функцию nthcdr будут передаваться разные числовые аргументы, включая 0, 1, и 5:

;; Оставим все как было. (nthcdr 0 '(сосна ель дуб клен)) => (сосна ель дуб клен) ;; Вернем копию без первого элемента. (nthcdr 1 '(сосна ель дуб клен)) => (ель дуб клен) ;; Вернем копию списка без трех элементов. (nthcdr 3 '(сосна ель дуб клен)) => (клен) ;; Вернем копию без всех четырех элементов. (nthcdr 4 '(сосна ель дуб клен)) => nil ;; Тоже самое. (nthcdr 5 '(сосна ель дуб клен)) => nil

Следует упомянуть, что nthcdr, как и cdr, не изменяет первоначальный список --- функция не является деструктивной. Этим она сильно отличается от функций setcar и setcdr.

7.4 setcar

Как вы могли уже догадаться из названий, функции setcar и setcdr устанавливают поля car и cdr списка в новые значения. Они на самом деле изменяют первоначальный список, в отличии от car и cdr, которые оставляют первоначальный список не измененным. Выясним, что же они делают, с помощью эксперимента.Начнем с функции setcar.

Вначале создадим переменную, которой в качестве значения присвоим некоторый список. Например, список животных:

(setq животные '(жираф антилопа тигр лев))

Если вы читаете это в Emacs, то вы может вычислить это выражение как обычно, расположив курсор за ним и нажав сочетание клавиш C-x C-e. (Я именно так и делаю, когда пишу все это. Это одно из преимуществ интерпретатора, встроенного в среду редактирования).

Когда мы вычислим переменную животные, то мы увидим, что она связана со списком (жираф антилопа тигр лев):

животные => (жираф антилопа тигр лев)

Или по другому, переменная животные указывает на список (жираф антилопа тигр лев).

Теперь, мы вычислим функцию setcar передав ей два аргумента --- переменную животные и цитированный символ бегемот, то есть мы напишем следующий трехэлементный список (setcar животные 'бегемот) и затем вычислим его как обычно:

(setcar животные 'бегемот)

После вычисления этого выражения, мы снова вычислим переменную животные. Вы увидите, что список животных изменился:

животные => (бегемот антилопа тигр лев)

Первый элемент прошлого списка --- жираф, заменен на бегемот.

То есть мы увидели, что setcar не добавляет новый элемент к списку, как это делает cons; а заменил жирафа на бегемота --- фактически изменил список.

7.5 setcdr

Функция setcdr похожа на функцию setcar. Только эта функция заменяет второй и последующие элементы списка, а не первый элемент.

Чтобы увидеть, как она работает, введем переменную домашние-животные и присвоим ей следующее значение:

(setq домашние-животные '(лошадь корова коза овца))

Если вы сейчас вычислите этот список, то в эхо-области отобразится (лошадь корова коза овца);

домашние-животные => (лошадь корова коза овца)

После этого давайте вычислим setcdr с двумя аргументами: первый --- это имя изменяемой переменной, а второй --- список который станет новым значением поля cdr для этой переменной:

(setcdr домашние-животные '(собака кошка))

Если вы вычислите это выражение, то в эхо-области появится список (собака кошка). Это значение, которое вернула функция. Результат, который нас интересует --- это "побочный эффект", который мы можем увидеть, вычислив переменную домашние-животные:

домашние-животные => (лошадь собака кошка)

И в самом деле --- список изменился с (лошадь корова коза овца) на (лошадь собака кошка). То есть, изменился cdr списка с (корова коза овца) на (собака кошка).

7.6 Упражнения

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