haskell - Haskell 中常见的 monad 对应的伴随仿函数对是什么？

Question

在范畴论中，单子(monad)可以由两个伴随仿函数构造而成。特别是，如果C和D是类别，并且F : C --> D和G : D --> C 是伴随仿函数，即存在双射

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

对于C中的每个X和D中的Y，则组合G o F: C --> C 是一个单子(monad)。

<小时/>

可以通过固定类型 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-sets 之间的双射是通过柯里化(Currying)给出的(模构造函数):

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

在这种情况下对应的 monad 是

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)

我不知道这个 monad 的名字应该是什么，除了它似乎是一个类似阅读器 monad 的东西，它携带着一段可重写的信息(编辑: dbaupp 点在评论中指出这是 State monad。)

因此，State 单子(monad)可以“分解”为一对伴随仿函数 F 和 G，我们可以这样写

State = G . F

到目前为止，一切顺利。

<小时/>

我现在正在尝试弄清楚如何将其他常见单子(monad)分解为成对的伴随仿函数 - 例如 Maybe、[]、Reader code>、Writer、Cont - 但我无法弄清楚我们可以将它们“分解”成的伴随仿函数对是什么。

唯一简单的情况似乎是Identity monad，它可以分解为任何一对仿函数F和G，这样F 与 G 相反(特别是，您可以只采用 F = Identity 和 G = Identity)。

有人可以透露一些信息吗？

Answer 1

您正在寻找的是 Kleisli category 。它最初的开发是为了表明每个单子(monad)都可以由两个伴随仿函数构建。

问题是 Haskell Functor不是通用仿函数，它是 Haskell 类别中的内仿函数。因此，我们需要一些不同的东西(据我所知)来表示其他类别之间的仿函数:

{-# 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我们可以表达给定单子(monad)的两个伴随仿函数。左边映射一个对象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 中表达这一点的更好方法，请告诉我。)