Skip to content

Latest commit

 

History

History
211 lines (153 loc) · 7.42 KB

practice-2020-05-20.md

File metadata and controls

211 lines (153 loc) · 7.42 KB
Raw

Практика 28 мая.

Часть 1: concurrency

Задание 1

Реализуйте race :: IO a -> IO b -> IO (Either a b). Используйте forkIO, throwTo, MVar. Семантика: когда один из тредов завершился, другой убиваем и возвращаем результат (или кидаем exception если тред завершился с exception'ом). Будьте внимательны к обработке асинхронных exception'ов. В результате работы вашей функции не должно оставаться неубитых тредов.

Задание 2

Используйте функцию bracket для того чтобы открыть файл и посчитать кол-во символов x.

Задание 3

Implement parallel Monte-Carlo integral calculation.

Choose function to integrate yourself.

integrate
  :: RandomGen g
  => g -- ^ Random generator
  -> Int -- ^ Number of random points to generate
  -> Double -- ^ Lower bound
  -> Double -- ^ Upper bound
  -> (Double -> Double) -- ^ Function to integrate
  -> Double

In Monte-Carlo method we generate N random points, calculate function value at each point and then calculate mean value multiplied by b - a for b and a being upper and lower bounds respectively.

See https://goo.gl/DkCm6Y.

Задание 4

Account name is represented by String. Account balance is represented by Int.

Ledger is a map from account name to balance, supporting following operations:

  • Get current balance of account A
    • If there is no key A in the map, return 0
  • Transfer c coins from account A to account B
    • If A has balance of less than c coins, throw an exception

Implement a ledger as newtype over Map from http://hackage.haskell.org/package/stm-containers-1.1.0.2/docs/StmContainers-Map.html.

Try to launch 100000 concurrent operations, working on:

  • Same keys
  • Different keys

And roughly compare performance via output of RTS (see slides).

Часть 2: линзы

Задание 5: Базовые линзы

В этом задании запрещается использовать библиотеки с линзами.

Настоящие линзы имеют следующий тип:

type Lens s t a b = forall f . Functor f => (a -> f b) -> s -> f t

Но для простоты мы будем использовать линзы Ван Лаарховена (или же «простые линзы»):

type Lens' s a  = Lens s s a a

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

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 для этого задания.

Можно использовать операторные формы этих функций:

(.~) :: Lens' s a -> a -> s -> s
(^.) :: s -> Lens' s a -> a
(%~) :: Lens' s a -> (a -> a) -> s -> s

Задание 6: Линза для пары

После этого реализуйте простейшие линзы для пары (!!! реализуйте эти функции вручную, запрещается использовать lens из усложнённой версии !!!):

-- _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 = _

Задание 7: lens

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

lens :: (s -> a) -> (s -> b -> t) -> Lens s t a b
lens get set = _

Подсказка: Если реализовать функцию выше тяжело, то попробуйте для начала реализовать более простую версию.

lens :: (s -> a) -> (s -> a -> s) -> Lens' s a
           │              │
           │              └─ setter
           │
           └── getter

Задание 7: choosing

После этого реализуйте линзы, которые сложней, чем _1 и _2:

-- Объединить две линзы в одну, которая работает с 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 = _

Часть 3: forall трюки

Задание 8. ST (но не репер)

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

Тип данных STRef должен соответствовать переменной, существующей в контексте Вашей ST монады.

В реализации можете использоватьTypeable.

В отдельном модуле реализуйте примеры использования.

Данный пример должен компилироваться с Вашим кодом и вычислять i-е число Фибоначчи:

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

Следующий пример также должен компилироваться и вычислять квадратный корень числа с плавающей точкой.

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