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

Лекции

Лекция 1. Конспект

Лекция 2. Конспект

Лекция 3. Конспект

Лекция 4. Конспект

Лекция 5. Функции flip, $, ., алгебраические типы. Конспект

Лекция 6. Рисование дерева, ленивые вычисления. Конспект

Лекция 7. Классы типов. Конспект

Лекция 8. Классы типов, Фигуры. Maybe Конспект

Лекция 9. Числовые типы и классы. Создание проекта STACK. Конспект

Лекция 10. Map. Функторы. Конспект

Лекция 11. Алгебраические типы с именованными полями. Аппликативные функторы Конспект. Рисованные картинки стр1, стр2.

Лекция 12. Ввод/Вывод. Монады. Конспект. Рисованные картинки стр.

Лекция 13. Продолжение. Монада Random. Конспект

Лекция 14. Готовая монада Random. Конспект

Задания для зачёта

1. Реализуйте генератор задачек на сложение чисел, это должно быть значение типа Random (String, String). При генерации должны получаться пары значений типа ("Чему равно 3 + 8?", "Ответ: 11"). Это должны быть задачи на сложение двух чисел от 1 до 10. Используйте do-нотацию. Проверьте результат с помощью generateN.
2. Реализуйте функцию filterGerenator :: (a -> Boolean) -> Random a -> Random a, эта функция генерирует случайные значения до тех пор, пока не выполнится условие. Например, filterGenerator even (randomInRange 1 10) создаёт генератор, который генерирует четные числа от 1 до 10.
3. Переделайте задачу 1 так, чтобы в ответе всегда получалась сумма больше 10. Т.е. нужно генерировать «сложные» задачи, где при сложении результат переходит через десяток.
4. Сгенерируйте «много» пар чисел ($K$ штук) от $-N$ до $N$, где $N = 1000$. Это координаты точек в квадрате. Посчитайте, какая часть из этих точек попала в круг с радиусом $N$ и с центром в $0$, т.е. для скольких точек выполняется ($x^2 + y^2 \le N^2$). Если таких точек $L$, можно оценить число $\pi \approx \frac{4L}{N}$.

Задачи

Вводные

1. Напишите вычисление факториала с помощью хвостовой рекурсии.

Операции со списками

Эти задачи нужно решить с хвостовой рекурсией и без хвостовой рекурсии, если без хвостовой рекурсии получается короче.

1. length1 длина списка;
2. last1 возвращает последний элемент списка;
3. push1 дописать элемент в конец списка;
4. repeat1 :: Int -> Char -> String повторить элемент указанное число раз;
5. conc1 конкатенация списков;
6. get1 получить элемент списка по его индексу;
7. rev1 перевернуть список;
8. take1 вернуть список, состоящий из указанного количества начальных элементов списка;
9. filter1 — это аналог встроенной функции filter;
10. map1 — это аналог встроенной функции map;

Теория чисел

Пользуйтесь функциями обработки списков: map, filter и т.п.

1. Дано число, вывести список всех его положительных делителей.
2. Дано число, проверить его на простоту.
   Воспользуйтесь предыдущей задачей, но не перебирайте список делителей полностью, проверьте только, какой делитель идёт после единицы.
3. Дано число, проверить, совершенное ли это число. Другими словами, верно ли что число равно сумме своих делителей, не считая себя. Например, 6 = 1 + 2 + 3.
4. Найдите все совершенные числа от 1 до миллиона
5. Решето эратосфена. Дано n, найдите все простые числа от 1 до n. Прочитайте алгоритм решета Эратосфена, и реализуйте его следующим образом: создайте список чисел от 2 до n, потом отделяйте от него первый элемент, фильтруйте остальные, которые на него делятся. Продолжайте это, пока список не кончится. Обсуждение решета Эратосфена и его реализации на Haskell см. учебник Кубенского.
6. Простые близнецы. Дано n, найдите все пары простых чисел от 1 до n, отличающихся на 2.

Операции на списках

concatMap

Следуюшие задачи нужно решить с помощью встроенной функции concatMap

1. Дан список, повторите каждый его элемент два раза.
2. Опять реализуйте filter
3. Реализуйте map

zip, zipWith и unzip

Используйте функции zip, zipWith, unzip.

1. Реализуйте функцию zipWithIndex: к каждому элементу списка “припишите” его индекс. Т.е. каждый элемент списка должен превратиться в тьюпл, где вначале идет индекс элемента, а потом сам элемент. Начинайте считать элементы с нуля.
2. Сложите каждый элемент списка [Int] с его индексом.
3. Дан список [Int], верните список, в котором все четные по счету элементы заменены на ноль
4. Дан список, удалите из него все элементы с четным индексом.
5. Дан список двузначных чисел. Верните тьюпл из двух списков: первые цифры чисел и вторые цифры чисел. Например, [10, 44, 31] превращается в ([1, 4, 3], [0, 4, 1]).

foldl и foldr

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

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

1. Посчитайте количество элементов в списке
2. Переверните список
3. Припишите один список к другому (операция ++)
4. Реализуйте функцию filter
5. Реализуйте функцию map
6. Реализуйте функцию concatMap. Она имеет тип: (a -> [b]) -> [a] -> [b] и делает следующее: concatMap f l применяет функцию f к каждому элементу списка l и получает списки. Все полученные списки объединяются в один.
7. Реализуйте foldl через foldr. И потом наоборот. (Подсказка: переворачивание списка мы делали через foldl, поэтому его можно использовать во втором случае)
8. Напишите функцию minmax, которая возвращает минимальный и максимальный элемент списка в виде Tuple.

Несколько задач на алгоритмы

Эти задачи не на конкретные функции или приемы, а на то, как запрограммировать что-то содержательное. Вы можете использовать всё, что мы проходили о Haskell.

1. Алгоритм быстрого возведения в степень. Положим, нам нужно вычислить \(x^n\). Запишем следующее равенство: $Answer = a^b \cdot c$. Оно верное, если \(a = x\), \(b = n\), \(с = 1\). Теперь выполняем следующие шаги:
   • Если \(b\) четно, то заменяем \(a \rightarrow a^2\), а \(b \rightarrow b/2\). Теперь \(Answer = (a^2)^{b/2}\cdot c\)
   • Если \(b\) нечетно, то заменяем \(b \rightarrow b-1\), \(с \rightarrow c\cdot a\). Теперь \(Answer = a^{b-1} \cdot (a \cdot c)\)

   Когда \(b\) станет равно нулю, мы получим \(Answer = a^0 \cdot c\), т.е. ответ это \(c\). Реализуйте этот алгоритм функционально, с хвостовой рекурсией

2. Быстрая сортировка
   1. Напишите функцию, которая по списку и заданному числу возвращает три списка в виде Tuple: все элементы, меньшие v; все элементы, равные v; все элементы, большие v.
   2. Напишите функцию, которая сортирует массив рекурсивно: Вызывает функцию из предыдущего пункта для первого элемента массива. Рекурсивно сортирует первый и третий списки, соединяет их опять в один список.
3. Сортировка слиянием.
   1. Напишите функцию, которая делит один список на два одинаковой длины. Или почти одинаковой, если длина нечетна. Просмотртие список функций по работе со списком из стандартной библиотеки, чтобы найти какую-нибудь функцию, которая в этом поможет.
   2. Напишите функцию, которая сливает два отсортированных списка в один отсортированный. Сделайте это рекурсивно, откусывая по одному элементу с начала каждого из списков.
   3. Теперь сама сортировка. Разделите заданный список на два равной длины. Рекурсивно сортируйте оба эти списка, потом слейте их вместе.

Алгебраические типы данных

Не забывайте писать в конце определений типов deriving Show, чтобы значения ваших типов можно было распечатывать.

1. Тип данных “Точка на плоскости”.
   1. Создайте свой собственный тип данных Point (точка на плоскости) У каждой точки есть две Int координаты.
   2. Реализуйте функцию vectorSum поэлементного сложения точек
   3. Реализуйте функцию vectorLength, которая считает длину вектора из нуля до точки
2. Тип данных “Фигура”
   1. Создайте тип данных Figure, значениями этого типа могут быть круги, для которых известен радиус. Прямоугольник, у которого известно две стороны. Равносторонний треугольник, у которого тоже известна одна сторона.
   2. Реализуйте функцию area :: Figure -> Double, которая вычисляет площадь фигуры
3. Введем тип “список”:

    data MyList = Empty | Cons Int MyList deriving Show 
   

   Реализуйте для такого списка операции:

   1. Сумма всех элементов списка
   2. Длина списка
   3. Переворачивание списка

Деревья

Создайте алгебраический тип дерево data Tree a = EmptyTree | TreeNode a (Tree a) (Tree a) и листовое дерево: data LeafTree a = Leaf a | InnerNode (LeafTree a) (LeafTree a). Чем они отличаются? Чем Tree отличается от дерева, введенного в лекции в задаче о рисовании дерева? Как бы вы задали дерево с произвольным количеством детей в каждом узле?

1. Посчитайте количество элементов в дереве и листьев в листовом дереве.
2. Сложите все числа в Tree Int и в LeafTree Int.
3. Дано число n, создайте полное дерево из n уровней: у корня дерева два потомка, у каждого потомка по два потомка, у каждого потомка тоже по два потомка, и так $n$ раз. В дереве из $n$ уровней должно получиться $2^n - 1$ непустых узлов.
4. Исправьте код рисования дерева из лекции так, чтобы он работал для дерева Tree Int из этой задачи. Считайте, что узел Leaf из конспекта — это узел TreeNode, у которого оба потомка EmptyTree. При необходимости нарисовать EmptyTree, рисуйте пустую строку. При этом в дереве будут появляться линии, ведущие к пустому EmptyTree, но мы можем считать, что это нормально. Если хотите усложнить, не рисуйте линии, ведущие к EmptyTree.

   Деревья поиска

Представьте, что у нас есть правило для того, как в числовом дереве Tree Int хранятся значения: значение в узле всегда не меньше всех значений в левом поддереве, и всегда меньше всех значений в правом поддереве. (Если вы уже знаете классы типов, то тип дерева должен быть Ord a => Tree a)

!(Двоичное дерево поиска, wikipedia)[https://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/274px-Binary_search_tree.svg.png]

1. Реализуйте функцию добавления нового значения в дерево.
2. Реализуйте функцию проверки, есть ли в дереве указанное значение.
3. Реализуйте функцию поиска максимального элемента в дереве поиска.
4. Реализуйте функцию поиска и удаления максимального элемента в дереве поиска, функция возвращает пару из значения максимума и нового дерева без максимума.
5. Реализуйте функуцию поиска следующего значения в дереве поиска. Т.е. дано число, и вы возвращаете следующее по порядку число из дерева.
6. Реализуйте аналогичные операции для Декартового дерева.

Бесконечные списки

1. Создайте бесконечный список степеней двойки: [1, 2, 4, 8, 16, ...]. Попробуйте два способа. map для возведения в степень и списка [1..] и умножение на 2 предыдущего значения.
2. Для заданного числа $n$ создайте бесконечный список, который начинается на $n$, а каждое следующее число равно $n/2$, если $n$ — четно, и $3n+1$ иначе.
3. $\varphi_0=1$, $\varphi_1=1$, $\varphi_n = \varphi_{n-2}-\varphi_{n-1}$.
4. $f_0=1$, $f_1=2$, $f_2=3$, $f_n = f_{n-2}f_{n-3}-f_{n-1}$.
5. Создайте бесконечный список 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, … Каждое число повторяется столько раз, чему оно равно.
6. Даны два списка, возможно, бесконечных. Верните список, где значения из списков чередуются. Например, alternate [1, 2, 3, 4, 5] [10, 20, 30] будет [1, 10, 2, 20, 3, 30, 4, 5].
7. Даны два списка, возможно, бесконечных. Это коэффициенты многочлена. Например, список [1,2,3,0,5] соответствует многочлену $1 + 2x+3x^2+5x^4$. Верните сумму этих многочленов. Фактически, вам надо сделать zipWith (+) poly1 poly2, но это обрубит ответ до более короткого списка.
8. В условиях предыдущей задачи верните произведение многочленов.
9. Верните бесконечную последовательность чисел Каталана. $c_0=1$, $c_1=1$, $c_n = \sum_i=0^{n-1} c_ic_{n-1-i}$. Например, $c_2 = c_0c_1 + c_1c_0=2$, $c_3=c_0c_2 + c_1c_1 + c_2c_0 = 5$, далее 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, … http://oeis.org/A000108
10. [http://oeis.org/A000002]
11. Разберите в учебнике Кубенского, как правильно писать решето эратосфена на Haskell, и верните список простых чисел.