owned this note
owned this note
Published
Linked with GitHub
# Haskell: ДЗ 2 -- Монады и парсер-комбинаторы
Второе домашнее задание проверяет, насколько хорошо у студентов развито понимание системы типов в Haskell, насколько хорошо они могут использовать типы для создания абстракций и решения проблем. А также проверяется возможность использовать уже существующие и широко используемые абстракции. Само задание помогает понять (как минимум нацелено на то, чтобы это сделать), как типы могут быть использованы для написания короткого, безопасного и переиспользуемого кода.
Тесты в этом блоке нужны не для всех заданий, а где нужны, то должный быть реализованы либо unit-тест при помощи библиотеки `hspec`, либо свойства при помощи `hedgehog`.
В остальных заданиях необходимо вручную показать выполнимость законов или свойств, используя технику _Equational Reasoning_ (далее просто **ER**), когда об этом указано явно. В реальной жизни могут возникнуть нетривиальные ошибки, если реализовать инстансы как-нибудь, не проверяя выполнимость законов. Навык доказательств при помощи пошаговых преобразований -- показательство -- очень полезный и позволяет не только доказывать менее тривиальные свойства, но и лучше понять, как устроены вещи. Доказательства можно написать простым текстом в комментариях или даже на бумажке. Использовать современные модные proof-assistant'ы вроде Agda или Idris необязательно (однако я не запрещаю всем желающим это сделать, если у Вас много времени).
Не переживайте, в каждом задании написано, как его нужно протестировать.
## Блок 1: Монадические вычисления
### Задание 1: Арифметические выражения
Арифметическое выражение (именно выражение, не результат его вычисления) можно представить рекурсивным алгебраическим типом данных. Реализуйте этот тип данных, чтобы с его помощью можно было задавать следующие операции:
* Целочисленные константы
* Сложение двух выражений
* Вычитание выражений
* Произведение выражений
* Деление выражений
* Возведение в степень выражений
После этого напишите функцию, которая принимает выражение и вычисляет его. Обратите внимание на то, что выражение может не получиться вычислить по разным причинам.
```haskell
eval :: Expr -> Either ArithmeticError Int
```
То есть Вы должны создать свой тип данных, который обозначает арифметическую ошибку и возвращать `Either` — либо ошибка, которая возникла, либо результат. Если выражение содержит несколько ошибок, то можно вернуть любую.
Достаточно проверять только на следующие арифметические ошибки:
1. Деленение на 0.
2. Возведение в отрицательную степень.
**Подсказка:** если реализовать функцию с `Either` сразу тяжело, то попробуйте `eval :: Expr -> Maybe Int`, после чего замените `Maybe` на `Either String`, а затем `String` можно будет заменить за свой тип данных.
**Тесты:** Это задание необходимо протестировать при помощи простых unit-тестов.
### Задание 2: Бинарные последовательности
Реализуйте функцию, которая принимает число `n` и генерирует все двоичные последовательности длины `n`.
Используйте инстанс монады для списка и оператор `(>>=)`.
```haskell
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 необходимо было написать функцию, которая суммирует числа в строке. В формулировке задания было допущено серьёзное ослабление, а именно -- данные на вход подаются валидные. В этом задании Вам необходимо реализовать безопасную функцию поиска суммы, а именно:
```haskell=
stringSum :: String -> Maybe Int
```
Если хотя бы один элемент строки нельзя сконвертировать в целое число, то необходиомо вернуть `Nothing`.
**Тесты:** Необходимо написать несколько простых юнит тестов на эту функцию.
#### Усложнённое задание
**Тесты:** Придумать свойства и протестировать с их помощью.
### Задание 2: Maybe? Maybe!
Дан следующий тип данных:
```haskell=
data Optional a = Optional (Maybe (Maybe a))
```
Реализуйте вручную инстансы `Functor`, `Applicative`, `Monad`, `Foldable` и `Traversable` для `Optional`.
**Тесты:** В этом задании вместо тестов нужно доказать законы монад для `Optional`, используя ER.
### Задание 3: Непустые знания о монадах
#### Основное задание
Дан следующий тип данных:
```haskell=
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
Имеется тип простого парсер-комбинатора:
```haskell=
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: Непростой парсер
Написать парсер списка списков чисел, разделённых запятой. Все числа перечисленны через запятую. В начале каждого списка находится число --- длина списка. Таким образом можно понять, где заканчивается каждый список. То есть список
```haskell=
[ [1, 10], [5, -7, 2] ]
```
в строковом виде может быть записан следующим образом:
```haskell=
"2, 1,+10 , 3,5,-7, 2"
```