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

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

Тесты в этом блоке нужны не для всех заданий, а где нужны, то должный быть реализованы либо unit-тест при помощи библиотеки `hspec`, либо свойства при помощи `hedgehog`.

В остальных заданиях необходимо вручную показать выполнимость законов или свойств, используя технику _Equational Reasoning_ (далее просто **ER**), когда об этом указано явно. В реальной жизни могут возникнуть нетривиальные ошибки, если реализовать инстансы как-нибудь, не проверяя выполнимость законов. Навык доказательств при помощи пошаговых преобразований -- показательство -- очень полезный и позволяет не только доказывать менее тривиальные свойства, но и лучше понять, как устроены вещи. Доказательства можно написать простым текстом в комментариях или даже на бумажке. Использовать современные модные proof-assistant'ы вроде Agda или Idris необязательно (однако я не запрещаю всем желающим это сделать, если у Вас много времени).

Не переживайте, в каждом задании написано, как его нужно протестировать.

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

### Задание 1: Арифметические выражения

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

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

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

eval :: Expr -> Either ArithmeticError Int

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

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

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

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

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

### Задание 2: Бинарные последовательности

Реализуйте функцию, которая принимает число `n` и генерирует все двоичные последовательности длины `n`.

Используйте инстанс монады для списка и оператор `(>>=)`.

ghci> bin 1
[ [ 0 ] , [ 1 ] ]
ghci> bin 2
[ [ 0 , 0 ] , [ 1 , 0 ] , [ 0 , 1 ] , [ 1 , 1 ] ]
ghci> bin 3
[ [ 0 , 0 , 0 ]
, [ 1 , 0 , 0 ]
, [ 0 , 1 , 0 ]
, [ 1 , 1 , 0 ]
, [ 0 , 0 , 1 ]
, [ 1 , 0 , 1 ]
, [ 0 , 1 , 1 ]
, [ 1 , 1 , 1 ]
]

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

## Блок 2: Иерархия типов

### Задание 1: Safe string sum

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

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

stringSum :: String -> Maybe Int

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

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

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

**Тесты:** Придумать свойства и протестировать с их помощью.

### Задание 2: Maybe? Maybe!

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

data Optional a = Optional (Maybe (Maybe a))

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

**Тесты:** В этом задании вместо тестов нужно доказать законы монад для `Optional`, используя ER.

### Задание 3: Непустые знания о монадах

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

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

data NonEmpty a = a :| [a]

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

Во время реализации инстансов для `NonEmpty` необходимо реализовать все вспомогательные функции самостоятельно.

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

**Тесты:** В этом задании необходимо доказать законы монад для `NonEmpty`, используя библиотеку `hedgehog` и технику property-based тестирование.

## Блок 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: Непростой парсер

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

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

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

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