Материалы представленные на сайте исключительно с целью ознакомления пользователям Интернета и не преследуют коммерческих целей или нарушение авторских прав.
© 2018 - 2024
return a = State RetA
where RetA s = (a, s)
(State r1) >>= p = State pState
where pState s = (res2, fState)
where (res1, interState) = r1 s
(State r2) = p res1
(res2, fState) = r2 interState
Таким образом, получается вычисление с состоянием, состоящее из двух связанных по состоянию частей – «r1» и «r2», однако вторая часть – «r2» – не известна заранее, а зависит от результата «r1».
Прочие
В стандартной библиотеке языка HASKELL определены еще несколько монад – IO, Reader, Writer, Cont.
IO - монада вычислений с побочными эффектами, Reader и Writer концептуально просты и довольно часто применяются; Cont – сложная монада, предназначенная для программирования в «стиле передачи продолжений» (continuation-passing style).
МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ВЫПОЛНЕНИЮ ЛАБОРАТОРНОЙ РАБОТЫ ПО ЛОГИЧЕСКОМУ ПРОГРАММИРОВАНИЮ
Лабораторная работа состоит из трех индивидуальных заданий на программирование на языках LISP и HASKELL и нескольких общих упражнений, которые приведены ниже и которые преподаватель уточняет на лекциях.
ЗАДАНИЕ N1. Работа со списками (на LISP’е и HASKELL’е)
5.1.1. Методические указания
В теоретическом плане:
· интерпретировать функциональную программу средствами теории примитивно-рекурсивных функций, для этого:
§ дать рекурсивное определение исходных и выходных данных программы, используя правила право-, леволинейных, КС грамматик , т.е формулы вида A->b;A->bB;A->Bb;A->BC..);
§ дать определение требуемой функции через простейшие функции, с применением операторов суперпозиции, подстановки, примитивной рекурсии;
Например, требуется определить функцию f, вычисляющую число элементов заданного списка.
Определим множество исходных данных L:
L->_; (пустой список)
L->Le; (e-элемент списка)
Множество выходных данных - целые числа:
Определим функцию f:
f(_)=0
f(eL)=f(L)+1;
Данному определению соответствует программа на LISP’е:
(defun f(l)(cond((null l)0)(T(+(f(cdr l))1))))
и на HASKELL’е:
f []=0
f x:xs= 1+f:xs
o сравнить программы на языках LISP и HASKELL по критериям:
§ пользовательские возможности;
§ возможности модификации;
§ объем текста программ;
§ трудозатраты;
§ соответствие стиля программирования и языка поставленной задаче
§ и другие.
В практическом плане:
· определить заданную функцию обработки списков через простые встроенные функции (типа car, cdr, cons,...) средствами языка LISP;
· определить заданную функцию обработки списков через простые операции работы со списками средствами языка HASKELL;
· отладить и протестировать полученные функциональные программы (количество тестов должно быть достаточным для вывода о работоспособности программы).
Не использовать функции ввода-вывода и возможности «фон-неймановского» стиля программирования.
5.1.2. Варианты
1.Даны списки целых чисел L1, L2. Построить список L3, состоящий из элементов списка L1, к которому добавлены все элементы списка L2, не входящие в L1.
2.Даны списки целых чисел L1, L2. Построить список L3 по следующему правилу: если L1 является подсписком L2, то из L2 исключить L1; в противном случае присоединить L1 к L2.
3.Множества заданы списками целых чисел L1 и L2. Получить в виде списка L3 множество, представляющее собой объединение множеств L1 и L2.
4.Множества заданы списками целых чисел L1 и L2. Получить в виде списка L3 множество, представляющее собой пересечение множеств L1 и L2.
5.Множества заданы списками строк L1 и L2. Получить в виде списка L3 множество L1\L2.
6.Дан список L1, элементом которого являются списки целых чисел. Построить список L2, изменив порядок элементов в L1 на обратный и изменить порядок на обратный в каждом подсписке.
7.Дан список литер L1. Построить список L2, исключив из L1 все повторяющиеся литеры.
8.Даны списки литер L1 и L2. Построить список L3 по следующему правилу: если L1 является префиксом L2, то исключить этот префикс и добавить его в качестве суффикса; в противном случае - присоединить к L1 список L2.
9.Дан список литер L. Исключить из списка все строчные литеры.
10. Множества целых чисел заданы списками L1, L2, L3. Построить список L4, представляющий собой пересечение множеств L1, L2, L3.
11. Дан список L. Если длина списка нечетна, то напечатать центральный элемент. В противном случае распечатать первую половину списка.
12. Дан список L. Если длина списка нечетна, построить список L1, поменяв местами левую и правую часть списка, в противном случае оставить список без изменения.
13. Даны два списка символов L1, L2. Если L1 есть подсписок L2, то определить следующий после L1 элемент списка L2, иначе ответом является слово no.
14. Даны списки L1,L2,L3. Если L1 является префиксом L2, а L3 - суффиксом L2, то ответ yes, иначе - no.
15. Даны списки L1, L2, L3. Если конкатенация L1 и L2 - есть префикс L3, то ответ - yes, иначе - no.
16. Даны списки L1, L2, L3. Если L1 и L2 являются подсписками L3, то сформировать новый список, удалив из L3 подсписки L1 и L2, в противном случае оставить L3 без изменения.
17. Список чисел разделить на 3 списка: числа, меньшие данного числа; равные данному; большие данного.
18. Даны два упорядоченных списка. Образовать из элементов этих списков новый список, также упорядоченный.
19. Из двух списков чисел извлечь общие числа, большие данного и поместить их в третий список.
20. В списке L1 найти элементы, имеющиеся в списке L2 и заменить их на элементы из списка L3.
21. Имеется список слов. Составить список различных слов данного списка с указанием частоты их появления в нем.
22. Имеется два списка. Определить является ли первый список подсписком второго.
23. Реализовать операции вставки и удаления записей из упорядоченного списка.
24. Отсортировать список, используя метод вставки.
25. Осуществить процедуру слияния двух упорядоченных списков.
26. Переупорядочить элементы списка так, чтобы вначале шли все отрицательные элементы, а затем все неотрицательные элементы.
27. Реализовать операцию поиска максимального элемента списка методом турнира. На каждом этапе попарного сравнения формируется новый список.
28. Имеется два упорядоченных списка. Определить принадлежат ли все элементы второго списка первому списку.
29. Удалить из списка все элементы, принадлежащие второму списку.
30. Элементы списка представляют собой слагаемые многочлена (если коэффициент при степени 0, то элемент в списке отсутствует). Выполнить операцию сложения двух многочленов, представленных списками.
ЗАДАНИЕ N2. Графы и деревья (на LISP’е и HASKELL’е)
5.2.1. Методические указания
Указания к заданию 2: те же, что к заданию 1, но при этом не разрешается использовать встроенные функции, выполняющие специфические операции над деревьями и графами;
5.2.2. Варианты
1. Задано дерево. Найти минимальный и максимальный путь в дереве.
2. Ориентированный граф задан с помощью цепных списков. Определить, является ли он ациклическим.
3. Вычислить сумму рангов всех вершин ориентированного ациклического графа, представленного с помощью цепных списков.
4. Граф задан с помощью цепных списков. Построить его реберный граф.
5. В дереве, организованном с помощью цепных списков, логически удаленные вершины помечены символом «#». Напишите процедуру физического удаления логически удаленных вершин. Сын удаленной вершины переподчиняется ее отцу. Корень дерева удалять запрещено.
6. Дерево задано с помощью цепных списков. Сформировать поддерево с помощью цепных списков, состоящее из помеченных вершин.
7. Граф задан с помощью цепных списков. Определить, существует ли путь между двумя заданными вершинами.
8. Задан граф с помощью цепных списков. Напечатать список участков. Участок - множество вершин, лежащих на одном пути, и имеющих степень два, кроме первой и последней.
9. Заданы два дерева с помощью цепных списков. Определить, является ли второе дерево поддеревом первого.
10. Дано бинарное дерево, некоторые вершины которого помечены. Вывести список путей, проходящих через эти вершины.
11. Дано бинарное дерево и номер уровня. Вывести список вершин, находящихся выше этого уровня.
12. Арифметическое выражение представлено в виде дерева (листья обозначают целые числа, прочие узлы операции). Написать программу вычисления такого выражения.
13. Дано бинарное дерево и номер уровня. Вывести список вершин, находящихся ниже этого уровня.
14. Дано дерево (необязательно бинарное) и номер уровня. Вывести список вершин, находящихся на данном уровне.
15. Дано дерево (необязательно бинарное). Определить путь минимальной длины от корня до листа.
16. Дано дерево (необязательно бинарное). Определить путь максимальной длины от корня до листа.
17. Дано бинарное дерево, некоторые вершины которого помечены. Проверить, находятся ли последние на одном пути от корня к листу.
18. Дано бинарное дерево. Найти путь максимальной длины, и проходящий через заданное множество вершин.
19. Дано дерево (необязательно бинарное). Построить путь от корня до помеченного листа.
20. Дано дерево (необязательно бинарное). Построить список длин путей от корня до листьев.
21. Вершины дерева помечены целыми числами. Построить путь с максимальной суммой чисел.
22. Вершины дерева помечены целыми числами. Построить путь с минимальной суммой чисел.
23. Вершины дерева помечены целыми числами. Построить список сумм чисел на каждом пути от корня до листьев.
24. Вершины дерева помечены целыми числами. Определить лист, к которому ведет путь от корня с максимальной суммой чисел.
25. Дано дерево (необязательно бинарное). Построить список вершин дерева, находящихся на заданном уровне.
26. Дано дерево (необязательно бинарное), вершины которого помечены целыми числами. Построить список сумм чисел для вершин каждого уровня.
27. Дано дерево, две вершины которого помечены. Построить путь, соединяющий эти вершины.
28. Дано бинарное дерево, две вершины которого помечены. Проверить, находятся ли эти вершины на одном пути от корня до листа.
29. Дано бинарное дерево. Построить список листьев этого дерева.
30. Дано бинарное дерево, вершины которого помечены целыми числами. Построить список сумм чисел вершин для всех путей от корня до листьев.
31. Дано бинарное дерево, вершины которого помечены целыми числами. Найти сумму чисел вершин на пути между двумя заданными вершинами этого дерева.
32. Дано бинарное дерево, вершины которого помечены целыми числами. Составить список листьев с указанием их уровней.
33. Сформировать последовательность имен вершин с указанием уровня вершин. Дерево обходить в порядке: левое поддерево, корень, правое поддерево.
34. В бинарном дереве найти всех троюродных братьев заданной вершины.
35. Определить, существует ли путь между двумя вершинами в ориентированном графе.
36. Определить количество вершин, расположенных ниже i-го уровня.
37. Найти длину максимального пути в дереве от корня до листа, не проходящего через помеченные вершины.
38. В бинарном дереве для двух заданных вершин определить все вершины, которые имеют в качестве потомков обе эти вершины.
39. В бинарном дереве найти всех двоюродных братьев вершины, заданной своим значением.
40. Найти длину минимального пути от корня до листа дерева.
41. Сформировать список висячих вершин дерева.
42. Определить количество вершин, расположенных на уровнях с первого по i-ый.
43. Определить количество вершин, расположенных на i-ом уровне.
44. Найти длину пути от корня до помеченного листа дерева.
45. Задано бинарное дерево. Удалить листья этого дерева.
46. Определить множество вершин дерева, расположенных выше уровня помеченной вершины.
47. Найти длину максимального пути от корня до листа дерева.
48. Реализовать операцию удаления вершины дерева. Все сыновья удаляемой вершины подвешиваются под родителя удаляемой вершины.
49. Реализовать операцию удаления поддерева, корень которого задан своим значением.
50. Найти все вершины, лежащие с данной на одном уровне.
51. Реализовать операцию перевешивания поддерева, начинающийся с заданной вершины под некоторый лист этого же дерева.
52. В дереве некоторые вершины помечены. Найти длину максимального пути от корня до помеченной вершины.
53. Найти всех братьев для некоторой вершины, заданной своим значением.
54. Определить, является ли данное дерево бинарным и найти все висячие вершины с максимальным уровнем.
55. Дано дерево (необязательно бинарное). Построить путь максимальной длины до помеченного листа.
56. Найти уровень вершины, имеющий максимальное количество сыновей.
57. Найти уровень вершины, имеющей минимальное количество сыновей.
58. Реализовать операцию вставки вершины между двумя вершинами в бинарном дереве.
59. Реализовать операцию вставки вершины в дерево поиска.
60. Реализовать операцию удаления вершины из дерева поиска.
ЗАДАНИЕ N3. Разные задачи (на LISP’е и HASKELL’е)
5.3.1. Методические указания
Указания к заданию 3: те же, что к заданию 2, но при этом можно использовать любые функции, в том числе функции ввода-вывода и специальные функции преобразования структур и текста.
5.3.2. Варианты
1. Дано положение коня на шахматной доске. Определить минимальный путь коня в заданную точку.
2. Дано положение слона на шахматной доске. Определить минимальный путь слона в заданную точку при наличии на доске запрещенных полей.
3. Напишите программу «Ханойские башни».
4. Напишите программу решения задачи о восьми ферзях.
5. Написать программу ввода и вычисления арифметического выражения (операнды - целые числа).
6. Написать программу символьного умножения двух многочленов от одной переменной.
7. Написать программу интерпретации (вычисления) польской инверсной записи арифметического выражения (операнды - целые числа).
8. Написать программу символьного дифференцирования многочлена от одной переменной.
9. Написать программу вычисления значения логического выражения в дизъюнктивной нормальной форме.
10. Напишите программу, распознающую дизъюнктивную нормальную форму формулы логики высказываний.
11. Напишите программу, которая преобразует префиксную запись арифметического выражения в инфиксную, с учетом того, что знак умножения может быть опущен.
12. Написать программу перемножения двух многочленов от n переменных.
13. Написать программу символического дифференцирования многочлена от n переменных.
14. Написать программу символического дифференцирования дробно-рациональной функции.
15. Написать программу символического дифференцирования произвольного алгебраического выражения (операции + - * /).
16. Написать программу символического дифференцирования выражения, включающего тригонометрические функции (операции + -).
17. Написать программу вычисления значения логического выражения в конъюнктивной нормальной форме.
18. Напишите программу, распознающую конъюнктивную нормальную форму.
19. Напишите программу, определяющую является ли данное выражение правилом языка Пролог.
20. Напишите программу, которая читает символьную запись многочлена от одной переменной, список значений коэффициентов, значение переменной и вычисляет значение многочлена.
21. Напишите программу, моделирующую работу недетерминированного конечного автомата.
22. Напишите программу, которая имитирует игру «Крестики-нолики».
23. Напишите программу, которая имитирует игру «Пятнадцать» («Восемь»).
24. Напишите программу, которая имитирует игру «12 палочек» (на каждом шаге можно взять 1,2 или 3, проигрывает тот, кто берет последнюю).
25. На шахматной доске расположены белые и черные ферзи, ладьи, кони и слоны. Могут ли Белые безнаказанно взять фигуру Черных.
26. Написать программу интерпретации (вычисления) триадной записи программы (предусмотреть арифметические операции и присваивание).
27. Напишите программу, которая имитирует игру «Быки и коровы».
5.4. Упражнения
1.Установить соответствия.
| Формулы l-исчисления | Названия преобразования |
| 1. (lx.M)N=M[x:=N]; 2. M=N Þlx.M=lx.N; 3. lx.M=ly. M [x:= y]/ | 1. a–конверсия 2. b–конверсия 3. правило x |
Правильные ответы: 1-2, 2-3, 3-1.
2.Докажем, что "x,y x=y. В каком шаге доказательства допущена ошибка
| 1. Fºlxy.yx 2. "M,N FMN=NM 3. xy=Fyx 4. º(lxy.yx)yx 5. =(lx(ly.yx)y)x | 6. =(ly.yy)x 7. =xx 8. xy=xx Þx=y 9. "x,y x=y |
Правильный ответ: 6.
3.Установить соответствия.
В языке Дж. Бэкуса функциональные определения соответствуют программам
| Функциональные определения | Описание программы |
| 1. Def aºnull°tl®1; a°tl; 2. Def bºс®1; *°[id,b°d]; 3. Def cºeq°[id,0]; 4. Def dº-°[id,1]; 5. Def eº(/+)°(@*)°Trans; 6. Def fº(@@e)°(@distl)°distr°[1;Trans°2] | 1. сравнение аргумента с нулем 2. вычитание единицы 3. выбор последнего элемента в списке 4. перемножение матриц 5. скалярное произведение 6. факториал |
Правильные ответы: 1-3, 2-6, 3-1,4-2,5-5,6-4.
4.Даны описания функций на языке ЛИСП
(defun u (a b) (+ a b))
(defun v (a) (list 'lambda '(b) (list '+ a 'b)))
(putd v1 '(lambda (a) (list 'lambda '(b) (list '+ a 'b))))
(defun twice (a) (list 'lambda '(x) (list a (list a 'x))))
(defun c (a b) (list 'lambda '(x) (list a (list b 'x))))
(defun v2 (a) (function (lambda (b) (+ a b))))
После их ввода в систему ее реакция на команду: (u 1 2) будет:
Правильный ответ:3.
5.Даны описания функций на языке ЛИСП
После их ввода в систему ее реакция на команду: (v 2) будет:
Правильный ответ: (lambda (b) (+ 2 b)).
6.Даны описания функций на языке ЛИСП
После их ввода в систему, реакция на команду: (apply (v 2)(u 1 2)) будет:
Правильный ответ:5.
7.Даны описания функций на языке ЛИСП
После их ввода в систему ее реакция на команду: (apply (twice ‘cdr) ‘(1 2 3 4 5 6)) будет:
Правильный ответ: (3 4 5 6).
5.5. Содержание отчета
Титульный лист. (должен содержать название курса, номер и название работы, фамилию, инициалы автора, номер группы и другие данные)
Содержание. (содержит названия всех последующих пунктов)
ЗАДАНИЕ N1. Работа со списками.
Постановка задачи. (копия задания)
Авторское понимание задачи. (более детальное изложение возможностей программы своими словами)
Теоретический раздел (см. методические указания, что сделать в теоретическом плане)
Тексты) программ на LISP’е и HASKELL’е
Результаты тестирования программ
Выводы по заданию 1.
ЗАДАНИЕ N2. Графы и деревья.
(Аналогично)
ЗАДАНИЕ N3. Разные задачи.
(Аналогично)
Упражнения
ОБЩИЕ ВЫВОДЫ
ИСПОЛЬЗОВАННАЯ ЛИТЕРАТУРА
ЛИТЕРАТУРА
1.http://ru.wikipedia.org/wiki/ Парадигма_программирования
2.http://ru.wikipedia.org/wiki/ Императивное_программирование
3.http://ru.wikipedia.org/wiki/ Процедурное_программирование
4.http://ru.wikipedia.org/wiki/Объектно – ориентированное программирование
5.http://ru.wikipedia.org/wiki/ Функциональное_программирование
6.http://ru.wikipedia.org/wiki/ Логическое_программирование
7.http://ru.wikipedia.org/wiki/ Структурное_программирование
8.http://ru.wikipedia.org/wiki/ Рекурсивная_функция_(теория_вычислимости)
9.http://ru.wikipedia.org/wiki/ Функция_Аккермана
10. http://ru.wikipedia.org/wiki/ Гипероператор
11. http://www.haskell.ru/ Язык и библиотеки Haskell 98/ Исправленное описание/ Декабрь 2002
12. http://www.rsdn.ru/article/haskell/haskell_part1.xml Мягкое введение в Haskell/ Часть 1/ Авторы: Пол Хьюдак, Джон Петерсон, Yale University, Джозеф Фасел, Los Alamos National Laboratory. Перевод: Денис Москвин. SoftJoys Computer Academy. Источник: A Gentle Introduction To Haskell. Материал предоставил: RSDN Magazine #4-2006/ Опубликовано: 03.03.2007. Исправлено: 24.04.2007. Версия текста: 1.0
13. http://www.rsdn.ru/article/haskell/haskell_part2.xml Мягкое введение в Haskell/ Часть 2/ Авторы: Пол Хьюдак, Джон Петерсон, Yale University, Джозеф Фасел, Los Alamos National Laboratory. Перевод: Денис Москвин. SoftJoys Computer Academy. Источник: A Gentle Introduction To Haskell. Материал предоставил: RSDN Magazine #1-2007/ Опубликовано: 24.04.2007. Исправлено: 15.04.2009. Версия текста: 1.0
14. http://pv.bstu.ru/flp/flplabs.htm Задания к лабораторным работам по дисциплине «Функциональное и логическое программирование». Лабораторные работы по функциональному программированию
15. http://www.rsdn.ru/article/funcprog/monad.xml Монады. Автор: Евгений Кирпичев aka jkff. Источник: RSDN Magazine #3-2008. Опубликовано: 28.12.2008. Исправлено: 15.04.2009. Версия текста: 1.
16. http://www.mari.ru/mmlab/home/lisp/ Лаборатория систем мультимедиа (новый web-сайт) организована в апреле 1993 года в Марийском государственном техническом университете.
17. http://it.kgsu.ru/Lisp/ Кафедра Информацилнных Технологий Курганского Государственного Университета. Шаг за шагом. Язык программирования LISP.
18. Х. Барендрегт. Лямбда-исчисление. Его синтаксис и семантика. Пер. с англ.- М.: Мир, 1985.-606с.
19. Э. Хювёнен, Й. Сеппянен «Мир Лиспа» в 2-х томах. М: Мир 1990г.
20. Хендерсон П. Функциональное программирование. Применение и реализация / Математическое обеспечение ЭВМ: Пер. с англ. (Петрова Л.Т.) - М. : , Мир, 1983 г. - 349 с.
21. Can Programming Be Liberated from \the von Neumann Style? A Functional Style and Its Algebra of Programs/ John Backus/ IBM Research Laboratory? San Jose/ Communications of the ACM/ August 1978, Volume 21, Number 8, pp 613-641.
22. Landin P. The Mechanical Evaluation of Expressions. The Computer Journal. Vol. 6, No. 4, 1964, pp/ 308-320.
Св. план 2012г., поз.42
Дата: 2016-10-02, просмотров: 345.