Что значит сочинять два функтора?

Упражнение 5 раздела Haskell Typeclassopedia Section 3.2 требует подтверждения или контрпримера в заявлении

Состав двух Функторов также является Функтором.

Сначала я подумал, что речь идет о создании методов fmap, определенных двумя отдельными экземплярами Functor, но это на самом деле не имеет смысла, поскольку типы не совпадают до тех пор, пока я могу сказать. Для двух типов f и f' типы fmap будут fmap :: (a -> b) -> f a -> f b и fmap :: (a -> b) -> f' a -> f' b, и это на самом деле не представляется сложным. Итак, что значит сочинять два Functors?

Ответ 1

Functor дает два сопоставления: одно на типах отображения уровня типов для типов (это x в instance Functor x where), и одно на функциях отображения уровня вычислений для функций (это x в fmap = x). Вы думаете о составлении сопоставления на уровне вычислений, но должны думать о составлении сопоставления на уровне типов; например, учитывая

newtype Compose f g x = Compose (f (g x))

Вы можете написать

instance (Functor f, Functor g) => Functor (Compose f g)

? Если нет, то почему нет?

Ответ 2

Речь идет о составе конструкторов типа, таких как [] и Maybe, а не о составе функций типа fmap. Так, например, существует два способа компоновки [] и Maybe:

newtype ListOfMabye a = ListOfMaybe [Maybe a]
newtype MaybeOfList a = MaybeOfList (Maybe [a])

Утверждение о том, что композиция из двух Functors является Functor, означает, что существует шаблонный способ записи экземпляра Functor для этих типов:

instance Functor ListOfMaybe where
    fmap f (ListOfMaybe x) = ListOfMaybe (fmap (fmap f) x) 

instance Functor MaybeOfList where
    fmap f (MaybeOfList x) = MaybeOfList (fmap (fmap f) x)

Фактически платформа Haskell поставляется с модулем Data.Functor.Compose, который дает вам тип Compose, который делает это "бесплатно",

import Data.Functor.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)

Compose особенно полезен с расширением GeneralizedNewtypeDeriving:

{-# LANGUAGE GeneralizedNewtypeDeriving #-}

newtype ListOfMaybe a = ListOfMaybe (Compose [] Maybe a)
   -- Now we can derive Functor and Applicative instances based on those of Compose
   deriving (Functor, Applicative)

Заметим, что композиция из двух Applicative также является Applicative. Поэтому, поскольку [] и Maybe являются Applicative s, то есть Compose [] Maybe и ListOfMaybe. Композиция Applicative - это действительно опрятная техника, которая постепенно становится все более распространенной в наши дни, как альтернатива монадам-трансформаторам для случаев, когда вам не нужна полная мощность монад.

Ответ 3

Здесь действительно полезно подумать о категориальной интерпретации, функтор F: C -> D принимает объекты (значения) и морфизмы (функции) к объектам и морфизмам из категории C к объектам и морфизмам в категории D.

Для второго функтора G : D -> E композиция функторов G . F : C -> E просто превращает кодомен в преобразовании F fmap в область преобразования G fmap. В Haskell это выполняется с небольшим развертыванием newtype.

import Data.Functor

newtype Comp f g a = Comp { unComp :: f (g a) }

compose :: f (g a) -> Comp f g a
compose = Comp

decompose :: Comp f g a -> f (g a)
decompose = unComp

instance (Functor f, Functor g) => Functor (Comp f g) where
  fmap f = compose . fmap (fmap f) . decompose

Ответ 4

Состав двух функций - это когда вы помещаете одну функцию внутри другой функции, например

round (sqrt 23)

Это композиция двух функций round и sqrt. Аналогично, состав двух функторов - это когда вы помещаете один функтор внутри другого функтора, например

Just [3, 5, 6, 2]

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