Основные функции обработки списков

К операциям выделения отдельных частей списков и создания из них новых структур сводятся многие алгоритмы обработки символьной ин­формации. Основными функциями, на основе которых выполняются ука­занные действия, являются встроенные функции CAR, CDR и CONS. Эти функции определяются на основе функций CAR, CDR, CONS. Список - частный случай точечной пары, то применимы функции, аргументы которых заданы точечными парами.

В Лиспе имеется ряд других полезных функций для обработки списков:

· LAST ─ выделяет последний элемент списка (результат - список);

· NTH ─ выделяет n-й элемент списка;

· SUBST ─выполняет замену элементов в списке;

· BUTLAST ─ выделяет список без последних элементов;

· MEMBER ─ проверяет принадлежность элемента списку;

· LENGTH ─вычисляет длину списка;

· REVERSE ─ выполняет обращение списка;

· ADJOIN ─добавляет элемент в множество, представленное списком;

· REMOVE─ удаляет элемент из списка.

Определение функции в ЛИСПЕ

Определение функций

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

В языке Лисп для этого применяется лямбда-выражение:

(lambda ({переменная}*){форма}*)

Здесь конструкция ({переменная}*) называется лямбда ─ списком и представляет собой список формальных параметров, которые соответст­вуют аргументам функции. Последовательность форм влямбда выражении определяет правило формирования значения функции и называется телом функции. Пусть требуется определить функцию, вычисляющую х⁵. Тогда лямбда-выражение будет иметь вид:

(lambda (х) (* х ххх х))

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

(lambda (x у) (cons x (cons у nil)))

Для того, чтобы применить функцию, определенную лямбда-выражением, к некоторым аргументам, необходимо в вызове функции записать вместо имени функции лямбда-выражение. К примеру:

1. ((lambda (x)(* x xxx x)) 4) ─> 1024

2. ((lambda (x y) (cons x (cons у nil))) 'a 'b) ─ > (A B)

В первом примере формальному параметру X лямбда ─ списка присваивается фактическое зна­чение 4, а затем вычисляется тело лямбда ─ выражения. Во втором примере формальным параметрам X и У назначаются значения фактических пара­метров, заданных атомами А и В, из которых строится список (А В). После произведенных вычислений связи между формальными параметрами и значе­ниями фактических параметров разрушаются.

Вычисление с помощью лямбда ─ вызовов требует каждый раз при очередном вызове необходимо снова описывать тело функции. Проблема решается, если слямбда ─ выражением связать не­которое имя (символ). Для связи имени и лямбда ─ выражения в Лиспе применяется форма DEFUN:

(defun имя лямбда ─ выражение)

При этом для упрощения записи влямбда ─ выражении опускается слово LAMBDA и скобки. В итоге получаем:

(defun имя лямбда ─ список {форма}*)

Результатом вызова формы DEFUN является имя определенной функции. Например:

(defunstepen 5 (х) (* х ххх х)) ─ >STEPEN 5

(defunspisok (ху) (cons x (cons у nil))) ─ > SPISOK

Теперь указанные выше лямбда ─ вызовы можно заменить следующи­ми вызовами:

(stepen 5 4) ─ > 1024

(spisok 'а b) ─ > (АВ)

Отметим, что имя функции представляется символом. Поэтому мож­но говорить о том, что DEFUN устанавливает связь между символом и оп­ределением функции. Создавать функции можно в любом текстовом редакторе и хранить в файле с расширением.lsp. Определения функций могут храниться в файлах и загружаться используя функцию LOAD:

(load<имя файла>)

Эта функция загружает файл выражений и выполняет эти выражения.

<Имя файла> - это строковая константа, которая представляет собой имя

файла без расширения (подразумевается расширение ".lsp"). Если

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

После запуска интерпретатора необходимо функцией load загрузить файл с библиотекой, к примеру, созданных пользователем функций на диске С: в каталоге PROG.

>(load “C:\\prog\\bibl.lsp”)

Рекурсии в ЛИСПЕ

Лисп специально создавался для рекурсивных вычислений, и вся си­ла языка как раз и заключена в возможности широкого использования ре­курсивных функций. К примеру вычисления фак­ториала:

(defunfactorial (n)

(cond ((zeropn) 1)

(t (* (factorial (- n i)) n))))

Процесс рекурсивных вызовов можно исследовать, используя воз­можности трассировки. Включение и выключение меха­низма трассировки выполняется с помощью входящих в состав интерпре­татора директив TRACE и UNTRACE:

Рис. 1. Схема рекурсивных вызовов при вычислении факториала числа 4.

Лисп позво­ляет также эффективно определять рекурсивные функции для обработки символьных данных. Определим упрощенную версию функции MEMBER. Чтобы отличать ее от функции, встроенной в систему назовём ее MY-MEMBER. Функция проверяет, входит ли элемент X в список Y и воз­вращает подсписок Y, который начинается с обнаруженного элемента:

(defun my-member (x у)

(cond ((null у) nil)

((equal x (first у)) у)

(t (my-member x (rest у)))))

В функции выполняется сравнение элемента X с первым элементом списка Y. Если обнаруживается совпадение, то функция возвращает спи­сок У. Если совпадение не обнаружено, то продолжается поиск элемента X в хвосте списка У. Для этого рекурсивно вызывается функция MY-MEMBER. Первое условие формы COND на каждом шаге рекурсии контролирует спи­сок У. Если этот список исчерпан, то определяемая функция MY-MEMBER возвратит значение NIL. Функция MY-MEMBER использует простую рекур­сию.

Примером функции, выполняющей символьную обработку и осно­ванной на параллельной рекурсии, может служить рекурсивная версия функции MY-INTERSECTION:

(defun my-intersection (a b) (cond

((null a) nil);1)

((member (first a) b);2)

(cons (first a)(my-intersection (rest a) b)))
(t (my-intersection (rest a) b))));3)

Данная функция вычисляет список общих элементов двух списков А и В. В определении функции реализованы три правила:

1. если список А исчерпан, то список общих элементов пустой;

2. если первый элемент списка А входит в список В, то этот элемент

добавляется к списку общих элементов списков (REST А) и В; такой

список формируется рекурсивным вызовом функции MY- INTERSECTION, применяемой к хвосту списка А и исходному списку В;

3. если первый элемент списка А не входит в список В, то строится список общих элементов из хвоста списка А и списка В с помощью рекурсивного вызова функции MY-INTERSECTION.