Постановка задачи
Часть 1. Знакомство с основами функционального программирования (Lisp)
Определить рекурсивную функцию для удаления последнего элемента списка.
Ч асть 2. Рекурсивные структуры данных (списки и деревья)
Имеется список, элементы которого — непустые бинарные деревья. Для каждого элемента списка найти среднее арифметическое листьевых вершин, из полученных результатов сформировать список. Выполнить реверс для полученного списка.
Часть 3. Ассоциативные списки и списки свойств символа.
Имеется ассоциативный список, вторым элементом точечных пар которого является символ. Организовать формирование списка свойств символа, определяемого по заданному ключу. Ввод имен свойств и их значений выполнить с клавиатуры. Организовать вывод ассоциативного списка и списка свойств его элементов в наглядном виде.
Исходные тексты
Часть 1. Знакомство с основами функционального программирования (Lisp)
Функция quote ‘(arg) или (quote arg) Назначение: блокирует вычисление выражения.
В Lisp для построения, разбора и анализа списков существуют очень простые базовые функции. Всего их пять – car, cdr, cons, atom и eq.
Функция car (car list) Назначение: выделяет первый элемент списка – голову списка.
Функция cdr (cdr list) Назначение: выделяет хвост списка (как список).
Функция cons (cons head tail) Назначение: строит новый список из переданных ей в качестве аргументов головы и хвоста.
Функция atom (atom arg) Назначение: проверяет, является ли аргумент атомом.
Функция eq (eq symbol1 symbol2) Назначение: проверяет тождественность двух символов.
Предложение cond (cond (predicate1 form1) (predicate2 form2) … (predicateN formN))
Назначение: выполнение ветвления.
Описание действия: выражения predicate, исполняющие роль предикатов, вычисляются последовательно слева направо до тех пор, пока не встретится выражение, значением которого является истина, далее вычисляется результирующее выражение form, соответствующее этому предикату, и полученное значение возвращается в качестве значения всего предложения cond. Если истинного предиката нет, то значением cond будет nil. Рекомендуется в качестве последнего предиката использовать символ t, и соответствующее ему результирующее выражение будет вычисляться всегда в тех случаях, когда ни одно другое условие не выполняется.
| (defun del (list) | Объявление функции |
| (cond | Оператор ветвления |
| ((null (cdr list)) nil) | Если хвост списка n пустое, то последний элемент списка находится в голове, и вместо этого элемента возвращаем пустой элемент |
| (t (cons (car list) (del (cdr list)))) | t-истина, если первое не выполнилось, то строим новый список cons, из головы car list и выделение конца, функцией del от cdr list, списка без головного элемента. |
| ) | |
| ) | |
| (print (del '(a b c d e))) | Запуск функции |
Рис. 1. Пример выполнения программы
Ч асть 2. Рекурсивные структуры данных (списки и деревья)
- Имеется список, элементы которого — непустые бинарные деревья. Для каждого элемента списка найти среднее арифметическое листьевых вершин, из полученных результатов сформировать список. Выполнить реверс для полученного списка.
| (defun SUM (A B) | Функция, суммирует попарно, количество листьев в правом и левом, и их суммы. |
| (list (+ (first A) (first B))(+ (second A) (second B)))) | |
| (defun COUNT_T (TREE) | Рекурсивная функция, определяет, является ли число листом, суммирует количество и сумму листов. |
| (cond ((null TREE) '(0 0)) | Если пустое, то значение 0 вершин и 0 сумма. |
| ((and TREE (null (second TREE)) (null (third TREE))) (cons (first TREE) (cons 1 nil))) | Проверка, является ли вершина листом (справа second и слева third нет вершин |
| (t (SUM (COUNT_T (second TREE)) (COUNT_T (third TREE)))))) | Если не лист, искать справа и слева листья |
| (defun AVERAGE (TREE) | Функция подсчета среднего, для одного элемента списка |
| ((lambda (A) (/ (first A) (second A))) (COUNT_T TREE))) | |
| (defun COMPLITE (NODE A) | Функции рекурсивно пробегают по списку, добавляя элементы, и переворачивая список |
| (cond ((null NODE) (cons A nil)) | |
| (t (cons (car NODE) (COMPLITE (cdr NODE) A))))) | |
| (defun REVERSE_T (NODE) | |
| (cond ((null NODE) nil) | |
| (t (COMPLITE (REVERSE_T (cdr NODE)) (car NODE))))) | |
| (defun CATALOG (f NODE) | Применение вычислений, для каждого дерева из списка |
| (cond ((null NODE) nil) | |
| (t (cons (eval (cons f (cons (cons 'quote (cons (car NODE) nil)) nil))) (CATALOG f (cdr NODE)))))) | |
| (print (REVERSE_T (CATALOG 'AVERAGE '( | Пример вызова |
| (1 (5 nil nil) (6 nil (7 nil nil))) | |
| (2 (8 nil nil) (9 (10 nil nil) nil)) | |
| (3 (11 (12 nil nil) (13 nil nil)) nil) | |
| (4 nil (14 nil nil)) | |
| (-1 nil (-2 nil nil)) | |
| (-10 nil nil) | |
| )))) |
Рис. 2. Пример входных данных
Рис. 3. Пример выполнения программы
Часть 3. Ассоциативные списки и списки свойств символа.
- Имеется ассоциативный список, вторым элементом точечных пар которого является символ. Организовать формирование списка свойств символа, определяемого по заданному ключу. Ввод имен свойств и их значений выполнить с клавиатуры. Организовать вывод ассоциативного списка и списка свойств его элементов в наглядном виде.
Ассоциативный список (associative list, a-list) — основанная на списках и точечных парах структура данных — список точечных пар.
((key1. data1) (key 2. data 2) … (key n. data n))
Первый элемент пары — ключ (как правило, символ), второй элемент — данные, которые могут быть любыми лисповскими объектами.
С помощью а-списков можно объединять разнотипные, поименованные ключами данные в единую структуру данных.
Основные действия с а-списками:
- создание списка;
> (defun pairlis (keys data)
(cond
((null keys) nil)
(t (cons (cons (car keys) (car data))(pairlis (cdr keys) (cdr data))))))
PAIRLIS
> (setq словарь (pairlis '(стол бумага карандаш) '(table paper pencil)))
((СТОЛ. TABLE) (БУМАГА. PAPER) (КАРАНДАШ. PENCIL))
> словарь
((СТОЛ. TABLE) (БУМАГА. PAPER) (КАРАНДАШ. PENCIL))
- поиск данных по ключу;
(defun assoc (key a-list)
(cond
((null a-list) nil)
((equal (caar a-list) key) (cdar a-list))
(t (assoc key (cdr a-list)))))
> (assoc 'бумага словарь)
PAPER
- обновление данных.
Списки свойств символа
С символом можно связать список именованных свойств (property list, p-list).
Функции для работы со списком свойств символа:
- присваивание нового значения;
(putprop символ значение свойство)
- получение значения;
(get символ свойство)
- удаление значения;
(remprop символ свойство)
- получение списка свойств.
(symbol-plist символ)
> (symbol-plist 'berry)
NIL
> (putprop 'berry 'cranberry 'name)
CRANBERRY
> (putprop 'berry 'red 'colour)
RED
> (putprop 'berry 'sour 'taste)
SOUR
> (symbol-plist 'berry)
(TASTE SOUR COLOUR RED NAME CRANBERRY)
> (remprop 'berry 'colour)
NIL
> (symbol-plist 'berry)
(TASTE SOUR NAME CRANBERRY)
3. Вывод:
В процессе выполнения контрольной работы, мною были изучены и закреплены базовые основы функционального программирования на языке Lisp. Были получены навыки работы со списками, рекурсивными структурами данных.