questions.org

Вопросы по темам

[5/5]Question 1: Intro

Перечислите основные парадигмы ФП и Haskell, отличительные особенности

1. FP:
   1. Иммутабельность
   2. Чистота
   3. Статическая типизация и вывод типов
   4. Функции высшего порядка
2. Haskell:
   1. Ленивые вычисления
   2. Pattern matching
   3. Type classes

Укажите преимущества чистоты

1. Есть referential transparency ⇒ есть бОльшие возможности для оптимизации
2. Проще делить программу на независимые модули и отлаживать их по отдельности (≈ один модуль - одна функция)
3. Чистые фукнции проще объединять в композиции, так как между ними нет неявных связей в виде изменяемого состояния
4. Чисто функциональные программы проще сделать параллельными

Укажите преимущества ленивых вычислений

1. Можно присваивать значения в любом порядке, так как при ленивых вычислениях вычисление значения произойдет только при его использовании
2. Можно использовать бесконечные структуры данных
3. Ленивый язык более выразительный, чем строгий
4. Иногда можно улучшить эффективность использования памяти при ленивых вычислениях.

Укажите преимущества иммутабельности

1. Нет проблемы нелокальности: изменение по одной ссылке не приведет к изменениям по остальным ссылкам, так как “изменяющая” функция вернет новый объект
2. Нет необходимости в копировании объектов
3. Инварианты достаточно проверять только при создании объекта
4. Нет зависимости от истории ⇒ нет зависимости от порядка вызова методов
5. Безопасное хранение объекта в коллекции
6. Не требуется синхронизация, так как все потоки только читают данные

Укажите преимущества статической типизации

1. Раннее обнаружение ошибок :: Ошибки находятся на этапе компиляции, а не выполнения. Часто программа на SML или Haskell работает правильно, как только ее наконец удается скомпилировать
2. Высокая поддерживаемость больших проектов :: Изменения могут быть верифицированы компилятором, и типы являются частью документации программы, облегчая ее понимание
3. Автоматизированная обработка программ :: Например, автоматический рефакторинг, как в средах IDEA или Eclipse
4. Оптимизация кода :: Код, написанный на статически типизированном языке, проще оптимизировать, так что в среднем статически типизированный язык эффективнее динамически типизированных

[16/19]Question 2: Basic Syntax

Имеется класс типов: class C a where maxInt :: Int. Реализуйте данный класс типов для какого-нибудь типа данных.

Имеется класс типов: class C a where intGetter :: a -> Int. Реализуйте данный класс типов для какого-нибудь типа данных.

data MyBool = MyBool Bool
instance C MyBool where
  intGetter (MyBool True) = 1
  intGetter _ = 0

Как обновить f в data A = A { f :: Int -> Int };?

cc = c {f = (+42)}

Что дает слово ”deriving”? Что это в языке Haskell?

deriving позволяет неявно определять функции стандартных typeclass‘ов. Детали такой неявной реализации иногда зависят от компилятора.

Напишите реализацию foldr и foldl. И нарисуйте картинку вычисления

foldr:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr _ z []     = z
foldr f z (x:xs) = x `f` (foldr f z xs)

foldl:

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl _ z []     = z
foldl f z (x:xs) = foldl (f z x) xs

Синтаксическим сахаром для какого кода является объявление следующего типа данных: data MyData = A { f :: Int, g :: Int -> Double }

data MyData = A Int (Int -> Double) 

Напишите тип выражения flip id.

id :: a -> a
flip :: (a -> b -> c) -> b -> a -> c
-- a ≡ b -> c
flip id :: b -> (b -> c) -> c

Напишите тип выражения ((+) . )

(+) :: Num n => n -> n -> n
(.) :: (b -> c) -> (a -> b) -> a -> c
-- b ≡ n; c ≡ n -> n
((+) . ) :: (a -> n) -> a -> n -> n

Напишите тип выражения (.) . (.)

-- left arg
(.) :: (b1 -> c1) -> (a1 -> b1) -> a1 -> c1
-- right arg 
(.) :: (b2 -> c2) -> (a2 -> b2) -> a2 -> c2
-- b ≡ b1 -> c1 ≡ ((a2 -> b2) -> (a2 -> c2)); c ≡ (a1 -> b1) -> (a1 -> c1)
-- a ≡ b2 -> c2 
((.) . (.)) :: (b2 -> c2) -> (a1 -> a2 -> b2) -> (a1 -> a2 -> c2)

Имеется тип данных data A a = B { f :: Double }. Укажите тип f.

f :: A a -> Double

В чем отличие data от newtype?

Уточнить

newtype гарантирует, что данные будут иметь такой же вид в рантайме, как и завернутый тип. То есть Конструктор для newtype гарантированно стирается во время компиляции. data объявляет абсолютно новую структуру данных в рантайме.

В чем отличие newtype от type? Приведите пример.

Что такое ”Currying (каррирование)” и функции высшего порядка?

Каррирование Вычисление функции, принимающей несколько аргументов, через несколько функций, принимающих один аргумент. Например, для функции 2-х аргументов h:(A × B) → C оператор каррирования Λ выполняет преобразование Λ(h):A → (B → C). То есть Λ: ((A × B) → C) → (A → (B → C)).

curry :: ((a, b) -> c) -> a -> b -> c
uncurry :: (a -> b -> c) -> (a, b) -> c

Функции высшего порядка Функции, принимающие в качестве аргументов другие функции или возвращающие другие функции в качестве результата.

map :: (a -> b) -> [a] -> [b]
filter :: (a -> Bool) -> [a] -> [a]
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b

Напишите, что такое DatatypeContexts? Приведите пример (не из презентации)

Ограничения на параметры в объявлениях data и newtype. Объявленные таким образом типы требуют выполнения ограничений при создании (construction) и деконструкции (deconstruction, ≈ разбиение конструктора при паттерн-матчинге), даже если эти ограничения неиспользуются. (deprecated in Haskell 7.2)

data Eq a => Foo a = Constr a

-- не можем написать функцию:
isEq :: Foo a -> Foo a -> Bool
-- должны написать:
isEq :: Eq a => Foo a -> Foo a -> Bool
isRa (Constr x) (Constr y) = x == y

-- не сработает:
getVal :: Foo a -> a
-- сработает:
getVal :: Eq a => Foo a -> a
getVal (Constr x) = x

Напишите тип следующей функции в наиболее общем виде: f a = map (* a) . map (uncurry (+)) . map (\x -> (x, x))

f :: Num a => a -> [a] -> [a]

Напишите функцию с типом, которая принимает список пар чисел и оставляет только такие, что сумма чисел в паре четная.

evenPairs :: (Integral a) :: [(a, a)] -> [(a, a)]
evenPairs = filter (even . uncurry (+))

Задан тип данных data Role a = A { name :: String, role :: a } | B { name :: String, roles :: [a] }. Напишите конструкцию, синтаксическим сахаром для которой является данных Record Syntax.

data Role a = A String a | B String [a]

Когда стоит описывать функцию, зависящую от typeclass‘а, внутри, а когда снаружи?

Когда функция изменяет класс или переводит класс во что-то другое - лучше внутри, если хотим использовать этот класс для вычисления, то снаружи.

Как писать функции и операторы в префиксной и инфиксной нотации?

(:) - это префиксная нотация, : - инфиксная map f a - префиксная, f `map` a - инфиксная

[13/13]Question 3: Kinds

Приведите пример типа с kind’ом Constraint -> *

type P a = a => Int

Приведите пример типа с kind’ом (* -> Constraint) -> Constraint

type D a = (a Int, Num Int)

Приведите пример типа с kind’ом (* -> *) -> Constraint

Monad, Functor, Applicative

Приведите пример типа с kind’ом (* -> Constraint) -> *

type P a = a Int => Int

Приведите пример типа с kind’ом * -> Constraint

Num, Ord, Eq, Show

Приведите пример типа с kind’ом (*->*)->*->*

MaybeT

Приведите пример типа с kind’ом (* -> *) -> *

type P a = a Int

Укажите kind для Monad

(* -> *) -> Constraint

Укажите kind следующего типа данных: data A f g = B (f g) (g f)

Не существует

Укажите kind следующего типа данных: data A f g = B (f g Int)

A :: (* -> * -> *) -> * -> *

Укажите kind типа type C p = p Int => Int

C :: (* -> Constraint) -> *

Укажите kind типа type C p = (p Int, p Double)

C :: (* -> *) -> *

Укажите kind типа type D a = (a Int, Num Int)

D :: (* -> Constraint) -> Constraint

[16/18]Question 4: Type hierarchy

Чему равно значение length (Left "hello") и почему?

0

length = foldr (\_ n -> 1 + n) 0

см. реализацию Foldable для Either

Чему равно значение length (Just [1..10]) и почему?

1 см. выше и реализацию Foldable для Maybe

Напишите typeclass Traversable

class (Functor t, Foldable t) => Traversable t where
  traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
  traverse f = sequenceA . fmap f
  sequenceA :: Applicative f => t (f a) -> f (t a)
  sequenceA = traverse id
  mapM :: Monad m => (a -> m b) -> t a -> m (t b)
  mapM = traverse
  sequence :: Monad m => t (m a) -> m (t a)
  sequence = sequenceA

Напишите реализацию Traversable для списка

instance Traversable [] where
    traverse f = foldr consF (pure [])
    where 
       consF x ys = (:) <$> f x <*> ys

Напишите реализацию Traversable для Maybe

instance Traversable Maybe where
    traverse _ Nothing  = pure Nothing
    traverse f (Just x) = Just <$> f x

Напишите реализацию Traversable для Either

instance Traversable (Either a) where
    traverse _ (Left x) = pure (Left x)
    traverse f (Right y) = Right <$> f y

Напишите typeclass Foldable

Напишите реализацию Foldable для списка

instance Foldable [] where
    foldMap _ []     = mempty
    foldMap f (x:xs) = f x <> foldMap f xs

Напишите реализацию Foldable для Maybe

instance Foldable Maybe where 
    foldr f zero Nothing = zero  
    foldr f zero (Just x) = f x zero 

Напишите реализацию Foldable для Either

instance Foldable Either where 
    foldr f zero Left = zero  
    foldr f zero (Right x) = f x zero 

Напишите, что делают эти расширения языка: TypeSynonyms, MultiParamTypeClasses, ViewPatterns, RecordsWildCards

TypeSynonyms - типы-синонимы в конструкторах? MultiParamTypeClasses - несколько типов в объявлении класса. ViewPatterns - дает паттерн матчинг с функциями. RecordWildcards - упрощает работу с record: дает забивать на поля в паттерн-матчинге и конструкторах.

Реализуйте traverse через sequence.

traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
sequence :: Monad m => t (m a) -> m (t a)
traverse f = sequence . fmap f

Реализуйте sequence через traverse.

sequence = traverse id -- так?

Укажите minimal complete definition для type class’а Foldable

foldMap | foldr

Укажите minimal complete definition для type class’а Traversable

traverse | sequenceA

Напишите реализацию Monoid для Maybe

instance Monoid a => Monoid (Maybe a) where
    mempty = Nothing
    Nothing `mappend` m = m
    m `mappend` Nothing = m
    Just m1 `mappend` Just m2 = Just (m1 `mappend` m2)

Напишите реализацию Monoid для (->)

instance Monoid b => Monoid (a -> b) where
    mempty _ = mempty
    mappend f g x = f x `mappend` g x

Напишите реализацию Monoid для (a -> a). Используя это знание, выразите foldr через foldMap

instance Monoid (b -> b) where
    mempty _ = id
    mappend  = (.)

newtype Arrow b = Arrow { getArrow :: b -> b }
-- для упрощения будем считать, что тип foldr следующий:
foldr   :: (a -> b -> b) -> t a -> b -> b
-- иначе придется задействовать flip, если сильно захочется, когда-нибудь будет реализовано
foldMap :: Monoid m => (a -> m) -> t a -> m

transform :: (a -> b -> b) -> a -> Arrow b
transform = Arrow . f

foldr f = getArrow . foldMap (transform f)

[10/10]Question 5: Functors

Напишите законы функтора

1. fmap id = id
2. fmap (f . g)   = (fmap f) . (fmap g)
   fmap (f . g) F = fmap f (fmap g F)

Напишите type class Functor и его реализацию для ((->) r)

class Functor f where
  fmap :: (a -> b) -> f a -> f b
  (<$) :: a        -> f b -> f a
  (<$) = fmap . const

instance Functor ((->) r) where
    fmap = (.)

Напишите type class Functor и его реализацию для Maybe

instance Functor Maybe where
    fmap f (Just x) = Just f x
    fmap _ Nothing = Nothing

Напишите type class Functor и его реализацию для Either

instance Functor (Either e) where
    fmap f (Right x) = Right (f x)
    fmap _ l         = l

Напишитe type class Functor и его реализацию для []

instance Functor ([]) where
    fmap = map

Реализуйте функцию (<<$>>) :: (Functor f, Functor g) => (a -> b) -> f (g a) -> f (g b)

(<<$>>) f w = (fmap $ fmap f) w

Напишите класс типов Bifunctor и реализуйте его для пары

class Bifunctor p where
    bimap  :: (a -> b) -> (c -> d) -> p a c -> p b d
instance Bifunctor (,) where
    bimap f g (a, b) = (f a, g b)

Напишите класс типов Bifunctor и реализуйте его для Either

instance Bifunctor Either where
    bimap f _ (Left a)  = Left  (f a)
    bimap _ g (Right b) = Right (g b)

Реализуйте fmap через bind

<$> :: Functor f => (a -> b) -> f a -> f b
>>= :: Monad m => m a -> (a -> m b) -> m b

f <$> a = a >>= (return . f)

Реализуйте bind через join и fmap

(>>=) :: m a -> (a -> m b) -> m b
fmap :: (a -> b) -> f a -> f b
join :: m (m a) -> m a
a >>= f = join (fmap f a)

[9/11]Question 6: Applicatives

Напишите законы аппликатива

1. identity
   pure id <*> v = v
2. composition
   pure (.) <*> u <*> v <*> w = u <*> (v <*> w)
3. homomorphism
   pure f <*> pure x = pure (f x)
4. interchange
   u <*> pure y = pure ($ y) <*> u

Напишите type class ~Applicative и его реализацию для ((->) r)

class Functor f => Applicative f where
    pure  :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b
    (*>) :: f a -> f b -> f b
    (<*) :: f a -> f b -> f a

instance Applicative ((->) r) where
    pure x = \_ -> x
    f <*> g = \x -> f x (g x)

Напишите type class ~Applicative и его реализацию для Maybe

class Functor f => Applicative f where
    pure  :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b
    (*>) :: f a -> f b -> f b
    (<*) :: f a -> f b -> f a

instance Applicative Maybe where
    pure = Just
    Just f  <*> a = f <$> a
    Nothing <*> _ = Nothing

Напишите type class ~Applicative и его реализацию для Either

class Functor f => Applicative f where
    pure  :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b
    (*>) :: f a -> f b -> f b
    (<*) :: f a -> f b -> f a

instance Applicative (Either e) where
    pure          = Right
    Left  e <*> _ = Left e
    Right f <*> r = fmap f r

Напишите type class ~Applicative и его реализацию для []

class Functor f => Applicative f where
    pure  :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b
    (*>) :: f a -> f b -> f b
    (<*) :: f a -> f b -> f a

instance Applicative [] where
    pure x    = [x]
    fs <*> xs = [f x | x <- xs, f <- fs]

Напишите type class ~Applicative и его реализацию для ZipList

class Functor f => Applicative f where
    pure  :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b
    (*>) :: f a -> f b -> f b
    (<*) :: f a -> f b -> f a

newtype ZipList a = zipList { getZipList :: [a] }
instance Applicative ZipList where
    pure x                        = ZipList (repeat x)
    (ZipList fs) <*> (ZipList xs) = ZipList (zipWith ($) fs gs)

Реализуйте функцию liftA3

liftA3 :: Applicative f => (a -> b -> c -> d) -> f a -> f b -> f c -> f d
liftA3 f a b c = f <$> a <*> b <*> c
-- насколько я понимаю, так можно проворачивать с любым числом аргументов

Реализуйте функцию liftAA2 :: (Applicative f, Applicative g) => (a -> b -> c) -> f (g a) -> f (g b) -> f (g c)

liftAA2 = liftA2 . liftA2

Реализуйте функцию (<<*>>) :: (Applicative f, Applicative g) => f (g (a -> b)) -> f (g a) -> f (g b)

Реализуйте функцию eitherA :: (Alternative f) => f a -> f b -> f (Either a b)

eitherA :: (Alternative f) => f a -> f b -> f (Either a b)
-- eitherA f1 f2 = fmap (Left) f1 НЕВЕРНО

Есть функция g :: a -> b и объект x :: Applicative f => f a. Напишите два разных способа получить объект y :: Applicative f => f b из x с использованием g.

getY :: (Applicative f) => (a -> b) -> f a -> f b
getY = fmap
getY = (<$>)
getY g x = pure g <*> x

[18/19]Question 7: Monads

Что такое монада?

Монады применяют функции, которые возвращают завернутые значения, к завернутому знаению.

class Monad m where   -- m :: * -> *
    return :: a -> m a                  -- return
    (>>=)  :: m a -> (a -> m b) -> m b  -- bind
    (>>)   :: m a -> m b -> m b         -- then
    m >> k = m >>= \_ -> k
(=<<) :: Monad m => (a -> m b) -> m a -> m b
f =<< x = x >>= f
infixl 1  >>, >>=
infixr 1  =<<

Напишите не меньше пяти типов данных, являющихся монадой

1. []
2. Maybe
3. Either
4. IO
5. State
6. Identity
7. Writer
8. Reader
9. RWS
10. Cont

Напишите не менее семи функций, полезных при работе с монадами

1. return
2. >>=
3. =<<
4. >>
5. liftM
6. liftM2
7. >=>
8. <=<
9. join
10. ifM
11. (||^)

Напишите тип функции join и приведите несколько примеров использования

join :: Monad m => m (m a) -> m a
ghci> join [[1,2], [3,4]]
[1,2,3,4]
ghci> join Just (Just 3)
Just 3

Реализуйте join через bind.

join :: Monad m => m (m a) -> m a
(>>=) :: m a -> (a -> m b) -> m b

join x = x >>= id

Напишите реализацию Monad для списка

data [a] = [] | a : [a]

instance Monad [] where
    return x = [x]
    xs >>= f = concat (map f xs)

Напишите реализацию Monad для Maybe

data Maybe a = Nothing | Just a

instance Monad Maybe where
    return = Just
    Nothing >>= _ = Nothing
    Just a  >>= f = f a

Напишите реализацию Monad для Either

data Either a b = Left a | Right b

instance Monad (Either a) where
    return  = Right
    Right r >>= f = f r
    Left l  >>= _ = Left l

Реализуйте Monad для ((->) r)

instance Monad ((->) r) where
    return = const
    f >>= k = \r -> k (f r) r

Напишите определение типа данных Writer и его instance Monad

newtype Writer w a = Writer { runWriter :: (a, w) } -- a is value, w is log
-- Writer w a type is just a newtype wrapper for a tuple (a, w); just a reminder of what newtype is

instance Monoid w => Monad (Writer w) where
    return a            = Writer (a, mempty)
    Writer (x, v) >>= f = let Writer (y, v') = f x
                          in Writer (y, v `mappend` v')

Напишите определение типа данных Reader и его instance Monad

newtype Reader e a = Reader { runReader :: e -> a }

instance Monad (Reader e) where 
    return a         = Reader $ \e -> a 
    (Reader r) >>= f = Reader $ \e -> runReader (f (r e)) e

Напишите определение типа данных State и его instance Monad

newtype State s a = State { runState :: s -> (a, s) }
instance Monad (State s) where
    return a       = State $ \s -> (a, s)
    oldState >>= f = State $ \s -> let (a, newState) = runState oldState s
                                   in runState (f a) newState

Напишите определение типа данных Cont и его instance Monad

newtype Cont r a = Cont { runCont :: (a -> r) -> r }

instance Monad (Cont r) where
    return a = Cont ($ a)
    Cont arr >>= f = Cont $ \br -> arr $ \a -> runCont (f a) br

Напишите тип (>=>) и смысл этого оператора.

(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c

Композиция функций, возвращающих завернутое значение.

Покажите, синтаксическим сахаром для чего является do-нотация (включая let).

Недостаточно

-- two-line do notation
do x <- m
   e
-- desugars to:
m >>= (\x -> e)

-- one-line do notation
main = do putStrLn "hello, world"
-- you can just remove do
main = putStrLn "hello, world"

-- multi-line do notation
do x <- mx
   y <- my
   z
-- is equivalent to:
do x <- mx
   do y <- my
      z
-- desugars to:
mx >>= (\x -> my >>= (\y -> z ))

-- non-recursive let in a do block desugars to a lambda:
do let x = y
   z
-- desugars to
(\x -> z) y

Что такое IO? Как теоретически это реализовано?

data IO a :: * -> *
instance Monad IO where
    (>>=) = bindIO

Отличие unsafePerformIO от unsafeInterleaveIO?

unsafeInterleaveIO дает дополнительные гарантии на порядок операций, идейно так реализовано:

do
    before
    unsafeInterleaveIO side
    after

Гарантируется, что то, что в side всегда выполнится после before. unsafePerformIO таких гарантий не дает.

[7/7]Question 8: Trans

Напишите класс типов MonadTrans и реализуйте его для StateT

class MonadTrans t where    -- t :: (* -> *) -> * -> *
    lift :: Monad m => m a -> t m a
instance MonadTrans (StateT s) where
    lift m = StateT $ \s -> do
        a <- m
        return (a, s)

Напишите класс типов MonadTrans и реализуйте его для WriterT

instance (Monoid w) => MonadTrans (WriterT w) where
    lift m = WriterT $ do
        a <- m
        return (a, mempty)

Напишите класс типов MonadTrans и реализуйте его для MaybeT

instance MonadTrans MaybeT where
    lift = MaybeT . liftM Just

Напишите класс типов MonadTrans и реализуйте его для ReaderT

instance MonadTrans ReaderT where
   lift m = ReaderT (const m)

Напишите тип StateT и то, как определен State через StateT

newtype StateT s m a = StateT { runStateT :: s -> m (a,s) }
type State s = StateT s Identity

Напишите тип MaybeT и реализуйте его инстанс Monad

newtype MaybeT m a = MaybeT { runMaybeT :: m (Maybe a) }
instance (Monad m) => Monad (MaybeT m) where
    fail _ = MaybeT (return Nothing)
    return = lift . return
    x >>= f = MaybeT $ do
        v <- runMaybeT x
        case v of
            Nothing -> return Nothing
            Just y  -> runMaybeT (f y)

Нарисуйте табличку отличий обычных типов и их трансформеров для известных вам трансформеров

Base monad	Transformer	Original type	Combined type
Maybe	MaybeT	Maybe a	m (Maybe a)
Either	EitherT	Either a b	m (Either a b)
Writer	WriterT	(a, w)	m (a, w)
Reader	ReaderT	r -> a	r -> m a
State	StateT	s -> (a,s)	s -> m (a, s)
Cont	ContT	(a -> r) -> r	(a -> m r) -> m r

[9/10]Question 9: Strict Lazy

Что такое irrefutable patterns и зачем они нужны?

Ленивые паттерны. Матчинг значения v на паттерн ~pat всегда успешный, независимо от pat. Может понадобиться, если у нас есть бесконечная структура, определенная рекурсивно.

Что такое Stream Fusion и зачем он нужен?

Нужно написать больше

Пишем что-нибудь вроде функций с бесконечными списками, аллоцируем слишком много памяти. Stream fusion превращает нашу функцию во что-то, что использует рекурсивную функцию, которая аллоцирует себе столько памяти, сколько нужно для результата. Вместо явной рекурсии можем использовать нерекурсивные функции над списком, которые используют допустимые функции map, foldr и так далее. Тут стало слишком много Inception.

Напишите, что значит тип ST и напишите основные функции по работе с ним

Монада, в которой есть мутабельные переменные и массивы, но при этом она referentially transparent. Strict state-transformer monad. new/read/write/modifySTRef, runST.

Что такое BangPatterns? Когда их нужно использовать?

Используем ! и убиваем ленивость. Делаем это, когда долго работаем и ломаемся по памяти; при арифметических операциях, рекурсии и подозрениях на утечки памяти.

Укажите, что делает deepseq и как.

deepseq полностью вычисляет структуру (до нормальной формы). Обходит структуру “глубоко”, например, seq вычислит до первого конструктора в списке, а deepseq зафорсит вычисление всех элементов списка.

В чем разница между seq и deepseq?

Первый вычисляет до WHNF, второй - до нормальной формы. Работает так: если вычислился результат seq, то и аргумент тоже вычислен.

В чем разница между seq и BangPatterns?

BangPatterns удобнее пишется, особенно в больших количествах, а так это вроде синтаксический сахар для seq.

Что такое STRef и в чем отличие от IORef?

STRef - укзатель на мутабельный контейнер в монаде ST, а IORef, соответственно, в IO. А по сути это вроде одно и то же.

Что такое Deforestation?

Избавляемся от аллокации промежуточных списков. По сути сливаем одинаковые вызовы функций в один.

map f . map g = map (f . g)

Чем плохо использовать IORef и IOArray? Зачем нужны STRef и STArray?

IOArray не очень мутабельный, IO-монада дает больше возможностей, но они не всегда нужны. А еще ST-операции можно делать в чистых функциях. Вообще STRef используем, когда мутабельность нам не снаружи дают, а она является деталью имплементации, и снаружи наша деятельность кажется вполне себе чистой.

[4/4]Question 10: TemplateHaskell

Как можно посмотреть AST-дерево для выражения в Haskell?

-- report :: Bool -> String -> Q () НЕВЕРНО

Но вообще цитирующими скобками же, наверное.

Напишите не меньше трех применений TemplateHaskell

• Писать функции n аргументов
• Генерировать автоматом инстансы
• Что-то высчитывать во время компиляции, тип один раз и навсегда.
• Парсить всякие структуры типа json
• Генерировать автоматом линзы

Что такое Q в типах функций Template Haskell?

Q - монада цитирования, которая позволяет автоматически генерировать уникальные имена для переменных с помощью монадической функции newName :: String -> Q Name.

В чем разница между [| |] и $()?

[| |] - quasi quotes, $() - вклейка (splice). Цитирующие скобки преобразуют конкретный хаскель-код в структуру Exp (получают AST), а вклейка - подставляет AST на место шаблона, поэтому это взаимно обратные операции.

[8/12]Question 11: Lenses

Зачем нужны линзы

Чтобы в сложных структурах(записях) удобно доставать и изменять значения.

Что такое изоморфизм (Iso)?

Изоморфизм - связь между эквивалентными типами. Iso - пара маппингов из первого типа во второй и из второго с первый, таких, что:

fw . bw = id
bw . fw = id

Чем линзы отличаются от призм?

Призмы - это как линзы, но линзы смотрят на часть типа-произведения, а призмы спускаются на уровень ниже в типе-сумме вроде Either или падают.

Напишите тип Iso

type Iso s t a b = forall p f. (Profunctor p, Functor f) => p a (f b) -> p s (f t)

Напишите тип функции from для Iso

from :: AnIso s t a b -> Iso b a t s

Напишите тип функции iso

iso :: (s -> a) -> (b -> t) -> Iso s t a b

Напишите реализацию over

Реализуйте set через over

Реализуйте over через view и set.

Напишите функцию lens, которая принимает геттер и сеттер и возвращает линзу

Укажите операторные обозначений функций view, set, over. Есть ли отличие в типах функций и их операторных выражений?

view == (^.), set == (.~), over == (%~). Отличий не знаю.

Реализация view

Не понятно к чему это, ну тип view’ :: obj -> field Как мы его делаем, есть поле car, ну и пишем car Person

[10/10]Question 12: Threads

Что такое STM (коротко), что позволяет делать и какие есть функции по работе с ним?

Software Transactional Memory - абстракция для concurrent communication, хороша тем, что две concurrent абстракции можно легко слепить в одну и не придется светить деталями реализации; позволяет выполнить транзакцию (либо все операции успешно, либо откат). Функции newTVar/readTVar/writeTVar, atomically, retry, orElse.

В чем отличие Haskell потоков от, например, потоков в Java?

Много хаскель-тредов могут быть замаплены на один ОС-тред, потому что в действительности этот ОС-тред всего лишь гоняет хаскель-рантайм. А рантайм сам разбирается со своим внутренним шедулингом, yield’ами и прочим. Это, кстати, уменьшает оверхед, который ось обычно тратит на context switching.

Что такое Strategy? Перечислите несколько стратегий и реализуйте некоторые. Зачем они нужны?

Стратегии позволяют выразить паралельные вычисления, то есть:

• поддерживают deterministic parallelism: результат программы не зависит от параллельных вычислений. Никаких сайд-эффектов.
• отделяют описание параллелизма от логики самой программы (модульность - здорово!). Делаем ленивую структуру, которая представляет собой наши вычисления, а потом пишем под нее стратегию, которая описывает, как обходить эту структуру и делать вычисления последовательно или параллельно.
• композиция! Берем маленькие стратегии, из них делаем большую.
• есть инстансы Monad и Applicative для удобства тривиальных случаев

Примеры:

• r0: ничего не делай.
• rseq: вычислить до WHNF.
• rdeepseq: вычисли меня полностью. %op = evalSeq Control.Seq.%op.
• rpar: сделаем спарк для параллельного вычисления.
• rparWith: композиция. Не покидает монаду Eval, не имеет встроенного rseq.

Как в Haskell обстоят дела с DeadLock‘ами?

Когда рантайм GHC находит группу тредов, которые все заблочены на блокирующих мутабельных переменных (MVar или переменные STM), и видит, что другие треды на них не ссылаются, он решает, что все треды в дедлоке и отсылает им асинхронные исключения BlockedIndefinitelyOnMVar/STM. Кстати, ловить асинхронные исключения моветон.

Что такое RTS?

RunTime System. 50k строк сишного кода, хайлайты:

• содержит всякий вспомогательный код, который позволяет бросить эксепшн после error, аллоцировать Array#, организовать работу с MVar.
• включает в себя менеджер памяти плюс сборщик мусора.
• содержит userspace-шедулер для хаскель-тредов, с поддержкой шедулинга их на несколько процессоров, и позволяет хаскель-тредам вызывать внешние функции в разных тредах ОС.
• содержит интерпретатор байткода для GHCi и динамический линковщик туда же.
• может в разный профайлинг и покрытие кода.
• поддержка STM.

Укажите несколько полезных опций RTS

-Asize/-Hsize/-Msize, -threaded, -Nn, -prof

Опишите, что такое MVar, зачем он может быть нужен и несколько функций по работе с этим объектом.

MVar T - Мутабельная переменная, которая либо пуста, либо содержит значение типа t. Можно использовать как синхронизированную мутабельную переменную, как канал или как семафор. Функции: takeMVar, putMVar, read/swap/with/modifyMVar

Что делает forkIO? Чем он отличается от forkFinally?

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

Как в Haskell реализована concurency

Par, Strategy, forkIO, MVar, STM, Async

Что такое spark и его флаги

Мини тред, занятый одним вычислением, соответственно легковесный и их можно завести очень много converted - useful work overflowed - sparks generated after spark pool limit achieved dud - already evaluated at the moment of applying `rpar` GC’d - unused and thrown away (ignored) => garbage collector fizzled - was unevluated at the time it was sparked but was later evaluated independently by the program

[5/6]Question 13: forall

Напишите, как иметь список объектов разных функторов, внутри каждого из которых значения одинакового типа, чтобы иметь возможность применить функции из этого значения в другое?

data FunctorBox a = forall f . Functor f => FB (f a)
FB :: forall {a} {f :: * -> *} . Functor f => f a -> FunctorBox a -- as ghci sees it

fmapFB :: forall t a . (t -> a) -> FunctorBox t -> FunctorBox a
fmapFB f = \(FB a) -> FB (f <$> a)

Зачем нужно расширение ExistentialQuantification?

Нужно написать больше

Для того, чтобы работать со значениями разных типов, но обладающими каким-то свойством (например, они одного класса), одинаково. Например, чтобы иметь возможность складывать такие значения в лист, получая тем самым гетерогенный лист, спрятав значения в некоторую “коробку” (type hider)

Зачем нужно расширение языка -XExplicitForall?

Чтобы явно аннотировать типы с использованием forall

В чем разница между -XRank2Types и -XRankNTypes? Зачем нужны оба?

-XRank2Types разрешает полиморфные типы ранга 2, -XRankNTypes разрешает полиморфные типы любого ранга. В системах с полиморфными типами ранга 2 задача вывода типов разрешима, если же ранг > 2, то задача становится неразрешимо и возникает необходимость явной аннотации типов. С этим и связана необходимость разделения этих расширений языка.

Зачем нужно расширение языка -XScopedTypeVariables и как оно взаимодействует с forall?

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

{-# LANGUAGE ScopedTypeVariables #-}
import Data.List

main = putStrLn "No errors."

-- show
myFunction :: forall a. Ord a => [a] -> [(a, a)]
myFunction inputList = zip sortedList nubbedList
    where sortedList :: [a]
          sortedList = sort inputList
          nubbedList :: [a]
          nubbedList = nub inputList
-- /show

Написать fmap с forall

fmap :: forall f . forall a b . (a -> b) -> f a -> f b

[6/8]Question 14: Advanced types

Что такое typed holes и зачем они нужны?

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

mfold :: [Maybe a] -> [Either a b]
mfold = foldr _f _z

> Found hole ‘_f’ with type: Maybe a -> [Either a b] -> [Either a b]
> Found hole ‘_z’ with type: [Either a b]

Зачем нужно расширение языка -XTypeApplications?

Нужно написать больше

Позволяет задавать явные аргументы типов полиморфной функции, например map @Int @Bool isEven xs. Решает проблему show/read, потому что мы явно задаем типы и все тайпчекается.

answer_read = show (read @Int "3") -- "3" :: String
answer_show = show @Integer (read "5") -- "5" :: String
answer_showread = show @Int (read @Int "7") -- "7" :: String

Зачем нужно расширение языка -XPartialSignatures?

Аналог typed holes для сигнатур функций:

arbitCs :: _ => a -> String
arbitCs x = show (succ x) ++ show (x == x)
Main.hs:6:12: warning: [-Wpartial-type-signatures]
    Found constraint wildcard ‘_’ standing for ‘(Show a, Eq a, Enum a)’
    In the type signature:
      arbitCs :: _ => a -> String

Можно ли создать следующий тип данных в Haskell: data a : > b = (a -> b) : > (b -> a)?

Что такое Functional Dependencies? Назовите какой-нибудь известный вам type class, в котором присутствуют функциональные зависимости.

Функциональные зависимости используются для ограничения параметров тайпклассов. Они позволяют объявить, что в тайпклассе с несколькими параметрами один из параметров можно однозначно! определить по другим.

class Mult a b c | a b -> c where
  (*) :: a -> b -> c

Классический (и единственный) пример использования - перемножение матриц/векторов/скаляров, тайпкласс указан выше.

Пример функции 2-го ранга

Rank 0: Int
Rank 1: forall a . a -> Int
Rank 2: (forall a . a -> Int) -> Int
Rank 3: ((forall a . a -> Int) -> Int) -> Int

foo :: (forall a . a -> a) -> (Char,Bool)
foo f = (f 'c', f True)

Что делает -XDataKinds

Заставляет создавать компилятор кайнды для нашей даты Промоутит простые типы до кайндов

GADT

Generalized algebraic datatypes или просто ГАДы Generalized algebraic datatypes, or simply GADTs, are a generalization of the algebraic data types that you are familiar with. Basically, they allow you to explicitly write down the types of the constructors.

[12/13]Question 15: Comonads

Напишите пример использования комонад

type Option = String
data Config = MakeConfig [Option]
type ConfigBuilder = Traced [Option] Config

profile :: ConfigBuilder \rightarrow Config
profile builder = runTraced builder ["-prof", "-auto-all"]

goFaster :: ConfigBuilder \rightarrow Config
goFaster builder = runTraced builder ["-O2"]

ghci> extract (traced defaultConfig =>> goFaster =>> profile)
MakeConfig ["-Wall","-prof","-auto-all","-O2"]

Напишите, какие комонады двойственны монадам Reader, Writer, State

Env, Traced и Store соответственно.

Напишите, какие комонады двойственны монадам Traced, Store, Env

Writer, State и Reader соответственно.

Напишите комонаду Stream и инстанс Comonad для нее.

data Stream a = Cons a (Stream a)

instance Functor Stream where
    fmap f (Cons x xs) = Cons (f x) (fmap f xs)

instance Comonad Stream where
    extract (Cons x _) = x
    duplicate xs@(Cons _ xs') = Cons xs (duplicate xs')
    extend f xs@(Cons _ xs') = Cons (f xs) (extend f xs')

Напишите комонаду Env и инстанс Comonad для нее.

data Env e a = Env e a

instance Comonad (Env a) where
    extract (Env _ a) = a
    extend f env@(Env e _) = Env e (f env)

Напишите комонаду Store и инстанс Comonad для нее.

data Store s a = Store (s \rightarrow a) s

instance Comonad (Store s) where
    extract (Store f s) = f s
    extend f (Store g s) = Store (f . Store g) s

Напишите комонаду Traced и инстанс Comonad для нее.

newtype Traced m a = Traced { runTraced :: m \rightarrow a }

instance Monoid m \Rightarrow Comonad (Traced m) where
    extract (Traced ma) = ma mempty
    extend f (Traced ma) = Traced $ \m \rightarrow f (Traced $ \m' \rightarrow ma (m <> m'))

Реализуйте instance Comonad для обычного Zipper

data ListZipper a = LZ [a] a [a]

instance Functor ListZipper where
    fmap f (LZ ls x rs) = LZ (fmap f ls) (f x) (fmap f rs)

instance Comonad ListZipper where
    extract (LZ _ x _) = x
    duplicate = genericMove listLeft listRight
      where
        iterate' f = tail . iterate f
        genericMove a b z = LZ (iterate' a z) z (iterate' b z)
        listLeft (LZ (a:as) x bs)  = LZ as a (x:bs)
        listRight (LZ as x (b:bs)) = LZ (x:as) b bs

IO использует абстракцию монад, какой аналог есть в мире комонад?

Напишите класс ComonadTrans

class ComonadTrans t where
    lower :: Comonad w -> t w a -> w a

Как можно было бы сделать codo нотацию для комонад? И что бы происходило в этом синтаксическом сахаре?

method
    wa> expr1
    wb> expr2
    wc> expr3

Такая штука выливается в это:

\wa \rightarrow
let wb =      extend (\this \rightarrow expr1) wa
    wc =      extend (\this \rightarrow expr2) wb
in  extract $ extend (\this \rightarrow expr3) wc

extend для comonad

class Functor w => Comonad w where
    extract   :: w a -> a
    (<<=)     :: (w a -> b) -> w a -> w b  -- extend
    duplicate :: w a -> w (w a)
extend f  = fmap f . duplicate
duplicate = extend id
fmap f    = extend (f . extract)

data [a] = [] | a : [a]
data ListZipper a = LZ [a] a [a]
instance Functor ListZipper where
    fmap f (LZ ls x rs) = LZ (map f ls) (f x) (map f rs)
extract :: ListZipper a -> a
extract (LZ _ x _) = x

Zipper

Такая штуковина, которая работает с бесконечными структурами, и ползает по ним с помощью курсора, помогает считать значения, зависящие от соседей

data [a] = [] | a : [a]
data ListZipper a = LZ [a] a [a]
listLeft, listRight :: ListZipper a -> ListZipper a
-- Сдвиг вправо и влево
listLeft  (LZ (a:as) x bs) = LZ as a (x:bs)
listRight (LZ as x (b:bs)) = LZ (x:as) b bs

[4/12]Question 16: Idris

Реализуйте функцию take для вектора на Idris

Реализуйте функцию filter для вектора на Idris

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

Напишите тип ”зависимая пара” на Idris

Что такое [| |]-идиома в Idris?

Что такое !-идиома в Idris?

Что такое _|_-eliminator? Зачем это надо?

Что такое ”тотальность” и какие преимущества она дает?

Какие парадигмы использует Idris

Totality Strict evalution Theorem proving DSL Extensible effects

Зависимые типы в idris и зачем они нужны

Зависимый тип в информатике и логике — тип, который зависит от некоторого значения. К примеру, тип, описывающий n-кортежи действительных чисел является зависимым, так как он «зависит» от величины n. типы функций тогда могут принимать вид «функция, принимающая сообщение, подписанное некоторым пользователем, и возвращающая данные этого пользователя», вместо более распространённого «функция, принимающая сообщение и возвращающая данные пользователя», что ведёт к намного более точным спецификациям. Более того, это даёт возможность, так сказать, перейти от подлежащих к сказуемым, использовать принцип «высказывания как типы»: «5 больше 3», «неверно, что 5 больше 3», «7 является простым числом», «Василий получил 2 сообщения».

Отличие Idris от разных языков

Идрис сочетает в себе особенности относительно мейнстримовых языков функционального программирования с функциями, заимствованных из систем автоматического доказательства теорем, фактически размывает границу между этими двумя видами программного обеспечения.

Пример кода на Idris

(++) : Vect n a -> Vect m a -> Vect (n + m) a
(++) Nil       ys = ys
(++) (x :: xs) ys = x :: xs ++ ys