Задачи

Вводные

1. Напишите факториал с хвостовой рекурсией
2. Функция sum1 складывает элементы списка.
   1. Сделайте вариант с хвостовой рекурсией
3. last1 возвращает последний элемент списка
4. conc1 конкатенация списков
5. push дописать элемент в конец списка
6. repeat :: Int -> Char -> [Char] повторить элемент указанное число раз
7. get1 получить элемент списка по его индексу
8. rev перевернуть список

Теория чисел

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

1. Дано число, вывести список всех его положительных делителей.
2. Дано число, проверить его на простоту.
   Воспользуйтесь предыдущей задачей, но не перебирайте список делителей полностью, проверьте только, какой делитель идёт после единицы.
3. Дано число, проверить, совершенное ли это число. Другими словами, верно ли что число равно сумме своих делителей, не считая себя. Например, 6 = 1 + 2 + 3.
4. Найдите все совершенные числа от 1 до миллиона
5. Решето эратосфена. Дано n, найдите все простые числа от 1 до n. Прочитайте алгоритм решета Эратосфена, и реализуйте его следующим образом: создайте список чисел от 2 до n, потом отделяйте от него первый элемент, фильтруйте остальные, которые на него делятся. И продолжайте это, пока список не кончится. Это значительно менее эффективно оригинального алгоритма, а если вас интересуют эффективные методы, см. учебник Кубенского.
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. И потом наоборот. (Подсказка: переворачивание списка мы делали через foldLeft, поэтому его можно использовать во втором случае)
8. Напишите функцию minmax, которая возвращает минимальный и максимальный элемент списка в виде Tuple.

concatMap

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

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

zip, zipWith и unzip

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

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

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

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 поэлементного сложения точек
2. Тип данных “Фигура”
   1. Создайте тип данных Figure, значениями этого типа могут быть круги, для которых известен радиус. Прямоугольник, у которого известно две стороны. Равносторонний треугольник, у которого тоже известна одна сторона.
   2. Реализуйте функцию area :: Figure -> Double, которая вычисляет площадь фигуры
3. На лекции мы самостоятельно ввели тип “список”. Реализуйте для такого списка операции:
   1. Сумма всех элементов списка
   2. Переворачивание списка

Операции с типом “Двоичное дерево”

Заведем тип “двоичное дерево”

    data Tree = Nil | Tree Int Tree Tree

Т.е. каждое дерево может быть либо пустым, либо быть узлом с целым значением и двумя деревьями, левым и правым. См. пример с лекции, там заведено похожее дерево.

Введем определения:

• Дерево поиска - это такое двоичное дерево, в котором элемент в каждой вершине строго больше всех элементов в левом поддереве и строго меньше всех элементов в правом поддереве.

1. Заведите тип Tree', параметризованный другим типом, чтобы дерево могло содержать не только Int значения.
2. Напишите функцию sumTree :: Tree -> Int, которая складывает все значения в дереве.
   • Напишите функцию sumTree', которая принимает на вход дерево Tree' a и складывает все его элементы. Эта функция должна быть определена только если тип a принадлежит классу Num. Правильно опишите тип sumTree'.
3. Создайте функцию линеаризации дерева, т.е. превращения дерева в список: пустое дерево превращается в пустой список. У непустого дерева сначала линеаризуйтся левое поддерево, потом в полученный список добавляется значение из корня дерева, потом в полученный список добавляются значения из линеаризованного правого поддерева.
   • Реализуйте эту же функцию для типа Tree' a
4. Создайте функцию добавления элемента в дерево поиска. Дано дерево поиска и новый Int элемент. Необходимо вернуть новое дерево, в которое этот элемент добавлен. Если такой элемент уже был, то вернуться должно незимененное дерево.
5. Дан список. Добавьте все его элементы по очереди в пустое дерево поиска, потом линеаризуйте дерево. Эта последовательность действий должна возвращать отсортированный список.
6. (*) Дано двоичное дерево, проверьте, является ли оно деревом поиска. Вам придется для каждого дерева не только вычислять, дерево ли это поиска, а еще искать максимальный и минимальный элемент.
7. (*) Реализуйте функцию сворачивания дерева аналогично fold-функциям для списков. Посчитайте сумму всех элементов дерева с помощью этой функции.

Классы типов

1. Запустите из лекции пример с классом типов Reversable, который описывает “переворачиваемые” значения. В этом примере мы описали класс и описали список [] и числа Int как представителей этого класса.
2. Сделайте Point переворачиваемым. При переворачивании переверните также обе координаты.
3. Опишите деревья Tree и Tree' как представителей этого класса. При переворачивании деревьте переворачивайте также значения в вершинах. Вам придется указать, что тип a из определения Tree' тоже переворачиваемый.
4. Реализуйте тип Complex комплексных чисел с координатами типа Double. Опишите ваш комплекс как Num. Проверьте по документации, какой минимальный набор функций необходимо реализовать. Проверьте заодно, что для ваших комплексных чисел работает встроенная функция sum, складывающая все значения в списке.

Тип Maybe

1. Реализуйте функцию safeHead :: [a] -> Maybe a, она должна возвращать голову списка, но учитывать, что головы может не быть.
2. Реализуйте функцию sumList2 :: [a] -> Maybe a, которая возвращает сумму первых двух элементов списка, при этом она должна пользоваться safeHead для получения элементов списка.
3. Если вы уже знаете, что такое монада, реализуйте предыдущую задачу с помощью функци >>= или do-нотации.
4. Реализуйте функцию safeGet :: Int -> [a] -> Maybe a, она должна возвращать элемент списка с указанным индексом.
5. Если вы уже знаете, что такое монада, реализуйте предыдущую задачу с помощью функци >>= или do-нотации.

Ленивые вычисления

1. Реализуйте бесконечный список чисел Фибоначчи. Они начинаются с 1, 1, а каждое следующее число равно сумме двух предыдущих.
2. (*) Множество натуральных чисел определяется следующим образом:
   • множество содержит 1.
   • если множество содержит \(x\), то оно содержит \(2x\), \(3x\) и \(5x\).
   • это минимальное множество с указанными свойствами.

   Реализуйте список элементов этого множества в возрастающем порядке.

   Подсказка. Воспользуйтесь функцией объединения отсортированных списков, которую вы реализовывали для алгоритма сортировки слиянием.

Функторы

1. Реализуйте функцию fmap из класса Functor для типов Tree и Tree’, определенных в предыдущих задачах.