Функциональное программирование

Тольяттинский государственный университет (Росдистант), ТГУ. Функциональное программирование.

Практическое задание № 1

Задание 1

Приведите пример нетривиальных выражений, принадлежащих следующему типу:

• ((Char,Integer), String, [Double])

• [(Double,Bool,(String,Integer))]

• ([Integer],[Double],[(Bool,Char)])

• [[[(Integer,Bool)]]]

• (((Char,Char),Char),[String])

• (([Double],[Bool]),[Integer])

• [(Integer, (Integer,[Bool]))]

• (Bool,([Bool],[Integer]))

• [([Bool],[Double])]

• [([Integer],[Char])]

2. Напишите функции, решающие следующие задачи:

2.1. Три точки A, B, C лежат на одной прямой. Заданы длины AB, BC, AC. Может ли точка A лежать между точками B и C.

2.2. Чему равен угол, если два смежных с ним угла составляют в сумме заданное число градусов.

2.3. Периметр равнобедренного треугольника равен P метрам, а боковая сторона L. Найти основание треугольника.

2.4. Найти углы треугольника, еcли они пропорциональны заданным числам A, B, C.

2.5. В равнобедренном треугольнике боковая сторона A, а основание B. Найти высоту, опущенную на основание.

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

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

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

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

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

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

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

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

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

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

Практическое задание № 2

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

1.2. Список натуральных чисел.

1.3. Список нечетных натуральных чисел.

1.4. Список четных натуральных чисел.

1.5. Список кубов натуральных чисел.

1.6. Список факториалов.

1.7. Список степеней десятки.

1.8. Список треугольных чисел (треугольное число равно количеству одинаковых кругов, из которых можно построить равносторонний треугольник, на каждой стороне которого укладываются эти круги.)

1.9. Список пирамидальных чисел (пирамидальное число равно количеству одинаковых шаров, из которых можно построить правильную пирамиду с треугольным основанием, на каждой стороне которой укладывается шары)

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

2.1. Функция, вычисляющая сумму квадратов целых чисел от 1 до n.

2.2. Функция, вычисляющая произведение целых чисел от 1 до n.

2.3. Функция, принимающая на входе список вещественных чисел и вычисляющая их арифметическое среднее. Функция, принимающая на входе список вещественных чисел и вычисляющая их геометрическое среднее.

2.4. Функция выделения n-го элемента из заданного списка.

2.5. Функция выделения n-m-го элемента из заданного списка.

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

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

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

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

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

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

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

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

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

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

Практическое задание № 3

1. В интернет-магазинах продают книги, видеокассеты и компакт-диски. База данных магазина для каждого типа товаров должна содержать следующие характеристики:

• Книги: название и автор

• Видеокассеты: название

• Компакт-диск: название, исполнитель и количество композиций

1) Разработайте тип данных Product , который может представлять эти виды товаров.

2) Определите функцию getTitle, возвращающую название товара.

3) На ее основе определите функцию getTitles , которая по списку товаров возвращает список их названий.

4) Определите функцию bookAuthors, которая по списку товаров возвращает список авторов книг.

5) Определите функцию lookupTitle : : String -> [Product] -> Maybe Product которая возвращает товар с заданным названием (обратите внимание на тип результата функции)

6) Определите функцию lookupTitles : : [String] - > [Product] - > [Product], которая принимает в качестве параметров список названий и список товаров и для каждого названия извлекает из второго списка соответствующие товары. Названия, которым не соответствует ни один товар, игнорируются. При определении функции обязательно используйте функцию lookupTitle

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

1) isMinor, проверяющую, что ее аргумент является младшей картой.

2) sameSuit , проверяющую, что переданные в нее карты одной масти.

3) beat s : : Card -> Card -> Bool, проверяющую, что карта, переданная ей в качестве первого аргумента, бьет карту, являющуюся вторым аргументом.

4) beats2, аналогичная beats, но принимающая в качестве дополнительного аргумента козырную масть.

5) beatsList, принимающая в качестве аргументов список карт, карту и козырную масть и возвращающая список тех карт из первого аргумента, которые бьют указанную карту с учетом козырной масти.

6) Функция, по заданному списку карт возвращающая список чисел, каждое из которых является возможной суммой очков указанных карт, рассчитанных по правилам игры в «двадцать одно» : младшие карты считаются по номиналу, валет, дама и король считаются за 10 очков, туз может рассматриваться и как 1 и как 11 очков. Функция должна вернуть все возможные варианты.

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

1) area, возвращающую площадь фигуры. Для текстового поля площадь зависит от высоты и ширины буквы в шрифте. Если выбранные шрифты моноширинные и ширина всех букв одинакова, необходимо также определить вспомогательную функцию, для каждого шрифта возвращающую его габариты.

2) getRectangles, из списка фигур выбирающую только прямоугольники.

3) getBound, по заданной фигуре возвращающую ограничивающий ее прямоугольник.

4) getBounds, по списку фигур возвращающую список их ограничивающих прямоугольников.

5) getFigure, по заданному списку фигур и координатам точки возвращающую первую фигуру, для которой точка попадает в ее ограничивающий прямоугольник. Используйте тип Maybe для возвращаемого значения.

6) move, по заданной фигуре и вектору сдвига возвращающую новую фигуру, сдвинутую относительно заданный на указанный вектор.

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

1) getHouses, выбирающую из базы данных только частные дома.

2) getByPrice, выбирающую из базы данных те объекты недвижимости, цена которых меньше указанной.

3) getByLevel, выбирающую из базы данных квартиры, находящиеся на указанном этаже.

4) getExceptBounds, выбирающую из базы данных квартиры, не находящиеся на крайних этажах

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

5. В библиотеке хранятся книги, газеты и журналы. Книга характеризуется именем автора и названием; журнал -названием, месяцем и годом выпуска; газета - названием и датой выпуска. База данных представляет собой список этих объектов. Разработайте тип данных, представляющий объекты библиотечного хранения. Определите следующие функции:

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

2) getByTytle, выбирающую из списка объектов хранения (базы данных) объекты с указанным названием.

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

4) getByMonths, действующую так же, как и предыдущая, но принимающую список месяцев.

5) getAuthors, возвращающую список авторов изданий, хранящихся в базе данных.

6. В некотором языке программирования существуют следующие типы данных:

• Простые типы: целые, вещественные и строки

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

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

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

1) isStructured, проверяющую, что ее аргумент является сложным типом.

2) getType, по заданному имени и списку идентификаторов (по базе данных) возвращающую тип идентификатора с указанным именем (при этом идентификатора в базе может и не оказаться) .

3) getFields , по заданному имени возвращающую список полей идентификатора, если он имеет тип структуры.

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

5) getByTypes, аналогичная предыдущей, но принимающую вместо одного типа список типов.

7. Определите следующий набор операций над строками:

• удаление всех символов из строки

• удаление всех вхождений указанного символа

• замена всех вхождений одного символа на другой

• добавление в начало строки указанного символа

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

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

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

3) deleteAll, принимающую две строки и удаляющую из второй строки все символы первой. При реализации обязательно использовать функцию processAll.

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

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

1) getByName, возвращающую информацию о человеке с указанным именем.

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

3) getAss ignment, возвращающая по указанной дате список дел.

9. Клавиши на клавиатуре могут быть либо управляющими, либо алфавитно-цифровыми. Нажатие алфавитно-цифровой клавиши может сопровождаться нажатием клавиши Shift. Из управляющих клавиш нас интересует только клавиша CapsLock, остальные можно не различать. Каждое нажатие алфавитно-цифровой клавиши несет с собой информацию в виде символа. После нажатия CapsLock последующие символы переводятся в верхний регистр до следующего нажатия CapsLock. Если режим CapsLock не активирован, символы, нажатые с Shift, переводятся в верхний регистр. Разработайте тип данных, представляющий указанную информацию, при этом последовательность нажатий клавиш представляется в виде списка. Задача состоит в том, чтобы разработать функцию, переводящую эту последовательность в строку символов. Например, последовательность нажатий Shift+ ' h ' ' e ' CapsLock ' l ' ' l ' Shift+ ' o ' CapsLock должна дать в результате строку HeLLo. Определите следующие функции:

1) getAlNum, возвращающую из списка нажатий только нажатия алфавитно-цифровых клавиш.

2) getRaw, возвращающую строку, составленную из нажатых символов без учета информации о Shift и CapsLock.

3) isCapsLocked, по последовательности нажатий определяющую, остался ли после нее режим CapsLock в активированном состоянии.

4) getString, переводящую последовательность нажатий в строку.

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

import Char

10. За время учебы в семестре студенты должны сдать определенное количество лабораторных работ, расчетно-графических заданий и рефератов. Лабораторная работа характеризуется названием предмета и номером, РГЗ -названием предмета, реферат – названием предмета и названием темы реферата. Разработайте тип данных, представляющий информацию по заданию. Учебный план студента представляет собой список, состоящий из пар, первый элемент которых является заданием, а второй - номером недели, в которую он был сдан. Если задание еще не сдано, второй элемент пары должен быть пустым (используйте тип Maybe) . Определите следующие функции:

1) getByTitle, возвращающую задания, которые необходимо сдать по указанному предмету.

2) getReferats - возвращающую список тем рефератов.

3) getRest - возвращающую список оставшихся несданными заданий.

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

5) getPlot - создающую список, состоящий из пар, первый элемент которых равен номеру недели, а второй - количеству сданных на эту неделю заданий.

Практическое задание № 4

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) toList, преобразующая заданное дерево поиска в список, упорядоченный по значениям ключей.

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, добавляющую в иерархию классов класс с заданным именем, унаследованный от указанного предка.

Практическое задание № 5

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

1.1. Функцию вычисления геометрического среднего элементов списка вещественных чисел с использованием функции foldr. Функция должна осуществлять только один проход по списку.

1.2. Функцию вычисляющую скалярное произведение двух списков (используйте функции foldr и zipWith).

1.3. Функцию countNegat, возвращающую количество отрицательных элементов в списке.

1.4. Функцию quicksort, осуществляющая быструю сортировку списка по следующему рекурсивному алгоритму. Для того чтобы отсортировать список xs, из него выбирается первый элемент x. Остальной список делится на две части: список, со-стоящий из элементов xs, меньших x и список элементов, больших x. Эти списки сортируются с помощьюрекурсии, а затем из них составляется результирующий список вида as ++ [x] ++ bs, где as и bs –отсортированные списки меньших и больших элементов соответственно.

1.5. Определенная в предыдущем пункте функция quicksort сортирует список в порядке возрастания. Обобщите ее: пусть она принимает еще одну функцию сравнения типа a -> a-> Bool и сортирует список в соответствии с ней.

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