Урок 4. Списки в LISP

LISP   15 декабря 2012  Автор статьи:  

Списки в языке программирования LISP состоят из CONS ячеек, где каждая ячейка состоит из двух частей:

  • CAR — первая часть ячейки, определяет значение в текущей ячейке
  • CDR — ссылка на следующую cons ячейку

Таким образом, если у вас есть список (a b c), то CAR вернет первый элемент в списке, т.е a. А функция CDR вернет на том же списке (b c). Если мы применим функции CAR и CDR на списке ((a b) c), то CAR — (a b), а CDR — c. Пустой список обозначается как NIL. NIL имеет двойственную природу, он единственный элемент в LISP является и списком и атомом. Таким образом становится понятно, что последний элемент списка является NIL. Так LISP понимает, что ваш список закончен. Кроме этого, вы можете явно указать последний элемент, таким образом CDR часть последнего элемента будет указывать на другой элемент, который может и не быть CONS ячейкой.
Пример:

(car '(a b c));a
(car '((a b) c));(a b)
(cdr '(a b c);(b c)
(cdr '((a b) c));c

Как вы могли заметить из примера, для того, чтобы задать список, который не содержит первым элементом функцию необходимо применять одинарную кавычку. Функция CONS формирует список из двух аргументов: первый аргумент данная функция использует как CAR — часть новой CONS ячейки, а вторую как CDR. Пример использования функции CONS:

(cons 1 '(2 3));(1 2 3)
(cons '(2 3) 1);((2 3) . 1)

Таким образом мы видим, что последовательность аргументов в CONS очень важна и ошибка в ней может привести к не очень интересным результатам. Что же означает точка после списка (2 3)? Она означает что вывели на экран CONS ячейку, у которой CDR ссылается на объект отличный от другой CONS ячейки, и он выводится на экран через точку. Теперь мне хотелось бы вам рассказать про дополнительные функции работы со списками. Очень интересное формирование имен происходит в языке LISP. Вместо того, чтобы вызвать функция CAR, а затем CDR, можно вызвать функцию CADR. Данный способ именования функций встретится вам в языке LISP еще не один раз. Очень полезной функцией для работы со списками является:

(nth i list);возвращает i-ый элемент в списке
(nth 0 '(1 2 3));1
(nth 1 '(1 2 3));2
(nth 2 '(1 2 3));3

Отсчет как и в большинстве языках программирования начинается с 0. На этом мы закончим наше знакомство со списками и перейдем к следующему уроку.

Научиться программировать

  • на Delphi

  • на Java

  • на C++