37

在范畴论中，一个单子可以由两个伴随函子构成。特别是，如果C和D是类别，并且 F : C --> D和G : D --> C是伴随函子，在某种意义上是双射

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

对于C中的每个X和D中的Y，则组合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)

并且通过currying给出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)

我不知道这个 monad 的名字应该是什么，除了它似乎是一个带有可覆盖信息的 reader monad（编辑： dbaupp 在评论中指出这是Statemonad. )

所以State单子可以被“分解”为一对伴随函子Fand G，我们可以写

State = G . F

到现在为止还挺好。

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

唯一简单的情况似乎是Identitymonad，它可以分解为任何一对仿函数，F并且与（特别是，你可以只取and ）相反。GFGF = IdentityG = Identity

任何人都可以解释一下吗？

4

3 回答 3

18

您正在寻找的是Kleisli 类别。最初开发它是为了表明每个 monad 都可以由两个伴随函子构成。

问题是 HaskellFunctor不是通用函子，它是 Haskell 类别中的 endo-functor。所以我们需要一些不同的东西（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 类别的 endo-functor，它就是 的类型fmap：

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

现在我们有明确的类型类来表示两个给定类别之间的函子c，d并且我们可以表达给定 monad 的两个伴随函子。左边将一个对象映射a到 justa并将态射映射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 更好地表达这一点，请告诉我。）

于 2012-12-18T18:57:12.357 回答
17
  • Maybe来自自由函子进入尖集范畴和健忘函子返回
  • []来自自由函子到幺半群和健忘函子的范畴

但这些类别都不是 Hask 的子类别。

于 2012-12-18T20:06:28.130 回答
8

正如你所观察到的，每一对伴随函子都会产生一个单子。反之亦然：每一个单子都是这样产生的。事实上，它以两种典型的方式做到这一点。一种是 Petr 描述的 Kleisli 结构；另一个是 Eilenberg-Moore 结构。事实上，Kleisli 是最初的这种方式，而 EM 是终端方式，属于合适的伴随函子对类别。它们是在 1965 年独立发现的。如果您想了解详细信息，我强烈推荐Catsters 视频。

于 2013-01-10T11:02:16.470 回答