deniok: (ухмыляюсь)
[personal profile] deniok
Как известно композиция двух функторов является функтором, причем fmap для этой композиции - это композиция fmap'ов:
GHCi> (fmap . fmap) (^2) [Just 3,Just 5,Nothing]
[Just 9,Just 25,Nothing]
Левый fmap протаскивает свой аргумент (fmap (^2)) через конструкторы списка, а дальше оставшийся fmap протаскивает свой аргумент (^2) через конструкторы Maybe.

Можно это выразить более универсально, введя обертку Compose :: (* -> *) -> (* -> *) -> * -> *:
newtype Compose f g a = Compose { getCompose :: f (g a) }

instance (Functor f, Functor g) => Functor (Compose f g) where
  fmap f (Compose x) = Compose $ (fmap . fmap) f x
Тогда предыдущий пример выглядит так:
GHCi> (getCompose . fmap (^2) . Compose) [Just 3,Just 5,Nothing]
[Just 9,Just 25,Nothing]

Ровно таким же образом устроена композиция двух Foldable (это Foldable) и двух Traversable (это Traversable):
GHCi> (foldMap . foldMap) Product [Just 3,Just 5,Nothing]
Product {getProduct = 15}
GHCi> (traverse . traverse) (\x->[x+10,x+20]) [Just 3,Just 5,Nothing]
[[Just 13,Just 15,Nothing],[Just 13,Just 25,Nothing],[Just 23,Just 15,Nothing],[Just 23,Just 25,Nothing]]
В терминах обертки Compose:
instance (Foldable f, Foldable g) => Foldable (Compose f g) where
  foldMap f (Compose x) = (foldMap . foldMap) f x

instance (Traversable f, Traversable g) => Traversable (Compose f g) where
  traverse f (Compose x) = Compose <$> (traverse . traverse) f x
При этом предыдущие примеры выглядят так:
GHCi> (foldMap Product . Compose) [Just 3,Just 5,Nothing]
Product {getProduct = 15}
GHCi> (fmap getCompose . traverse (\x->[x+10,x+20]) . Compose) [Just 3,Just 5,Nothing]
[[Just 13,Just 15,Nothing],[Just 13,Just 25,Nothing],[Just 23,Just 15,Nothing],[Just 23,Just 25,Nothing]]
Отличия в вызовах связаны исключительно с распаковкой результата: для fmap мы снимали обертку вызывая getCompose, в свертках упаковка результата в Compose отсутствует, поэтому не делаем ничего. Для траверсов эта упаковка "уезжает" во внутренние списки; чтобы от нее избавится нужен fmap, протаскивающий getCompose через внешний, аппликативный список.

Все три интерфейса (Functor, Foldable и Traversable) не "портят" структуру контейнера. Более точно, структура либо сохраняется (Functor и, часто, Traversable, список во всех примерах сохраняет свою трехэлементность), либо полностью исчезает (Foldable и, иногда, Traversable). Вот пример полного исчезнавения для traverse:
GHCi> (traverse . traverse) (\_ -> []) [Just 3,Just 5,Nothing]
[]
GHCi> (traverse . traverse) Left [Just 3,Just 5,Nothing]
Left 3
Этот побочный эффект дает нам аппликативный функтор, навешанный на стрелку; он позволяет частично выжить значениям, но не траверсируемому контейнеру, как структуре.

Аппликативный функтор - самый простой вычислительный контекст, в котором изменение структуры контейнера - штатная операция:
GHCi> [id, (+10)] <*> [3,5,7]
[3,5,7,13,15,17]
GHCi> Just (+10) <*> Nothing
Nothing
GHCi> Just (+10) <*> Just 3
Just 13
Является ли композиция аппликативных функторов аппликативным функтором? Да! Имеется замечательная функция liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c, которая позволяет поднимать любую функцию двух аргументов в аппликативный функтор. Но сам оператор (<*>) :: Applicative f => f (a -> b) -> f a -> f b является функцией двух аргументов, и, следовательно, может быть поднят в следующий аппликативный функтор:
> :t liftA2 (<*>)
liftA2 (<*>) :: (Applicative f1, Applicative f) =>
     f (f1 (a -> b)) -> f (f1 a) -> f (f1 b)
Таким образом мы можем соединить аппликативные эффекты двух контейнерных типов:
GHCi> liftA2 (<*>) [Just id, Just (+10)] [Just 3,Just 5,Nothing]
[Just 3,Just 5,Nothing,Just 13,Just 15,Nothing]
GHCi> liftA2 (<*>) [Nothing, Just (+10)] [Just 3,Just 5,Nothing]
[Nothing,Nothing,Nothing,Just 13,Just 15,Nothing]
И большего числа, трех, например,
GHCi> (liftA2 . liftA2) (<*>) [Just (Right (+10)), Just (Left "Ops1")] [Just (Left "Ops2"), Just (Right 5), Nothing]
[Just (Left "Ops2"),Just (Right 15),Nothing,Just (Left "Ops1"),Just (Left "Ops1"),Nothing]
Теперь понятно, как написать представителя класса типов Applicative для обертки Compose:
instance (Applicative f, Applicative g) => Applicative (Compose f g) where
  pure = Compose $ pure . pure
  Compose f <*> Compose x = Compose $ liftA2 (<*>) f x
Проверяем:
GHCi> getCompose $ Compose [Just id,Just (+10)] <*> Compose [Just 3,Just 5,Nothing]
[Just 3,Just 5,Nothing,Just 13,Just 15,Nothing]
GHCi> getCompose $ Compose [Nothing,Just (+10)] <*> Compose [Just 3,Just 5,Nothing]
[Nothing,Nothing,Nothing,Just 13,Just 15,Nothing]
И даже так:
GHCi> fmap getCompose . getCompose $ (Compose . fmap Compose) [Just (Right (+10)),Just (Left "Ops1")] <*> (Compose . fmap Compose) [Just (Left "Ops2"),Just (Right 5),Nothing]
[Just (Left "Ops2"),Just (Right 15),Nothing,Just (Left "Ops1"),Just (Left "Ops1"),Nothing]
Страшно? Тогда то же самое, но по буквам:
GHCi> cmp2 = Compose . fmap Compose
GHCi> :t cmp2
cmp2 :: Functor f => f (f1 (g a)) -> Compose f (Compose f1 g) a
GHCi> getCmp2 = fmap getCompose . getCompose
GHCi> :t getCmp2
getCmp2 :: Functor f => Compose f (Compose f1 g) a -> f (f1 (g a))
GHCi> getCmp2 $ cmp2 [Just (Right (+10)),Just (Left "Ops1")] <*> cmp2 [Just (Left "Ops2"),Just (Right 5),Nothing]
[Just (Left "Ops2"),Just (Right 15),Nothing,Just (Left "Ops1"),Just (Left "Ops1"),Nothing]


А вот композиция монад - это монада? К сожалению, в общем случае нет. Но, к счастью, при некоторых довольно общих условиях - да! Но об этом в следующей серии. Stay tuned!
From:
Anonymous( )Anonymous This account has disabled anonymous posting.
OpenID( )OpenID You can comment on this post while signed in with an account from many other sites, once you have confirmed your email address. Sign in using OpenID.
User
Account name:
Password:
If you don't have an account you can create one now.
Subject:
HTML doesn't work in the subject.

Message:

 
Notice: This account is set to log the IP addresses of everyone who comments.
Links will be displayed as unclickable URLs to help prevent spam.

Profile

deniok: (Default)
deniok

April 2017

S M T W T F S
      1
23 45678
9101112131415
16171819202122
23242526272829
30      

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 22nd, 2017 10:13 pm
Powered by Dreamwidth Studios