hw1

hw1 -- Базовые конструкции языка и не только

Первое домашнее задание проверяет понимание базовых конструкций языка. А также стандартные функции и интерфейсы. Обратите внимание, что задание соответствует материалу, который рассказан в темах со 2 по 5ю отсюда.

В качестве вспомогательного материала про парсер-комбинаторы и тестирование при выполнении этого ДЗ рекомендуется использовать данные слайды

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

В данном домашнем задании от Вас требуется познакомиться с некоторыми библиотеками для тестирования и реализовать тесты с помощью них.

Тесты должны находиться в директории test/

Тесты должны запускаться командной stack test.

В заданиях явно указано, какие тесты для них должны быть реализованы.

Срок сдачи

00:00 (UTC+3) 27 Марта 2020.

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

В этом блоке разрешено использовать автоматический deriving только для Show. Остальные инстансы необходимо реализовывать самостоятельно.

Задание 1: Дни недели

Тесты: Это задание необходимо протестировать при помощи простых unit-тестов.

Определите свой тип данных для Дней недели. Реализуйте следующие функции:

1. nextDay: возвращает следующий за переданным день недели.
2. afterDays: возвращает день недели, который наступит после заданного через переданное число дней.
3. isWeekend: проверяет, является ли день недели выходным.
4. daysToParty: выводит число дней, оставшихся до пятницы.

Задание 2: Натуральные числа

Тесты: Это задание необходимо протестировать при помощи простых unit-тестов. Property-based тесты по желанию (оцениваются дополнительными баллами).

Базовое задание

Этот тип данных для натуральных чисел определяется следующим образом:

data Nat = Z | S Nat

Реализуйте следующие операции (которые должны быть реализованы полностью самостоятельно):

1. Сложение двух натуральных чисел.
2. Умножение двух натуральных чисел.
3. Вычитание натуральных чисел.
4. Превращение целых чисел в натуральные и наоборот.
5. Проверка натуральных чисел на равенство.
6. Сравнение натуральных чисел.

Усложнённая версия

Дополнительно требуется реализовать следующие функции:

7. Проверка натурального числа на чётность.
8. Целочисленное деление натуральных чисел.
9. Остаток от деления натурального числа на другое.

Задание 3: Растительность

Тесты: Это задание необходимо протестировать при помощи простых unit-тестов.

Тип данных для двоичного дерева имеет два конструктора:

1. Лист дерева, не содержит данных.
2. Узел дерева. Содержит непустой список одинаковых значений и имеет двух детей.

Двоичное дерево называется двоичным деревом поиска если оно удовлетворяет следующему условию: значения всех элементов в левом поддереве меньше значения в узле, а значения элементов в правом поддереве больше значения в узле.

Реализуйте следующие операции с двоичным деревом поиска:

1. Проверка дерева на пустоту.
2. Подсчёт размера дерева (то есть числа элементов в нём).
3. Поиск заданного элемента в дереве (используйте тот факт, что дерево является деревом поиска).
4. Вставка нового элемента в двоичное дерево поиска. Если вставляемый элемент уже находится в дереве, то необходимо добавить его в список того узла, в котором этот элемент находится. Тут следует обратить внимание, что если в узле дерева есть список элементов, то этот список всегда непустой.
5. Функцию fromList, которая создаёт дерево из списка элементов.
6. Функцию, которая удаляет заданный элемент из дерева.

Блок 2: Сворачиваемся

Задание 1: Инстанс Foldable для Tree

Тесты: Это задание необходимо протестировать при помощи Property-based тестов.

В этом задании обязательно использовать расширение языка -XInstanceSigs и указывать типы функций в инстансах. При этом необходимо реализовать обе функции foldMap и foldr.

Реализуйте инстанс Foldable для типа Tree. Инстанс должен быть реализован таким образом, чтобы выполнялось свойство: toList . fromList ≡ sort.

Задание 2: Разбиваемся

Тесты: Это задание необходимо протестировать при помощи простых unit-тестов. Property-based тесты по желанию (оцениваются дополнительными баллами).

Базовая версия

Используя свёртку, реализуйте функцию splitOn, которая разбивает список на подсписки по элементу.

ghci> splitOn '/' "path/to/file"
["path", "to", "file"]

Стоит обратить внимание, что функция splitOn всегда возвращает непустой список элементов. Это должно быть отражено в типе. Пример приведён для обычного списка, хотя это решение не полностью корректное.

Усложнённая версия

Дополнительно реализуйте функцию (опять же, используя свёртку) joinWith, обратную splitOn. При этом Ваши реализации должны удовлетворять свойству:

joinWith x . splitOn x ≡ id.

ghci> joinWith '/' ["path", "to", "file"]
"path/to/file"

Стоит обратить внимание на то, что функция joinWith принимает непустой список.

Блок 3: Моноиды

Задание 1

Тесты: Это задание необходимо протестировать при помощи простых unit-тестов.

Базовая версия

Напишите функцию, принимающую список списков внутри Maybe и возвращающую конкатенацию всех внутренних списков.

ghci> maybeConcat [Just [1,2,3], Nothing, Just [4,5]]
[1,2,3,4,5]

Усложнённая версия

Функция должна принимать произвольный набор Either, где и Left и Right содержат некоторые моноидальные элементы, и необходимо вернуть пару из результатов моноидального объединения отдельно элементов внутри Left и отдельно элементов внутри Right.

ghci> eitherConcat [Left (Sum 3), Right [1,2,3], Left (Sum 5), Right [4,5]]
(Sum {getSum = 8}, [1,2,3,4,5])

Задание 2

Тесты: Это задание необходимо протестировать при помощи простых unit-тестов.

Базовая версия

Реализуйте инстансы алгебраических классов типов для следующих структур данных. Ваши инстансы должны удовлетворять законам для этих структур.

1. Semigroup для data NonEmpty a = a :| [a].
2. Semigroup для типа данных data ThisOrThat a b = This a | That b | Both a b.

Усложнённая версия

Дополнительно реализуйте следующие инстансы:

1. Semigroup и Monoid для строк, объединяемых при помощи '.'.

ghci> Name "root" <> Name "server"
Name "root.server"

2. Semigroup и Monoid для newtype Endo a = Endo { getEndo :: a -> a }.

Блок 4: Functor и его друзья

Задание 1

Тесты: Это задание необходимо протестировать при помощи простых unit-тестов.

Основное задание

В ДЗ1 необходимо было написать функцию, которая суммирует числа в строке. В формулировке задания было допущено серьёзное ослабление, а именно -- данные на вход подаются валидные. В этом задании Вам необходимо реализовать безопасную функцию поиска суммы, а именно:

stringSum :: String -> Maybe Int

Числа в строке разделены одним или несколькими пробельными символами. Если хотя бы один элемент строки нельзя сконвертировать в целое число, то необходиомо вернуть Nothing.

Функция должна использовать инстанс Traversable для листа.

Усложненное задание

Необходимо написать несколько простых юнит тестов на эту функцию.

Задание 2

Дан следующий тип данных:

data Tree a
  = Branch (Tree a) (Tree a)
  | Leaf a

Реализуйте вручную инстансы Functor, Applicative, Foldable и Traversable для Tree.

Должны выполняться законы этих тайпклассов.

Задание 3:

Дан следующий тип данных:

data NonEmpty a = a :| [a]

Реализуйте вручную инстансы Functor, Applicative, Monad, Foldable и Traversable для NonEmpty.

Во время реализации инстансов для NonEmpty можно использовать соответствующие инстансы для списка.

Блок 5: Монады и монадические вычисления

Задание 1

Тесты: Это задание необходимо протестировать при помощи простых unit-тестов.

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

• Целочисленные константы
• Сложение двух выражений
• Вычитание выражений
• Произведение выражений
• Деление выражений
• Возведение в степень выражений

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

eval :: Expr -> Either ArithmeticError Int

То есть Вы должны создать свой тип данных, который обозначает арифметическую ошибку и возвращать Either — либо ошибка, которая возникла, либо результат. Если выражение содержит несколько ошибок, то можно вернуть любую.

Достаточно проверять только на следующие арифметические ошибки:

1. Деленение на 0.
2. Возведение в отрицательную степень.

Подсказка: если реализовать функцию с Either сразу тяжело, то попробуйте eval :: Expr -> Maybe Int, после чего замените Maybe на Either String, а затем String можно будет заменить за свой тип данных.

Задание 2

Реализуйте Simple Moving Average алгоритм, используя State монаду.

ghci> moving 4 [1, 5, 3, 8, 7, 9, 6]
[1.0, 3.0, 3.0, 4.25, 5.75, 6.75, 7.5]

ghci> moving 2 [1, 5, 3, 8, 7, 9, 6]
[1.0, 3.0, 4.0, 5.5, 7.5, 8.0, 7.5]

Блок 6: Парсер-комбинаторы

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

• Parser Combinators: Basics
• Parser Combinators: Implementing simple parser

Основная часть упражнений оттуда всё равно является частью этого домашнего задания.

Тесты: в заданиях этого блока необходимо написать несколько юнит-тестов при помощи hspec. Property-based тесты по желанию.

Задание 1: Copy-paste

Имеется тип простого парсер-комбинатора:

data Parser s a = Parser { runParser :: [s] -> Maybe (a, [s]) }

В отличие от парсера предложенного на практике, он может работать не только со строкой, но и с любым потоком данных. Реализуйте вручную инстансы Functor, Applicative, Monad и Alternative для этого парсера.

Задание 2: Базовые комбинаторы

Реализуйте следующие базовые комбинаторы:

1. ok --- парсер никогда не падает и не поглащает инпут.
2. eof --- проверяет, что парсер дошёл до конца потока данных (иначе падает).
3. satisfy --- парсер принимает предикат на элемент потока, и возвращает элемент, поглащая его из потока, если предикат на элемент равен True, иначе падает.
4. element и stream --- парсят один или несколько элементов потока (как char и string).

Задание 3: Простые парсеры

Используя существующие комбинаторы (реализовав по необходимости остальные) напишите следующие парсеры строковых потоков:

1. Парсер правильных скобочных последовательностей (падает, если последовательность неправильная, и не падает, если правильная).
2. Парсер целого числа, перед которым может быть знак + или -.

Задание 4: Непростой парсер

Написать парсер списка списков чисел, разделённых запятой. Парсер должен иметь тип:

listlistParser :: Parser Char [[Int]]

Все числа перечисленны через запятую. В начале каждого списка находится число --- длина списка. Таким образом можно понять, где заканчивается каждый список. То есть список

[ [1, 10], [5, -7, 2] ]

в строковом виде может быть записан следующим образом:

"2, 1,+10  , 3,5,-7, 2"

Бонусное задание

Данное задание направлено на изучение монады Cont

newtype Cont r a = Cont { runCont :: (a -> r) -> r }

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

В данном задании от Вас требуется разобраться или реализовать самостоятельно инстансы Functor, Applicative, и Monad для Cont.

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

А именно, необходимо поддержать read, write, exit, yield, fork.

Должна иметься возможность написать следующий код:

main' = do
  x <- readLine
  let str = "Hello, " ++ show x ++ "!" in
  writeLine str
  exit Success

Требуется также реализовать функцию kernel, которая будет интерпретировать данный код.

Информацию о монаде Cont можно найти здесь, а больше информации, как реализовать то что требуется здесь.