# Haskell: ДЗ 2 -- Монады и парсер-комбинаторы

Второе домашнее задание проверяет, насколько хорошо у студентов развито понимание системы типов в Haskell, насколько хорошо они могут использовать типы для создания абстракций и решения проблем. А также проверяется возможность использовать уже существующие и широко используемые абстракции. Само задание помогает понять, как типы могут быть использованы для написания короткого, безопасного и переиспользуемого кода.

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

Тесты должны находиться в директории `test/`, Вы можете без труда найти ее в директории соответствующего пакета предложенного Вам [темплейта](https://github.com/pva701/fp-homework-templates).

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

В качестве вспомогательного материала при выполнении этого ДЗ можно использовать данные [слайды](https://slides.com/fp-ctd/lecture-55)

## Блок 1: Базовые конструкции

### Задание 1

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

В ДЗ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` можно использовать соответствующие инстансы для списка.

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

### Задание 1

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

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

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

eval :: Expr -> Either ArithmeticError Int

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

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

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

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

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

### Задание 2
Реализуйте [Simple Moving Average](https://en.wikipedia.org/wiki/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]

Реализация должна быть эффективной, и работать для листов размером в $10^4$ достаточно быстро (за 2-3 секунды).

### Задание 3
Помимо `Monad`, существуют еще и другие тайпклассы, похожие на `Monad`.
В данном задании от Вас требуется выразить одни через другие.

Пусть есть следующие тайпклассы.

class MonadFish m where
    returnFish :: a -> m a
    (>=>)      :: (a -> m b) -> (b -> m c) -> (a -> m c)

class MonadJoin m where
    returnJoin :: a -> m a
    join       :: m (m a) -> m a

class Monad m where
    (>>=)  :: m a -> (a -> m b) -> m b
    return :: a -> m a

Необходимо реализовать
* `MonadJoin`, имея `MonadFish`
* `Monad`, имея `MonadFish`
* `MonadFish`, имея `Monad`
* `MonadJoin`, имея `Monad`

Все инстансы должны иметь вид

instance MonadA m => MonadB m where
...

Для этого вам понадобится расширения языка `UndecidableInstances` и `FlexibleInstances`.

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

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

* [Parser Combinators: Basics](http://www.seas.upenn.edu/~cis194/spring13/hw/10-applicative.pdf)
* [Parser Combinators: Implementing simple parser](http://www.seas.upenn.edu/~cis194/spring13/hw/11-applicative2.pdf)

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

**Тесты:** в заданиях блока необходимо написать несколько юнит-тестов при помощи `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 можно найти [здесь](https://slides.com/fp-ctd/lecture-55#/29),
а больше информации, как реализовать то что требуется [здесь](https://www.dropbox.com/s/z1e1kxi32zl8kbd/DDToOS.pdf?dl=0).