# Haskell: ДЗ 5 – Продвинутые типы и линзы
## Продвинутые типы
### Задание 1. ST (но не репер)
Реализуйте свой аналог `ST` монады, поддерживающий значения произвольного типа.
Код должен содержаться в отдельном модуле, модуль не должен экспортировать ничего что может позволить сломать инварианты ST монады.
Тип данных `STRef` должен соответствовать переменной, существующей в контексте Вашей `ST` монады.
В реализации можете использовать`Typeable`.
В отдельном модуле реализуйте примеры использования.
Данный пример должен компилироваться с Вашим кодом и вычислять i-е число Фибоначчи:
```haskell
fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib i = runST $ do
s <- newSTRef 0
t <- newSTRef 1
forM_ [2..i] $ \_ -> do
_s <- readSTRef s
_t <- readSTRef t
writeSTRef s _t
writeSTRef t (_s + _t)
readSTRef t
```
Следующий пример также должен компилироваться и вычислять квадратный корень числа с плавающей точкой.
```haskell
eps :: Double
eps = 1.0e-15
whileM :: Monad m => m Bool -> m () -> m ()
whileM c act =
c >>= \b ->
if b
then act >> whileM c act
else pure ()
sqrt' :: Double -> Double
sqrt' x
| x < 1 = error "x < 1 not supported"
| x == 0 = 0
| otherwise = runST $ do
l <- newSTRef 0
r <- newSTRef x
let checkCond = do
l_ <- readSTRef l
r_ <- readSTRef r
pure (r_ - l_ > eps)
whileM checkCond $ do
l_ <- readSTRef l -- l^2 < x
r_ <- readSTRef r -- r^2 >= x
let m = (l_ + r_) / 2
if (m * m >= x)
then writeSTRef r m
else writeSTRef l m
readSTRef r
```
### Задание 2. HalyavaScript
В данном задании от Вас потребуется реализовать новый язык программирования, который назовём HalyavaScript.
HalyavaScript -- статически типизируемый язык программирования, повторяющий основные конструкции языка JavaScript.
Реализовать HalyavaScript требуется в виде eDSL на Haskell, таким
образом получая type inference и parsing из коробки.
HalyavaScript поддерживает следующие типы:
* `Int32` (конвертируется в `Number`)
* `Double` (конвертируется в `Number`)
* `String`
* `Boolean`
* Функции от одного и двух агрументов
Конкретный синтаксис Вам предлагается разработать самим.
Для вдохновения можно использовать пример ниже:
```haskell
-- | For a given @x@ calculates @ceiling (log2 (a))@
log2 =
sFun1 $ \a logCnt ->
sWithVar 0 $ \accum ->
accum @= 1 #
logCnt @= 0 #
sWhile (a @> eRead accum)
( accum @= eRead accum + eRead accum #
logCnt @= eRead logCnt + 1
)
```
Обратите внимание, что у данной функции специально отсутвует сигнатура типа, чтобы Вы имели возможность придумать все типы сами.
Для реализации можете использовать GADT, tagless final, Free монады и другие продвинутые подходы языка.
Реализуйте интерпретатор Вашего языка, который будет интерпретировать код написанный на HalyavaScript.
К реализации должен быть приложен простой пример программы, в котором задействованы типы `Int` и `String`.
### Задание 3. HalyavaScript to JavaScript
Реализуйте еще один интерпретатор, который будет конвертировать код на HalyavaScript в строковое представление.
Например, код из предыдущего задания должен выглядеть как-то так. Необязательно точь-в-точь так же.
```javascript
function(v0){
var v1=0;
var v2=0;
v2=1;
v1=0;
while ((v0) > (v2)) {
v2=(v2) + (v2);
v1=(v1) + (1);
}
return v1
}
```
Напишите несколько unit-тестов, которые конвертируют код в строку и сравнивают ее с ожидаемым результатом.
### Задание 4. Погружение в HalyavaScript
Реализуйте 3 математические функции на HalyavaScript. Они должны использовать как `Int`, так и `Double`.
Математические функции можете писать какие хотите, но плюсом будет если они будут отличны от стандартных примеров вроде
факториала и чисел Фибоначчи.
Для каждой функции реализуйте QuickCheck тест, который тестирует соответствие результатов интерпретации программ на HalyavaScript выводу канонических реализаций тех же математических функций на стандартном хаскеле.
## Линзы
Данный блок заданий посвящён линзам. В начале блока предлагается реализовать базовые операции по работе с линзами, чтобы лучше понимать, как устроена библиотека. А затем идут задания на использование линз, чтобы научиться пользоваться этим мощным инструментом.
### Задание 5: Базовые линзы
В этом задании запрещается использовать библиотеки с линзами.
Настоящие линзы имеют следующий тип:
```haskell=
type Lens s t a b = forall f . Functor f => (a -> f b) -> s -> f t
```
Но для простоты мы будем использовать линзы Ван Лаарховена (или же «простые линзы»):
```haskell=
type Lens' s a = Lens s s a a
```
Реализуйте следующие базовые примитивы по работе с линзами:
```haskell
set :: Lens' s a -> a -> s -> s -- set value (setter)
view :: Lens' s a -> s -> a -- lookup value (getter)
over :: Lens' s a -> (a -> a) -> s -> s -- change value (modifier)
```
**_Подсказка_:** используйте функторы `Const` и `Identity` для этого задания.
Можно использовать операторные формы этих функций:
```haskell
(.~) :: Lens' s a -> a -> s -> s
(^.) :: s -> Lens' s a -> a
(%~) :: Lens' s a -> (a -> a) -> s -> s
```
После этого реализуйте простейшие линзы для пары (!!! реализуйте эти функции вручную, запрещается использовать `lens` из усложнённой версии !!!):
```haskell=
-- _1 :: Functor f => (a -> f b) -> (a, x) -> f (b, x)
_1 :: Lens (a, x) (b, x) a b
_1 = _
-- _2 :: Functor f => (a -> f b) -> (x, a) -> f (x, b)
_2 :: Lens (x, a) (x, b) a b
_2 = _
```
Напишите юнит-тесты, которые проверяют, что ваши линзы `_1` и `_2` работают как ожидается вместе с функциями `set`, `view`, `over`.
Линза представляет собой по сути пару из геттера и сеттера. Следовательно, прежде чем использовать линзу, необходимо научиться создавать её. Для этого реализуйте следующую функцию:
```haskell
lens :: (s -> a) -> (s -> b -> t) -> Lens s t a b
lens get set = _
```
**Подсказка:** Если реализовать функцию выше тяжело, то попробуйте для начала реализовать более простую версию.
```haskell=
lens :: (s -> a) -> (s -> a -> s) -> Lens' s a
│ │
│ └─ setter
│
└── getter
```
После этого реализуйте линзы, которые сложней, чем `_1` и `_2`:
```haskell
-- Объединить две линзы в одну, которая работает с Either.
choosing :: Lens s1 t1 a b
-> Lens s2 t2 a b
-> Lens (Either s1 s2) (Either t1 t2) a b
choosing l1 l2 = _
-- Изменить цель линзы и вернуть новый результат. Постарайтесь
-- реализовать без анонимных функций и определений своих функций
(<%~) :: Lens s t a b -> (a -> b) -> s -> (b, t)
(<%~) l f s = _
-- Изменить цель линзы, но вернуть старый результат.
(<<%~) :: Lens s t a b -> (a -> b) -> s -> (a, t)
(<<%~) l f s = _
```
### Задание 6: FileSystem lenses
Начиная с этого задания разрешается использовать пакет `microlens`.
Задан тип данных, которым можно представить простое дерево файловой системы:
```haskell
data FS
= Dir
{ name :: FilePath -- название папки, не полный путь
, contents :: [FS]
}
| File
{ name :: FilePath -- название файла, не полный путь
}
```
Создайте функцию, которая «сканирует» заданную директорию и создаёт объект типа `FS` наподобие функции [`getDirectory'`](https://hackage.haskell.org/package/filesystem-trees-0.1.0.6/docs/System-File-Tree.html#v:getDirectory-39-).
После этого создайте базовые линзы и призмы Вашего типа данных.
### Практика на линзы
> Блок практики не оценивается баллами. Он лишь предоставляет набор команд, которые полезно научиться реализовывать в одну строку при помощи линз, прежде чем приступать к дальнейшим заданиям. Все команды в списке очень простые, но если Вы не можете выполнить и их, значит, Вы не до конца разобрались с линзами, и выполнять дальнейшие задания ещё рано.
1. Список поддеревьев папки для `Dir`, иначе пустой список.
2. `Maybe` с именем директории, если `Dir`, или `Nothing` иначе.
3. Имя файла, если `File`, или пустую строку иначе.
4. Изменить имя корня дерева на `/`.
5. Добавить произвольный суффикс к имени корня дерева.
6. Получить имя самой первой папки в списке поддиректорий (`Nothing`, если такой нет).
7. Получить список имён только `File` из `Dir` (нерекурсивно).
### Задание 7: Обходы FS
Реализуйте следующие `Lens` или `Traversal`:
1. `cd`: перейти в поддиректорию с указанным именем.
2. `ls`: получить список имён содержимого директории.
3. `file`: получить имя конкретного `File`, если он существует.
В итоге должна быть возможность делать нечто похожее:
```haskell
myDir ^? cd "A" . cd "B" . file "C" -- Just "C" при существовании myDir/A/B/C
myDir ^.. cd "A" . cd "B" . ls -- получить содержимое myDir/A/B/
```
### Задание 8: Изменения структуры FS
#### Базовая версия
Реализуйте следующие функции, используя линзы:
1. Изменить в директории расширения всех файлов на другое (нерекурсивно).
2. Получить имена всех файлов и директорий рекурсивно.
3. Удалить выбранную поддиректорию, только если она пустая.
#### Усложнённое задание
4. Получить полный путь к файлу с названием файла относительно стартового узла `FS`.
Интерфейс должен быть следующим:
```haskell=
ghci> myDir ^? move "A" . move "B" . getPath -- myDir is labeled by 'root'
Just "root/A/B/"
```
Разумеется, что все действия происходят над Вашей структурой данных, а в вашей файловой системе ничего не меняется.
Sign in with Wallet
Connect another wallet