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

Ссылки

• haskell.org для установки
• wiki.haskell.org много материалов для изучения
• Haskell Wikibook. Читайте разделы в Haskell Basics: Variables and functions, Truth values, Type basics, Lists and tuples, Next steps. В разделе Elementary Haskell: всё без Types declarations и без разделов о непонятном.
• Кубенский А.А. Функциональное программирование. Для доступа к сайту издательства Юрайт перейдите по ссылке http://cufts.library.spbu.ru/CRDB/SPBGU/resource/306/goto и введите свои университетские логин и пароль.
• Наша лекция про функторы, аппликативные функторы и монады

Задачи

Вводные

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

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

Теория чисел

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

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

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

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 (или списка из двух элементов, если вы еще не знаете, что такое Tuple).

concatMap

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

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

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

Эти задачи не на конкретные функции или приемы, а на то, как запрограммировать что-то содержательное. Вы можете использовать всё, что мы проходили о 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. Теперь сама сортировка. Разделите заданный список на два равной длины. Рекурсивно сортируйте оба эти списка, потом слейте их вместе

zip, zipWith и unzip

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

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

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

Не забывайте писать в конце определений типов 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. Переворачивание списка

Тип Maybe

1. Реализуйте функцию safePop :: [a] -> Maybe (a, [a]), которая по списку возвращает пару (tuple) из его головы и хвоста. Результат заворачивается в Maybe, чтобы учесть ситуацию, когда результата нет, т.е. список пуст.
2. Используя фунцию safePop, реализуйте функцию safeGet :: Int -> [a] -> Maybe a, она должна возвращать элемент списка с указанным индексом.

Классы типов

1. Повторите код с лекции, который создает класс Reversible с методом rev. Потом реализуйте переворачивание Int, cписка.
2. Реализуйте для типа Point следующие классы. Проверьте, что с типом Point начнут работать встроенные функции min, minimum, print и другие, ожидающие типы классов Show, Eq, Ord.
   1. Reversiable: при переворачивании точки меняются местами координаты, и каждая из них переворачивается.
   2. Show: точка записывается в виде строки текста как два числа через точку с запятой.
   3. Eq: две точки можно сравнить на одинаковость
   4. Ord: две точки можно сравнить, при этом реально сравниваются расстояния до (0; 0)

Деревья

В этом разделе задача 1 обязательна.

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

1. Реализуйте для дерева класс Show.
   1. В простой версии вам нужно вывести все дерево в одну строку, расставив скобки: Например, 1[2[5, 6], 3[_,5]], здесь в корне записана 1, у нее потомки 2 и 3. У двойки потомки 5 и 6, у тройки правый потомок 5.
   2. В сложной версии сделайте красивый вывод дерева, как в команде tree в linux:

       1
       ├── 2
       │   ├── 5
       │   └── 6
       └── 3
       └── 5
      

2. Реализуйте для дерева функцию сворачивания. Она принимает на вход две функции, соответствующие каждому из конструкторов: f1 :: b (для конструктора EmptyTree), f2 :: a -> b -> b -> b (для конструктора TreeNode, мы имеем одно значение в узле и два свернутых значения из поддеревьев). И еще она принимает на вход дерево: treeFold :: b -> (a -> b -> b -> b) -> Tree a -> b.
3. Аналогично, для листового дерева придумайте сигнатуру и реализуйте сворачивание.
4. Для листового дерева реализуйте listifyLeafTree, превращение в список. Просто значения из листьев выписываются слева направо. Вы можете использовать для этого реализованное выше сворачивание.
5. Аналогично для обычного дерева реализуйте listifyTreeFirst, listifyTreeLast, listifyTreeBetween, это три разных превращения в список. Они отличаются тем, в какой момент корень дерева попадает в список. В начале, в конце или между тем как в список попадет левое поддерево, и до того, как попадет правое. Попробуйте начать писать превращение в список с помощью свораивания, чтобы понять, что имеется в виду.
6. Имея listify для деревьев, сделайте их представителями класса Foldable.

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

7. Дерево поиска. Представьте, что у нас есть правило для того, какие значения хранятся в дереве. Значение в узле всегда не меньше всех значений в левом поддереве, и всегда меньше всех значений в правом поддереве. Реализуйте функцию добавления нового значения в дерево.

   Кстати, как вы опишете тип у такой функции? Вы можете для простоты считать, что дерево поиска это Tree Int, но лучше считайте, что это Ord a => Tree a, т.е. дерево из любого упорядоченного типа.

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

Функторы, Аппликативные функторы

Лекция: Функторы, Аппликативные функторы, Монады

1. Сделайте деревья из прошлого раздела (хотя бы одно) функтром.
2. * Придумайте, как можно сделать листовое дерево аппликативным функтором
3. Даны два значения Maybe Int. Верните их сумму тоже в виде Maybe Int. Используйте <$> и <*>.
4. Даны два списка [Int]. Получите новый список, где каждый элемент первого сложен с каждым элементов второго. Используйте <$> и <*>.
5. Реализуйте монаду Log с лекции.
6. Монада IO. Напишите функцию, которая читает два числа с клавиатуру и возращает их сумму IO Int. Воспользуйтесь этой функцией внутри main.