Домашние задания, осень 2014, 243 группа
В табличке:
пусто - задача не сдавалась-1 - задача нагло списана и будет заменена другой
0 - задача не зачтена
0.5 - задача решена не до конца, либо хочется что-то изменить
1 - задача зачтена
Работы, выделенные зеленым, зачтены полностью. Фамилии, выделенные зеленым, обозначают людей, набравших нужное для зачета число решенных задач.
Условия задач:
Домашнее задание 1. 17.02.2014
Конспект парыЛямбда-исчисление для самых маленьких
- Реализовать программу подсчета факториала
- Реализовать программу подсчета i-го числа Фибоначчи
Домашнее задание 2. 24.02.2014
Конспект пары- Реализовать функцию обращения списка. Функция должна работать за линейное время (подсказка: конкатенация — это плохо)
- Реализовать функцию, которая формирует список из n последовательных степений двойки (n — аргумент функции)
- Реализовать функцию, которая вычисляет сумму цифр данного числа
- Реализовать функцию, которая выдает первую позицию вхождения заданного числа в список
- Реализовать функцию, проверяющую, является ли строка палиндромом
Домашнее задание 3. 03.03.2014
Конспект пары- Записать следующую функцию в point-free стиле: func x l = map (\y -> y*x) l. В комментариях показать все промежуточные шаги преобразований.
- Реализовать функцию, генерирующую бесконечный список степеней двойки. Функция должна быть реализована с помощью "завязывания в узел".
- Реализовать функцию, генерирующую бесконечный список, содержащий все целые положительные числа, состоящие только из цифр 1, 7 и 9 (числа должны идти в порядке возрастания). Например, первые 10 чисел в этом списке должны быть [1,7,9,11,17,19,71,77,79,91]. Функция должна быть реализована с помощью "завязывания в узел".
- Вывести первую позицию в списке, на которой сумма двух соседних элементов максимальна. Например, для [1, 5, 6, 2] функция должно вернуть значение 2.
- Посчитать высоту дерева, а также минимальное расстояние в дереве от корня до листьев.
- Реализовать функцию, которая по произвольной строке проверяет корректность скобочной последовательности в этой строке.
- [необязательная] Записать следующую функцию в point-free стиле: func f g l = filter f (map g l)
Домашнее задание 4. 10.03.2014
Конспект пары- Реализовать функцию поиска по некоторому условию в двоичном дереве. Условие передается в качестве параметра.
- Реализовать функцию свертки для бинарного дерева.
- Реализовать три варианта функции, подсчитывающей количество четных чисел в списке (с использованием стандартных функций map, filter, foldr). Использование рекурсии не допускается.
- Проверить, что все элемента списка различны
- Написать программу, которая в диалоговом режиме позволяет осуществлять следующие операции:
0 - exit
1 - add value to sorted list
2 - remove value from list
3 - print list
Все операции должны сохранять сортированность. Начинаем с пустого списка.
Домашнее задание 5. 17.03.2014
Конспект пары- Реализовать функцию, которая по заданному числу n выводит все его разложения на положительные слагаемые (с точностью до порядка разложения)
- Проверить, что все элементы списка удовлетворяют некоторому условию (условие передается как параметр)
- Опишите функцию, которая для данного числа n возвращает список из всех строк длины n, состояших из чисел 1,2,3. Например, при n=2 функция должна вернуть список [[1,1], [1,2], [1,3], [2,1], [2,2], [2,3], [3,1], [3,2], [3,3], ]
- С помощью оператора >>= опишите функцию, которая для данного числа n создает список из всех попарных произведений чисел от 1 до n. ( Т.е. что-то такое: [1*1, 1*2, 1*3, …, 1*n, 2*1, 2*2, …, n*n] - всего n*n элементов)
- Используя монадичесие функции, опишите фунцию, которая ищет в списке первый элемент, больший своих соседей (предыдущего и следующего)
- Дано выражение, содержащее переменную, константы, арифметические операции. Посчитать производную этого выражения по этой переменной, провести в полученном выражении для производной возможные упрощения (например, 1*x = x). Подходящий тип данных разработать самостоятельно
Домашнее задание 6. 07.04.2014
Конспект пары- Для двоичного дерева, элементы которого – символы, реализовать две функции: одна по дереву строит его представление в виде строки, а вторая функция по этой строке восстанавливает исходное дерево. Дерево должно храниться в следующем формате: Empty кодируется буквой 'e', Node x left right кодируется так: сначала буква 'n', потом символ x, потом подряд без разделителей представления для left и right
- Описать тип, позволяющий хранить информацию о многочленах с одной переменной, и реализовать для него сложение, умножение и show
- Реализовать тип данных BinarySearchTree и соответствующие функции для работы с ним: добавление, удаление, поиск, размер (число элементов), высота
- Для типа Graph, разбиравшегося на паре, реализовать алгоритм Дейкстры поиска кратчайшего пути. Поиск пути должен производиться с использованием экземпляров класса типов Monad или MonadPlus
Темы докладов:
Модульное тестирование в Haskell(Анастасия Семенова)- Средства распараллелирования программ в Haskell
Средства для работы с сетью в Haskell(Владимир Глазачев)- Библиотека парсер-комбинаторов Parsec
Создание графических приложений на Haskell (на примере одной из библиотек)(Евгений Моисеенко)