Ратный труд обертки-композитора
Как известно композиция двух функторов является функтором, причем 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!
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!