Функциональное программирование /Росдистант/ Практические задания (Вариант 5-Д,С,Ш)

Функциональное программирование /Росдистант/ Практические задания (Вариант 5-Д,С,Ш)

Тема 1. Введение в функциональное программирование

Учебные вопросы:

1.  Цели и задачи дисциплины «Функциональное программирование»

2.   Алгоритм: определение, свойства и способы записи.

3.  Изобразительные средства алгоритмов: словесный, формульно-словесный, блок-схема.

4.  Транслятор: назначение, классификация, этапы процесса трансляции.

Тема 2. Операции и стандартные библиотечные функции языка

Учебные вопросы:

1. Процедуры: создание и использование в программах.

2. Операторы: понятие, назначение, классификация

3. Переменные: назначение, классификация, описание в программе, работа с данными.

Тема 3. Типы данных в Haskell

Учебные вопросы:

1.  Какие основные типы данных существуют в Haskell?

2.  Что такое алгебраические типы данных и как они используются в Haskell?

3.  Как работают полиморфные типы данных в Haskell и какие преимущества они предоставляют?

4.  Что такое параметрический полиморфизм и как он применяется к типам данных?

5.  Как использовать классы типов для определения ограничений на типы данных?

6.  Что такое монадические типы данных и как их можно использовать в Haskell?

Задание 1.1. Базовые алгоритмические структуры

Вычислить значение функции y по заданной формуле. Значения исходных данных x, a и b ввести с клавиатуры. Результат вывести на печать. Функция выбирается из таблицы 1.2.

Определить тип вычислительного процесса. Написать программу на языке Haskell. Представить результаты вычислений по заранее подготовленному тесту.

Для отладки программы можно использовать онлайн.

Из таблицы 1.1 выбрать номер варианта (по первой букве фамилии). Из таблицы 1.2 выбирается задание.

аблица 1.2

Задание

1

Даны координаты центров и радиусы двух окружностей на плоскости. Определить может ли вторая окружность целиком содержаться внутри первой? Если нет, то сколько точек пересечения имеют окружности?

2

Определить можно ли из отрезков с заданными длинами A, B, C построить прямоугольный треугольник?

3

Определить можно ли из круглого листа железа диаметром D метров вырезать квадрат со стороной A метров?

4

Стороны треугольника A, B, C. Найти высоту, опушенную на строну C.

5

Высота равнобедренного треугольника H метров, основание L. Найти углы треугольника и длину боковой стороны.

6

По данной хорде A найти длину дуги, если она соответствует центральному углу в C градусов.

7

Найти точку, равноудаленную от осей координат и от точки с заданными координатами (x,y).

8

Даны четыре точки A, B, C, D на плоскости. Является ли четырехугольник ABCD параллелограммом?

9

Составить уравнение прямой, проходящей через 2 заданные точки.

10

Даны четыре точки A, B, C, D на плоскости. Является ли четырехугольник ABCD квадратом?

Тема 4. Рекурсивные функции

Учебные вопросы:

1.  Что такое рекурсия в контексте функционального программирования?

2.  Как рекурсивные функции используются для обработки списков в Haskell?

3.  Какие виды рекурсии существуют в Haskell и как они работают?

4.  В чём разница между хвостовой и нехвостовой рекурсией?

5.  Как использование рекурсии влияет на производительность функций в Haskell?

6.  Как можно оптимизировать рекурсивные функции в Haskell для повышения производительности?

7.  Как в Haskell реализуются рекурсивные типы данных, такие как списки и деревья?

Методические указания по выполнению самостоятельной работы студентов:

1.  Для более глубокого усвоения материала лекции необходимо ознакомится с рекомендованной литературой по дисциплине.

2.  Выполнить практическое задание, цель которого - сформировать навыки работы с рекурсивными функциями.

Задание 2.1

Составить программу по заданию, согласно варианту.

Построить алгоритм в виде блок-схемы, используя стандартные средства Microsoft Word, написать программу на языке Haskell. Для отладки программы можно использовать онлайн-компилятор. Представить результаты вычислений по заранее подготовленному тесту.

Из таблицы 2.1 выбрать номер варианта (по первой букве фамилии). Из таблицы 2.2 выбирается задание.

Таблица вариантов задания 2.2

Вариант

Задание

1

Функция умножения элементов двух списков. Возвращает список, составленный из произведения элементов списков-параметров. Учтите, что переданные списки могут быть разной длины.

2

Функция перестановки местами соседних четных и нечетных элементов в заданном списке.

3

Функция, которая вычисляет 2 в степени n. Функция не должна использовать оператор ^ или любую функцию возведения в степень из стандартной библиотеки.

4

Функция, которая удаляет из заданного списка целых чисел все четные числа. Например: по списку [1,4,5,6,10] должно возвращаться [1,5] .

5

Функция f, которая удаляет из заданного списка целых чисел все числа, меньшие заданного . Например: f 5 [1,4,5,6,10] должно возвращаться [5,6,10] .

6

Функция, которая удаляет пустые строки из заданного списка строк. Например: при ["", "Hello", "", "", "World!"] функция возвращает ["Hello","World!"] .

7

Функция, которая меняет знак всех положительных элементов списка чисел, например: по [-1, 0, 5, -10, -20] дает [-1,0,-5,-10,-20]

8

Функция f типа Char -> String -> String , которая принимает на вход строку и символ и возвращает строку, в которой удалены все вхождения символа. Пример: f ’l' "Hello world!" должно возвращать "Heo word!".

9

Функция f типа Char -> String -> String , которая принимает на вход строку и символ и возвращает строку, в которой продублированы все вхождения символа. Пример: f ’о' "Hello world!" должно возвращать "Helloо woоrld!".

10

. Функция f типа Char -> Char -> String -> String , которая заменяет в строке указанный символ на заданный. Пример: f 'e’ 'i’ "eigenvalue" возвращает "iiginvalui".

Тема 5. Операторы, рекурсивные типы и синтаксические деревья

Учебные вопросы:

1.  Какие виды операторов существуют в Haskell? Как они работают с различными типами данных?

2.  Что такое рекурсивный тип данных и как он используется в Haskell для определения сложных структур данных?

3.  Как можно использовать рекурсию для построения синтаксических деревьев в Haskell и что это даёт?

4.  Какие преимущества даёт использование рекурсивных типов данных при работе с синтаксическими деревьями?

5.  Как операторы применяются к рекурсивным типам данных в Haskell, и какие особенности их использования следует учитывать?

6.  Как в Haskell реализуется сопоставление с образцом для работы с рекурсивными типами данных и синтаксическими деревьями?

Методические материалы к занятию: 

1.  Для изучения данной темы необходимо изучить материалы электронного учебника.

2.  Необходимо выполнить тестовые задания, которые закрепят освоения основных вопросов по данной теме.

Задание 3.1

Составить программу по заданию, согласно выбранному варианту.

Составить программу на языке Hascell.

Для отладки программы можно использовать онлайн-компилятор.

Номер варианта выбирается из таблицы 3.1 по первой букве фамилии студента.

Задание выбрать из таблицы 3.2.

Задание 3.2

Составить программу по заданию, согласно выбранному варианту.

Таблица вариантов задания 3.2

Ва-риант

Задание

1

. Работа с типом Expr. Используя тип Expr, определенный выше, реализуйте следующие функции (используйте для тестирования функцию parseExpr)

1) Определите корректную функцию diff, которая принимает в качестве дополнительного аргумента имя переменной, по которой необходимо осуществлять дифференцирование.

2) Определите функцию simplify, которая упрощает выражения типа Expr, применяя очевидные правила вида:

• x + 0 = 0 + x = x

• x · 1 = 1 · x = x

• x · 0 = 0 · x = 0

• и т. д.

3) Определите функцию toString, преобразующую выражение типа Expr в строку. Например, результатом применения функции к выражению Add (Mult (Const 2) (Var "x")) (Var "y") должна быть строка "2*x+y". Учтите возможность использования скобок, например, выражение Mult (Const 2) (Add (Var "x") (Var "y")) должно преобразовываться в строку "2*(x+y)"

4) Определите функцию eval, которая принимает два параметра: выражение типа Expr и список пар типа (String,Integer), задающий соответствие имен переменных и их значений. Функция должна вычислять значение выражение с учетом заданных значений выражений. Например, выражение eval (Add (Var "x") (Var "y")) [("x",1),("y",2)] должно выдавать число 3.

2

Функции для работы с типом List. Для введенного ранее типа List определите следующие функции:

1) lengthList, возвращающую длину списка типа List.

2) nthList, возвращающую n-й элемент списка.

3) removeNegative, которая из списка целых (тип List Integer) удаляет отрицательные элементы.

4) fromList, преобразующую список типа List в обычный список.

5) toList, преобразующую обычный список в список типа List.

3

Функции работы с бинарными деревьями поиска. Определите тип данных, представляющий бинарные деревья поиска. В деревьях поиска данные могут находиться не только в листьях, но и в промежуточных узлах дерева. Используйте деревья для представления ассоциативного массива, сопоставляющие значения ключей (представляемых как строки) целым числам. Для каждого узла с некоторым ключом в левом поддереве должны содержаться элементы с меньшими значениями ключа, а в правом — с большими. При поиске соответствия между строкой и числом необходимо учитывать эту информацию.

. Определите описанный тип данных и следующие функции:

1) add, добавляющую в дерево заданную пару ключа и значения.

2) find, возвращающую число, соответствующее заданной строке.

3) exists, проверяющую, что элемент с заданным ключом содержится в дереве.

4

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

1) dirAll, возвращающую список полных имен всех файлов каталога, включая подкаталоги.

2) find, возвращающаую путь, ведущий к файлу с заданным именем. Например, если каталог содержит файлы a, b и c, и b является каталогом, содержащим x и y, тогда функция поиска для x должна вернуть строку "b/x".

3) du, для заданного каталога возвращающую количество байт, занимаемых его файлами (включая файлы в подкаталогах).

5

Утверждением будем называть логическую формулу, имеющую одну из следующих форм:

• имя переменной (строка)

• p & q

• p | q

• ~p

где p и q — утверждения. Например, утверждениями являются следующие формулы:

• x

• x | y

• x & (x | ~y)

Разработайте тип данных Prop, представляющий утверждения такого вида. Определите следующие функции:

1) vars :: Prop -> [String], которая возвращает список имен переменных (без повторений), встречающихся в утверждениях.

2) Пусть задан список имен переменных и их значений типа Bool, например [("x",True),("y",False)]. Определите функцию truthValue :: Prop -> [(String,Bool)] -> Bool, которая определяет, верно ли утверждение, если переменные имеют заданные списком значения.

3) Определите функцию tautology :: Prop -> Bool, которая возвращает True, если утверждение верно при любых значениях переменных, встречающихся в нем (например, это выполняется для утверждения (x | ~x)).

6

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

Булевское значение, равное True отмечает конец слова, читаемого, начиная с корня дерева.

Определите следующие функции:

• exists, которая проверяет, что заданное слово содержится в trie-дереве.

• insert, которая по дереву и слову возвращает новое дерево, в которое включено это слово. Если слово уже содержится в дереве, оно должно возвращаться без изменений.

всех слов из дерева, началом которых служит указанная строка

7

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

data Number = Zero | Next Number

Т. е. число является либо нулем (Zero), либо определяется, как число, следующее за предыдущим числом. Например, число 3 записывается как Next (Next (Next Zero)). Определите для такого представления следующие функции:

1) fromInt, для заданного целого числа типа Integer возвращающую соответствующее ему значение типа Number.

2) toInt, преобразующую значение типа Number в соответствующее целое число.

3) plus :: Number -> Number -> Number, складывающую свои аргументы.

4) mult :: Number -> Number -> Number, умножающую свои аргументы.

5) dec, вычитающую единицу из своего аргумента. Для Zero функция должна возвращать Zero.

6) fact, вычисляющую факториал.

8

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

1) getSubordinate, возвращающую список подчиненных указанного работника.

2) getAllSubordinate, возвращающую список всех подчиненных данного работника, включая косвенных.

3) getBoss, возвращающую начальника указанного работника.

4) getList, возвращающую список пар, первым элементом которых является имя работника, а вторым — количество его подчиненных (включая косвенных).

9

. Область на плоскости является либо прямоугольником, либо кругом, либо объединением областей, либо их пересечением. Прямоугольник характеризуется координатами левого нижнего и правого верхнего углов, круг — координатами центра и радиусом. Разработайте структуру данных, представляющую область описанного вида. Определите следующие функции:

1) contains, проверяющую, что заданная точка попадает в область.

2) isRectangular, проверяющую, что область задается только прямоугольниками.

3) isEmpty, проверяющую, что область пуста, т. е. ни одна точка плоскости не попадает в нее.

10

. Класс в объектно-ориентированном языке содержит набор методов. Кроме этого, он может иметь единственный родительский класс. Однако существуют классы и без родителей. При наследовании класса методы предка добавляются к методам потомка. Определите тип данных, представляющий информацию об иерархии классов. Опишите следующие функции:

1) getParent, возвращающую непосредственного предка класса с указанным именем.

2) getPath, возвращающую список всех предков данного класса (непосредственный предок, предок предка и т. д.)

3) getMethods, возвращающую список методов указанного класса с учетом наследования.

4) inherit, добавляющую в иерархию классов класс с заданным именем, унаследованный от указанного предка.

Тема 6. Функции высшего порядка

Учебные вопросы:

1.  Что такое функции высшего порядка? Как они используются в Haskell?

2.  Какие виды функций высшего порядка существуют в Haskell и как они работают?

3.  Как каррирование и частичное применение функций связаны с функциями высшего порядка?

4.  В чём разница между функциями высшего порядка и обычными функциями?

5.  Как можно использовать функции высшего порядка для обработки списков и других структур данных в Haskell?

6.  Как функции высшего порядка могут быть использованы для создания новых функций на основе существующих?

Методические материалы к занятию: 

1.  Для изучения данной темы необходимо изучить материалы электронного учебника.

2.  Необходимо выполнить тестовые задания, которые закрепят освоения основных вопросов по Таблица 4.2

Ва-риант

Задание

1

Создайте функцию, которая принимает другую функцию в качестве аргумента и возвращает список, состоящий из результатов применения этой функции к каждому элементу списка.

2

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

3

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

4

Создайте функцию, которая принимает функцию в качестве аргумента и применяет её к каждому элементу списка, возвращая новый список. Примените эту функцию для вычисления квадратов чисел в списке.

5

Напишите функцию высшего порядка, которая принимает три функции в качестве аргументов: одну для фильтрации списка, вторую для преобразования элементов списка и третью для объединения результатов. Используйте эту функцию для создания нового списка на основе исходного.

6

 Реализуйте функцию, которая принимает функцию в качестве аргумента и использует её для сортировки списка по возрастанию или убыванию в зависимости от переданной функции.

7

Создайте функцию высшего порядка, которая принимает функцию и список в качестве аргументов, применяет функцию к каждому элементу списка и возвращает результат в виде строки.

8

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

9

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

10

Создайте функцию высшего порядка, которая принимает функцию и два списка в качестве аргументов, объединяет их и применяет функцию к каждой паре элементов из обоих списков