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

23 апреля 2014

Мы с вами уже перестали бояться монад, но всякие непонятные стрелочки в коде типа <>, <$>, <*> и <|> по-прежнему повергают нас в ужас. Сегодня мы выясним, что и здесь бояться особо нечего. Как и в случае с монадами, здесь имеют место быть обыкновенные классы типов и функции для работы с ними. Все просто.

Функторы

Функтор — это просто такой класс для типов, к которым можно применить отображение (map):

class Functor f where
  fmap :: (a -> b) -> f a -> f b

Для fmap должны выполняться следующие законы:

fmap id = id
fmap (p . q) = (fmap p) . (fmap q)

Следует отметить, что в GHC есть расширение DeriveFunctor, позволяющее писать deriving Functor.

Типичные функторы — это Maybe, Either и, конечно же, списки. Для списков fmap определен просто как map. Обратите внимание, что он не может быть определен как reverse . map g, потому что это нарушило бы первый закон. Кроме того, часто экземпляр класса типов Functor объявляется для различных контейнеров. Например, Data.Map также является функтором.

У функции fmap есть инфиксная форма:

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

Из любой монады можно получить функтор:

ghci> let fmap' f ma = ma >>= (return . f)
ghci> :t fmap'
fmap' :: Monad m => (a -> b) -> m a -> m b

Или в do-нотации:

fmap' f ma = do
  a <- ma
  return $ f a

То есть, можно сказать, что любая монада автоматически также является и функтором. В том числе, это относится к монаде IO, что позволяет писать:

ghci> x <- fmap reverse getLine
abcdef
ghci> x
"fedcba"

Тем не менее, в общем случае без явного объявления экземпляра класса типов никакого функтора из монады вы не получите.

Пока несложно, правда?

Аппликативные функторы

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

-- Control.Applicative

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

  (*>) :: f a -> f b -> f b
  u *> v = pure (const id) <*> u <*> v

  (<*) :: f a -> f b -> f a
  u <* v = pure const <*> u <*> v

На первый взгляд все это выглядит несколько запутанно, поэтому рассмотрим пример. Списки, Maybe, Either и другие хорошо знакомые нам типы являются аппликативными функторами. Вот как это работает на примере Maybe:

ghci> Just (+1) <*> Just 3
Just 4
ghci> Just (+1) <*> Nothing
Nothing
ghci> Nothing <*> Just 3
Nothing

А вот пример со списками:

ghci> [ (+1), (*2) ] <*> [1,2,3]
[2,3,4,2,4,6]

То есть, функция pure как бы оборачивает функцию в контекст, а <*> применяет функцию в контексте к данным в контексте. Использование операторов *> и <* на практике я встречал довольно редко, но, тем не менее, с ними можно столкнуться. Тут требуется небольшое пояснение.

Есть такая забавная функция const, принимающая два аргумента и всегда возвращающая первый:

ghci> :t const
const :: a -> b -> a

Есть такой забавный фокус:

ghci> :t const id
const id :: b -> a -> a

Если вам это сломало мозг, тут объясняется, как это работает. Это несложно.

По умолчанию <* и *> определены так:

u <* v = pure const <*> u <*> v
u *> v = pure (const id) <*> u <*> v

Например:

ghci> Just 1 <* Just 2
Just 1
ghci> [1,2,3] <* [4,5,6]
[1,1,1,2,2,2,3,3,3]
ghci> Just 1 *> Just 2
Just 2
ghci> [1,2,3] *> [4,5,6]
[4,5,6,4,5,6,4,5,6]

Куда указывает стрелочка, то значение и остается. Ну и в соответствии с семантикой <*>, если один из аргументов является Nothing или пустым списком, то и в итоге получаем Nothing или пустой список.

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

-- | Identity
pure id <*> v = v
-- | Composition
pure (.) <*> u <*> v <*> w = u <*> (v <*> w)
-- | Homomorphism
pure f <*> pure x = pure (f x)
-- | Interchange
u <*> pure y = pure ($ y) <*> u

На практике, конечно же, их редко кто доказывает строго, обычно достаточно написать соответствующие тесты.

Синергия классов типов Functor и Applicative

Как вы, конечно же, заметили, Applicative является подклассом Functor. Это означает, что стрелочки <$> и <*> часто используются совместно. Допустим, у нас есть такая функция:

ghci> let f x = if x == 0 then Nothing else Just (1 / x)
ghci> f 0
Nothing
ghci> f 3
Just 0.3333333333333333

Теперь мы хотим применить ее к трем числам — x, y и z. Если хотя бы для одного числа функция возвращает Nothing, то и весь результат должен быть Nothing. Иначе мы должны вернуть Just (1 / x, 1 / y, 1 / z). Как мы помним, Maybe является монадой, что позволяет вместо всяких вложенных if, then, else написать:

g x y z = do
  x' <- f x
  y' <- f y
  z' <- f z
  return (x', y', z')

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

ghci> :t (,,)
(,,) :: a -> b -> c -> (a, b, c)
ghci> (,,) 1 2 3
(1,2,3)

Держим в уме, что запись a -> b -> c -> (a, b, c) равносильна a -> (b -> c -> (a, b, c)).

ghci> :t f 1
f 1 :: Maybe Double
ghci> :t (<$>)
(<$>) :: Functor f => (a -> b) -> f a -> f b
ghci> :t (,,) <$> f 1
(,,) <$> f 1 :: Maybe (b -> c -> (Double, b, c))

Смотрите, у нас были некие данные (результат применения функции f к 1) в контексте Maybe и мы успешно применили (частично, благодаря каррированию) функцию (,,) к этому контексту, поскольку Maybe является функтором. В итоге мы получили новую функцию от двух аргументов в контексте Maybe. Теперь нам нужно применить полученную функцию в контексте к следующей порции данных в контексте. Но постойте-ка, ведь для этого и нужны аппликативные функторы!

ghci> :t (,,) <$> f 1 <*> f 2
(,,) <$> f 1 <*> f 2 :: Maybe (c -> (Double, Double, c))
ghci> :t (,,) <$> f 1 <*> f 2 <*> f 3
(,,) <$> f 1 <*> f 2 <*> f 3 :: Maybe (Double, Double, Double)
ghci> (,,) <$> f 1 <*> f 2 <*> f 3
Just (1.0,0.5,0.3333333333333333)

Вместо четырех строчек кода в do-нотации мы обошлись всего лишь одной. Разве это не здорово?

Также имеются функции liftA2, liftA3 и так далее, делающие то же самое:

ghci> liftA2 (,) (f 1) (f 2)
Just (1.0, 0.5)
ghci> :t liftA2
liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c

Приведенный паттерн довольно широко используется в Haskell, например, в библиотеке aeson, при работе с формами в различных веб-фреймворках и тд.

Дополнение: Тихо и незаметно Applicative стал суперклассом Monad.

Моноиды

Моноиды в Haskell используются вообще везде.

-- Data.Monoid

class Monoid a where
  mempty :: a
  mappend :: a -> a -> a

  mconcat :: [a] -> a
  mconcat = foldr mappend mempty

Моноид — это просто такая штука, которую можно «складывать» (mappend) с другими такими же штуками и у которой имеется нейтральный элемент (mempty), который при сложении с любым другим элементом дает этот же элемент.

У mappend есть более короткая запись:

(<>) :: Monoid m => m -> m -> m

Законы для моноидов:

mempty <> x = x
x <> mempty = x
x <> (y <> z) = (x <> y) <> z
mconcat = foldr (<>) mempty

Список является типичным моноидом. Для него mempty — это пустой список, а mappend — операция ++:

ghci> "aaa" <> "bbb"
"aaabbb"
ghci> mempty <> "abc"
"abc"

Еще моноидами являются Set’ы, Map’ы, Maybe, а также Text, BinaryString и их билдеры. Для многих типов можно объявить более одного экземпляра класса типов Monoid. Например, для чисел можно выбрать в качестве mempty и mappend как число 0 и операцию сложения, так и число 1 и операцию умножения. Эта проблема в Haskell решается путем объявления newtype’ов, в случае с числами это соответственно Sum и Product.

Заключение

Дополнительные материалы:

  • Прекрасное объяснение, нафига вообще нужна вся эта возня с моноидами, функторами и так далее;
  • Соответствующая глава в LYH обязательна к прочтению, в ней есть много интересного, что не написано в этом посте;
  • Еще более углубленный материл вы найдете в 10-й главе «Building and Parsing Text» замечательной книги Beginning Haskell;
  • Typeclassopedia — неисчерпаемый источник мудрости о классах типов в Haskell, одна только картинка о связи между ними просветляет;

Помимо названных, в Haskell есть еще много занятных классов типов. Например, Foldable, для всего, что может сворачиваться (fold), Traversable для всего, что можно обойти слева направо, Alternative, представляющий собой моноид над аппликативными функторами (та самая непонятная стрелочка <|>) и другие. Но теперь, когда вы уже окончательно поняли, что в Haskell в принципе нет ничего, кроме типов, классов типов и функций для работы с ними, вы без труда разберетесь с ними самостоятельно. Не так ли?

Метки: , .

Понравился пост? Узнайте, как можно поддержать развитие этого блога.

Также подпишитесь на RSS, Google+, Facebook, ВКонтакте или Twitter.