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

ЛЕКЦИЯ 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)

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

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

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

((b c) d)

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

(cons 'x '(a b c))

или

LIST

* (list 'a '(b c)) (a (b c))

этот список представляется

Получается следующим образом:

1. Создается списочная ячейка для каждого аргумента функции

2. В car поле ставится указатель на соответствующий элемент

3. В cdr поле ставится указатель на следующую списочную ячейку

8.1.5 Переменные и списки.

Рассмотрим выражение

(setq y '(a b c))

Переменная Y будет иметь значение '(a b c)

Использование переменной , в функции обеспечивает доступ к структуре

(setq x (cons 'd y))

CONS не изменяя структуры, увеличивает список.

Если в функции присвоения список задается явно, то под него отводятся новые списочные ячейки.т.е.

(setq z '(a b c))

Переменная z будет иметь значение '(a b c)

8.1.6 EQ и EQUAL.

EQ проверяет физическое равенство списков, и EQUAL -логическое, т.е. для EQ необходимо, чтобы списки имели одинаковую стpуктуpу, а для EQUAL одинаковые элементы. (Структура списка определяется списочными ячейками).

*(setq lis1 '(a b))

* (setq lis2 '(a b))

Другая структура списка

* (setq lis3 lis1)

* (equal lis1 lis2)

t

* (equal lis1 lis3)

t

* (eql lis1 lis2)

nil

* (eql lis1 lis3)

t

* (eq lis1 lis2)

nil

* (eq lis1 lis3)

t

Однако для отдельного атома это не выполняется, т.е. новые ячейки не отводятся.

* (setq m 'abc)

* (setq n 'abc)

* (eq m n)

t

8.1.7 Cборка мусора

В результате вычислений в памяти могут возникнуть структуры, на которые нельзя ссылаться. Это происходит, когда вычисляемая структура не сохраняется с помощью setq, или когда теряются ссылки на старое значение.

Например

(setq l1 '((a) b c))

(setq l1 (cdr l1))

Для повторного использования ставшей мусором памяти в лисп системах предусмотрен специальный сборщик мусора, (garbage collector) GC, который автоматически запускается когда в памяти остается мало места.

Сборщик мусора перебирает все ячейки и собирает ставшие мусором ячейки в область свободной памяти для использования.

8.2 Обработка списков без разрушения.

(rplaca x y) (setf (car x) y)

(rplacd x y) (setf (cdr x) y)

Можно использовать для замены элементов.

Например, рассмотрим функцию, replace-item, которая имеет три элемента: первый элемент должен быть списком. Функция разрушающе замещает первое местоположение второго аргумента в списке на третий аргумент.

(defun replace-iteme (lis old new)

(rplaca (member old lis) new).

8.3.3 Использование разрушающих функций.

Разрушающие функции необходимо использовать при работе с большими списками, чтобы не увеличивать расход памяти, например использовать nconc вместо append.

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

Можно получить бесконечные списки:

* (setq v1 '(a b c))

(a b c)

* (setq v2 v1)

(a b c)

* (setq v2 (nconc v1 v2))

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

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

8.4 Применяющие функционалы.

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

Так как применяющие функционалы вычисляют значение функции, в этом смысле они аналогичны функции EVAL,

вычисляющей значение выражения.

8.4.1 APPLY.

Предположим мы хотим объединить в один список несколько вложенных списков, т.е. из

((a b c) (d e f) (k l)) получить (a b c d e f k l).

Для этой задачи используем функцию apply. APPLY имеет два аргумента: имя функции и список, и применяет названную функцию к элементам списка, как к аргументам функции.

Определим функцию, которая рассчитывает среднее списка чисел

(defun list-mean (lis)

(/ (apply '+ '(lis) (length lis)))

* (list-mean '(1 2 3 4))

2.5

Часто apply используют вместе c марсаr.

Мы хотим найти общее число элемент в списках

(countall '((a b c) (d e f) (k l)))

(defun countall (lis)

(apply '+ (mapcar 'length lis)))

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

Например

* (countatom '(a (a (b) c) (d) e (f g)))

8

(defun countatom (lis)

(cond ((null lis) 0)

((atom lis) 1)

(t (apply '+ (mapcar 'countatom lis)))))

8.4. 2 Cочетание apply, nconc, mapcar - mapcan.

Построить функцию list-last, образующую список из хвостов списков.

Например

* (list-last '((a b) (b c) (c d))) возвращает (b c d)

(defun list-last (lis)

(apply 'append (mapcar 'last lis)))

APPEND работает медленно и оставляет много мусора.

Можно это сделать через nconc:

(defun list-last (lis)

(apply 'nconc (mapcar 'last lis)))

В лиспе имеется отображающий функционал mapcan

(mapcan fn x1 x2 ... xN)

(apply 'nconc (mapcar fn x1 x2 ... xN))

T.е. mapcan объединяет результаты в один список, используя функцию nconc.

(defun list-last (lis)

(mapcan 'last lis))

8.4.3 Функционал FUNCALL.

Применяющий функционал FUNCALL

аналогичен APPLY, но аргументы он

принимает, не в списке, а по отдельности:

(funcall fn x1 x2 ... xN) (fn x1 x2 ... xN)

Здесь fn - функция с n aргументами.

Например,

* (funcall '+ 1 2) * (+ 1 2)

3

* (funcall (car '(+ - / *)) 1 2)

3

Пример.

Рассмотрим использование funcall для построения функции map2, которая действует аналогично mapcar, но берет в качестве аргументов два элемента из списка, а не один.

Например:

* (map2 'list '(A Christie V Nabokov K Vonnegut))

дает ((A Christie) (V Nabokov) (K Vonnegut))

Эта функция имеет вид:

(defun map2 (f2 lst)

(if (null lst)

nil

(cons (funcall f2 (car lst) (cadr lst))

(map2 f2 (cddr lst)))))

Содержание раздела