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




Внутреннее представление списков. Применяющие функционалы


ЛЕКЦИЯ 8.

ВНУТРЕННЕЕ ПРЕДСТАВЛЕНИЕ СПИСКОВ. ПРИМЕНЯЮЩИЕ ФУНКЦИОНАЛЫ


Содержание


8.1 Внутреннее представление списков


8.1.1 Структура памяти

Каждый атом занимает ячейку.

Списки, являются совокупностью атомов, и связываются вместе специальными элементами памяти, называемыми списочными ячейками или

cons-ячейки.

Каждая списочная ячейка состоит из двух частей, полей.

Первое поле - CAR, второе CDR

Поля типа списочная ячейка содержат указатели на другие ячейки, или nil.

Если обе ячейки содержат указатели на атомы, то можно записать проще

Этому случаю соответствует структура (a.b)

которая называется точечной парой.


8.1.2 Представление списков через списочную ячейку.

Список из одного атома, представляется, как

NIL указывает на конец списка.

Вместо nil пишут - \.

Список получается как операция (cons 'a nil)

Список из двух элементов (b a)

Правое поле указывает на cdr списка (хвост).

Левое поле, на саr

списка(голову).

Каждому элементу списка соответствует списочная ячейка.

Список (a b c d) будет представлен как :

Если список не одного уровня (a (b c) d), то каждому элементу списка соответствует списочная ячейка.

Причем саr поле второй списочной ячейки указывает на вложенный список.


8.1.3 Представление списков через точечные пары.

Любой список можно записать в точечной нотации.

(a) (a.nil)

(a b c) (a.(b.(c.nil)))

Выражение представленное в точечной нотации можно привести к списочной если cdr поле является списком.

(a.(b c)) <=> (a b c)

(a.(b.c)) <=> (a b.c)


8.1.4 Списочная ячейка и базовые функции.

Результатом действия функции car

будет значение левого поля первой списочной ячейки

* (сar '(a (b c) d)

a

Результатом действия функции cdr

будет значение правого поля первой списочной ячейки.

* (сdr '(a (b c) d)

((b c) d)

CONS создает новую списочную ячейку, car поле которой указывает на первый элемент, а cdr на второй

(cons 'x '(a b c))




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