Введение в программирование на Лиспе



             

Структуры данных - часть 2


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

(C )


(B C )


(C (A B))


Пример 3.2.

Упражнения 3.1.: Нарисуйте диаграммы для списков вида:

((A B) C)

((A B) (D C))

((A B)(D(C E)))

Любой список может быть построен из пустого списка и атомов с помощью CONS и любая его часть может быть выделена с помощью подходящей композиции CAR-CDR.

CONS - Функция, которая строит списки из бинарных узлов, заполняя их парами объектов, являющихся значениями пары ее аргументов. Первый аргумент произвольного вида размещается в левой части бинарного узла, а второй, являющийся списком, - в правой.

CAR – Функция, обеспечивающая доступ к первому элементу списка - его "голове".

CDR – Функция, укорачивающая список на один элемент. Обеспечивает доступ к "хвосту" списка, т.е. к остатку списка после удаления его головы.

ATOM - Функция, различающая составные и атомарные объекты. На атомах ее значение "истина", а на более сложных структурах данных – "ложь".

EQ – Функция, которая проверяет атомарные объекты на равенство.

Таблица 3.1. Элементарные функции над списками. Примеры соответствия между аргументами и результатами элементарных функций обработки списков.

ФункцияАргументыРезультатКонструирование структур данныхДоступ к компонентам структуры данных:СлеваСправаОбработка данных:Предикаты:Атомарность – неделимостьРавенство
CONSA и Nil(A )
CONS(A B) и Nil((A B) )
CONS

CONS

A и (B)

(Результат предыдущего CONS) и ( C )

(A B)

((A B) C)

CONSA и (B C)(A B C)
CAR(A B C)A
CAR(A (B C))A
CAR((A B) C)(A B)
CARAНе определен
CDR(A )Nil
CDR(A B C D)(B C D)
CDR(A (B C))((B C))
CDR((A B) C)( C )
CDRAНе определен
CDR

CAR

(A B C)

Результат предыдущего CDR

(B C)

B

CAR

CAR

(A C)

Результат предыдущего CAR

A

Не определен

CONS

CAR

A и (B)

Результат предыдущего CONS

(A B)

A

CONS

CDR

A и (B)

Результат предыдущего CONS

(A B)

(B)

ATOMVeryLongStringOfLettersT
ATOM( A B )Nil - выполняет роль ложного значения
CDR

ATOM

( A B )

Результат предыдущего CDR

(B)

Nil

ATOMNilT
ATOM( )T
EQA AT
EQA BNil
EQA (A B)Nil
EQ(A B) (A B)Не определен
EQ(A B) (A B)Не определен
EQNil и ()T

Различие истинностных значений в Лиспе принято отождествлять с разницей между пустым списком и остальными объектами, которым программист может придать в программе некоторый другой смысл. Таким образом, значение "ложь" – это всегда Nil.

Если требуется явно изобразить значение "истина", то используется стандартная константа – атом T (true), но роль значения "истина" может выполнить любой, отличный от пустого списка, объект.

Упражнение 3.2. Посмотрите, что сделает Лисп-система с ниже приведенными выражениями2), сравнивая результаты с данными из таблицы 3.1:

(CONS 'Head Nil ) (CONS 'Head '(Body Tail) ) (CAR '(Head Body Tail)) (CDR '(Head Body Tail)) (ATOM 'Body) (ATOM '(Body)) (ATOM ()) (ATOM (CAR '(Head Body Tail))) (EQ Nil ())




Содержание  Назад  Вперед