owned this note
owned this note
Published
Linked with GitHub
# Haskell: ДЗ 1 -- Базовые конструкции языка
Первое домашнее задание проверяет понимание базовых конструкций языка: списки, полиморфизм, паттерн-мэтчинг, алгебраические типы данных, классы типов. А также стандартные функции и интерфейсы. Задания разделены на блоки. Были предприняты некоторые усилия со стороны преподавателей, чтобы блоки соответстовали независимым частям лекций. Некоторые задания имеют усложнённые версии, которые необходимо выполнять **дополнительно к базовой**, но они также будут оценены дополнительными баллами.
Решения заданий необходимо оформить в качестве проекта. Итоговое полностью сделанное домашнее задание необходимо прислать на почту: fp.itmo.ctd@gmail.com
Задания будут проверяться лично. Вам необходимо подготовить тесты к заданиям самостоятельно. Так как это первое ДЗ, то необязательно использовать тестирующие фреймворки для создания тестов (о них будет рассказано позже). Подготовьте тесты самостоятельно хоть как-нибудь, но чтобы их можно было довольно легко запустить и прогнать из ghci. Более детальные требования к ДЗ находятся в табличке с результатами.
## Блок 1: Простые функции (однострочники)
### Задание 1
Упорядочить по возрастанию переданную тройку элементов.
```haskell=
ghci> order3 (5, 2, 10)
(2, 5, 10)
```
### Задание 2
Функция должна повторять каждый элемент столько раз, чему равен сам элемент.
```haskell=
ghci> smartReplicate [1,2,3]
[1,2,2,3,3,3]
```
### Задание 3
Напишите функцию, которой передаётся список списков и некоторый элемент. Эта функция должна вернуть список только тех списков, которые содержат переданный элемент.
```haskell=
ghci> contains 3 [[1..5], [2,0], [3,4]]
[[1,2,3,4,5],[3,4]]
```
### Задание 4
Требуется написать функцию, которая принимает строку, состоящую только из чисел, разделённых пробельными символами, и находит сумму всех чисел в этой строке. Тип функции должен быть `String -> Int`. В данном задании нужно считать, что переданная строка корректная.
```haskell
ghci> stringSum "1 1"
2
ghci> stringSum "100\n\t-3"
97
```
Больше тестов ниже:
```haskell
passTests = [ "1", "1 2 3", " 1", "1 ", "\t1\t", "\t12345\t", "010 020 030"
, " 123 456 789 ", "-1", "-1 -2 -3", "\t-12345\t", " -123 -456 -789 "
, "\n1\t\n3 555 -1\n\n\n-5", "123\t\n\t\n\t\n321 -4 -40"
]
mustFail = ["asd", "1-1", "1.2", "--2", "+1", "1+"]
```
## Блок 2: Паттерн-мэтчинг на списках
### Задание 1
Реализовать функцию, которая удаляет элемент по заданному индексу и возвращает удалённый элемент. Подумайте над тем, как отразить такое поведение в типе функции наиболее полно.
### Задание 2
Требуется реализовать сортировку слиянием:
```haskell
ghci> mergeSort [2, 1, 0, 3, 10, 5]
[0, 1, 2, 3, 5, 10]
```
Поместите следующий код в начале вашего модуля
```haskell
import System.Random (newStdGen, randomRs)
randomIntList :: Int -> Int -> Int -> IO [Int]
randomIntList n from to = take n . randomRs (from, to) <$> newStdGen
```
чтобы тестировать вашу функцию в ghci следующим образом
```haskell
ghci> example <- randomIntList 5 (-10) 10
ghci> example
[-8,1,-8,-5,-7]
ghci> mergeSort example
[-8,-8,-7,-5,1]
```
Для этого необходимо в зависимости добавить библиотеку `random`.
## Блок 3: Добро пожаловать в фантастический мир алгебраических типов данных
### Задание 1: Дни недели
Вы проектируете собственный фантастический мир. Эта задача не из лёгких. Для начала Вы решаете ввести время в ваш собственный мир, используя привычные дни недели.
Определите свой тип данных для _Дней недели_. Реализуйте следующие функции:
1. `nextDay`: возвращает следующий за переданным день недели.
2. `afterDays`: возвращает день недели, который наступит после заданного через переданное число дней.
3. `isWeekend`: проверяет, является ли день недели выходным.
4. `daysToParty`: выводит число дней, оставшихся до пятницы.
### Задание 2: Проектирование замков
#### Основное задание
Преждем чем населить мир обитателями, Вы принимаете решение создать города в Вашем мире, потому что Вам всегда нравилось играть в Civilization. Необходимо определить типы данных для представления города:
1. В городе может быть замок (а может и не быть).
2. В городе может быть либо церковь, либо библиотека, а может не быть ничего, но не может быть двух эти зданий одновременно.
3. В городе может быть несколько жилых домов, но должен быть как минимум один.
4. В замке может сидеть лорд, а может и не сидеть.
5. У города могут быть стены, но только тогда, когда в городе есть замок!
6. В каждом жилом доме может жить от одного до четырёх человек.
Определите тип данных для города таким образом, чтобы в Вашем мире нельзя было в принципе создать города, не удовлетворяющие этому условию. После этого поддержите следующие функции по развитию городов:
1. Построить замок, но только если в городе нет замка. Должна быть возможность понять, был ли построен новый замок в результате выполнения этой операции.
2. Построить церковь или библиотеку, но только если в городе нет ничего из этого! Требования аналогично предыдущей функции.
3. Постройка для новой семьи нового жилого дома, в который они въедут.
4. Возможность лорду въехать в замок, но только если в городе есть замок, в котором нет лорда. Если лорд не смог въехать в замок, то необходимо сообщить, по какой именно причине он не смог это сделать.
5. Построить стены в городе. Это очень сложное занятие, поэтому построить стены можно лишь тогда, когда в городе минимум 10 человек и есть лорд.
### Задание 3: Натуральные числа
Чтобы экономика в городах могла развиваться, необходимо ввести в мир деньги, назначить цены за товары и услуги.
#### Базовое задание
Но сначала необходимо ввести некоторые операции по работе с натуральными числами, в которых будут выражаться деньги. Напомню, что натуральным числом является либо `0`, либо какое-то натуральное число, увеличенное на `1`. Этот тип данных представляется следующим образом:
```haskell
data Nat = Z | S Nat
```
Реализуйте следующие операции (которые должны быть реализованы полностью самостоятельно):
1. Сложение двух натуральных чисел.
2. Умножение двух натуральных чисел.
3. Вычитание натуральных чисел.
4. Превращение целых чисел в натуральные и наоборот.
5. Проверка натуральных чисел на равенство.
6. Сравнение натуральных чисел.
То есть необходимо реализовать инстансы `Eq`, `Ord`, `Num` для типа данных `Nat` **не** через `deriving`.
#### Усложнённая версия
Дополнительно требуется реализовать следующие функции:
7. Проверка натурального числа на чётность.
8. Целочисленное деление натуральных чисел.
9. Остаток от деления натурального числа на другое.
### Задание 4: Растительность
Чтобы сделать Ваш мир более красочным и живописным, Вы решаете добавить в него растительность. Так как Вы программист, то единственный вид растительности, который Вам известен -- двоичные деревья поиска.
Дерево имеет два конструктора:
1. Лист дерева, не содержит данных.
2. Узел дерева. Содержит список одинаковых значений и имеет двух детей.
При этом _двоичное дерево_ называется _двоичным деревом поиска_ если оно удовлетворяет следующему условию: значения всех элементов в левом поддереве меньше значения в узле, а значения элементов в правом поддереве больше значения в узле.
Реализуйте следующие операции с _двоичным деревом поиска_:
1. Проверка дерева на пустоту.
2. Подсчёт размера дерева (то есть числа элементов в нём).
3. Поиск заданного элемента в дереве (используйте тот факт, что дерево является деревом поиска).
4. Вставка нового элемента в _двоичное дерево поиска_. Если вставляемый элемент уже находится в дереве, то необходимо добавить его в список того узла, в котором этот элемент находится. Тут следует обратить внимание, что если в узле дерева есть список элементов, то этот список всегда непустой.
5. Функцию `fromList`, которая создаёт дерево из списка элементов.
6. Функцию, которая удаляет заданный элемент из дерева.
## Блок 4: Сворачиваемся
### Задание 1: Инстансы Foldable
В этом задании **обязательно** использовать расширение языка `-XInstanceSigs` и указывать типы функций в инстансах. При этом необходимо реализовать обе функции `foldMap` и `foldr`.
#### Основное задание
Реализуйте вручную инстансы `Foldable` для следующих типов данных:
1. `data Pair a = Pair a a`
2. `data NonEmpty a = a :| [a]`
#### Усложнённое задание
Прошло много времени, как Вы создали собственный мир... В исходном коде вашего мира появилось много типов данных и абстракций. Пришло время порефакторить предыдущий код. Для этого необходимо сделать тип данных `Tree` инстансом класса типов `Foldable`. Инстанс должен быть реализован таким образом, чтобы выполнялось свойство: `toList . fromList ≡ sort`.
### Задание 2: Разбиваемся
#### Базовая версия
Используя свёртку, реализуйте функцию `splitOn`, которая разбивает список на подсписки по элементу.
```haskell
ghci> splitOn '/' "path/to/file"
["path", "to", "file"]
```
Стоит обратить внимание, что функция `splitOn` всегда возвращает непустой список элементов. Это должно быть отражено в типе. Пример приведён для обычного списка, хотя это решение не полностью корректное.
#### Усложнённая версия
Дополнительно реализуйте функцию (опять же, используя свёртку) `joinWith`, обратную `splitOn`. При этом Ваши реализации должны удовлетворять свойству:
`joinWith x . splitOn x ≡ id`.
```haskell
ghci> joinWith '/' ["path", "to", "file"]
"path/to/file"
```
Стоит обратить внимание на то, что функция `joinWith` принимает непустой список.
## Блок 5: Моноиды
### Задание 1
#### Базовая версия
Напишите функцию, принимающую список списков внутри `Maybe` и возвращающую конкатенацию всех внутренних списков.
```haskell
ghci> maybeConcat [Just [1,2,3], Nothing, Just [4,5]]
[1,2,3,4,5]
```
#### Усложнённая версия
Функция должна принимать произвольный набор `Either`, где и `Left` и `Right` содержат некоторые моноидальные элементы, и необходимо вернуть пару из результатов моноидального объединения отдельно элементов внутри `Left` и отдельно элементов внутри `Right`.
```haskell
ghci> eitherConcat [Left (Sum 3), Right [1,2,3], Left (Sum 5), Right [4,5]]
(Sum {getSum = 8}, [1,2,3,4,5])
```
### Задание 2
#### Базовая версия
Реализуйте инстансы алгебраических классов типов для следующих структур данных. Ваши инстансы должны удовлетворять законам для этих структур.
1. `Semigroup` для `data NonEmpty a = a :| [a]`.
2. `Semigroup` для типа данных `data ThisOrThat a b = This a | That b | Both a b`.
#### Усложнённая версия
Дополнительно реализуйте следующие инстансы:
1. `Semigroup` и `Monoid` для строк, объединяемых при помощи `'.'`.
```haskell
ghci> Name "root" <> Name "server"
Name "root.server"
```
2. `Semigroup` и `Monoid` для `newtype Endo a = Endo { getEndo :: a -> a }`.
### Задание 3
Имеется следующий тип данных `Builder` для создания строк:
```haskell
data Builder = One Char | Many [Builder]
```
Реализуйте инстансы классов типов `Semigroup` и `Monoid` для типа `Builder`. Реализуйте функцию создания билдера из строки:
```haskell
fromString :: String -> Builder
```
Реализуйте функцию построения строки из билдера:
```haskell
toString :: Builder -> String
```
Подумайте над тем, как можно реализовать этот тип данных более эффективно и предложите способы оптимизаций.