Каковы сопряженные пары функторов, соответствующие общим монадам в Хаскелле?

В теории категорий монада может быть построена из двух сопряженных функторов. В частности, если С и D - категории, а F: C → D и G: D → C - сопряженные функторы, в том смысле, что существует биекция

hom (FX, Y) = hom (X, GY)

для каждого X в C и Y в D, то композиция G o F: C → C является монадой.

Одна такая пара сопряженных функторов может быть задана путем фиксации типа b и принятия F и G как

data F b a = F (a,b)
data G b a = G (b -> a)

instance Functor (F b) where
  fmap f (F (a,b)) = F (f a, b)

instance Functor (G b) where
  fmap f (G g) = G (f . g)

и биекция между hom-множествами задается (по модулю конструкторов) путем каррирования:

iso1 :: (F b a -> c) -> a -> G b c
iso1 f = \a -> G $ \b -> f (F (a,b))

iso2 :: (a -> G b c) -> F b a -> c
iso2 g = \(F (a,b)) -> let (G g') = g a in g' b

и в этом случае соответствующая монада

data M b a = M { unM :: b -> (a,b) }

instance Monad (M b) where
    return a    = M (\b -> (a,b))
    (M f) >>= g = M (\r -> let (a,r') = f r in unM (g r') a)

Я не знаю, как должно быть имя этой монады, за исключением того, что это похоже на монаду-читателю, которая несет в себе часть переписываемой информации ( изменить: точки dbaupp в комментариях, что это монада State.)

Итак, монада State может быть "разложена" как пара сопряженных функторов F и G, и мы могли бы написать

State = G . F

До сих пор так хорошо.

Теперь я пытаюсь выяснить, как разложить другие общие монады на пары присоединенных функторов - например, Maybe, [], Reader, Writer, Cont - но я не могу выяснить, какие пары сопряженных функторов мы можем "разложить" на них.

Единственный простой случай - это монада Identity, которую можно разложить на любую пару функторов F и G таких, что F обратна к G (в частности, вы могли бы просто возьмите F = Identity и G = Identity).

Может ли кто-нибудь пролить свет?

Ответ 1

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

Проблема состоит в том, что Haskell Functor не является общим функтором, а является эндо-функтором в категории Haskell. Поэтому нам нужно что-то другое (AFAIK) для представления функторов между другими категориями:

{-# LANGUAGE FunctionalDependencies, KindSignatures #-}
import Control.Arrow
import Control.Category hiding ((.))
import qualified Control.Category as C
import Control.Monad

class (Category c, Category d) => CFunctor f c d | f -> c d where
    cfmap :: c a b -> d (f a) (f b)

Обратите внимание, что если взять -> для c и d, мы получим эндо-функтор категории Haskell, который является только типом fmap:

cfmap :: (a -> b) -> (f a -> f b)

Теперь у нас есть явный класс типа, представляющий функторы между двумя заданными категориями c и d, и мы можем выразить два сопряженных функтора для данной монады. Левый сопоставляет объект a только a и отображает морфизм f на (return .) f:

-- m is phantom, hence the explicit kind is required
newtype LeftAdj (m :: * -> *) a = LeftAdj { unLeftAdj :: a }
instance Monad m => CFunctor (LeftAdj m) (->) (Kleisli m) where
    cfmap f = Kleisli $ liftM LeftAdj . return . f . unLeftAdj
    -- we could also express it as liftM LeftAdj . (return .) f . unLeftAdj

Правильный сопоставляет объект a объекту m a и отображает морфизм g в join . liftM g или эквивалентно (=<<) g:

newtype RightAdj m a = RightAdj { unRightAdj :: m a }
instance Monad m => CFunctor (RightAdj m) (Kleisli m) (->) where
    cfmap (Kleisli g) = RightAdj . join . liftM g . unRightAdj
    -- this can be shortened as RightAdj . (=<<) g . unRightAdj

(Если кто-нибудь знает лучший способ выразить это в Haskell, пожалуйста, дайте мне знать.)

Ответ 2

Maybe происходит от свободного функтора в категорию заостренных множеств и забывчивый функтор назад
[] исходит из свободного функтора в категорию моноидов и забывчивый функтор назад

Но ни одна из этих категорий не является подкатегориями Hask.

Ответ 3

Как вы заметили, каждая пара сопряженных функторов порождает монаду. Обратное также верно: каждая монада возникает таким образом. Фактически, он делает это двумя каноническими способами. Одна из них - конструкция Клейсли, которую описывает Петр; другая - конструкция Эйленберга-Мура. Действительно, Клейсли является исходным таким образом, а Е-М - терминальным, в подходящей категории пар сопряженных функторов. Они были обнаружены независимо в 1965 году. Если вы хотите получить подробные сведения, я настоятельно рекомендую видео Catsters.