与Haskell中常见的monad相对应的伴随函子对是什么？

Question

在类别理论中,monad可以用两个伴随的仿函数构造.特别是,如果C和D是类别而 F:C - > D和G:D - > C是伴随函子,在某种意义上说是双射

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

对于每个X在Ç和ÿ在d然后该组合物克邻FⅧ: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-sets之间的双射(模数构造函数):

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在评论中指出这是Statemonad. )

所以State单子可以"分解"为一对伴随函子的F和G,我们可以写

State = G . F

到现在为止还挺好.

---

现在,我试图找出如何分解等常见单子到对伴随函子的-例如Maybe,[],Reader,Writer,Cont-但我无法弄清楚伴随函子的对,我们可以"分解"他们进入的.

唯一的简单情况似乎是Identity单子,它可以被分解为任意一对函子的F和G,使得F是逆G(在特别,可以只取F = Identity和G = Identity).

任何人都能解释一下吗？

Answer 1

您正在寻找的是Kleisli类别.最初开发它是为了表明每个monad都可以用两个伴随的仿函数构造.

问题是Haskell Functor不是通用函子,它是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到just,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中表达这一点的更好方法,请告诉我.)

Answer 2

• Maybe 来自免费的仿函数,进入尖头套装和健忘的仿函数
• [] 来自免费的functor进入monoids类别和健忘的functor背面

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

Answer 3

正如你所观察到的,每一对伴随的仿函数都会产生一个monad.反之亦然:每个monad都以这种方式出现.事实上,它以两种规范的方式实现.一个是Kleisli建筑Petr描述的; 另一个是Eilenberg-Moore建筑.实际上,Kleisli是最初的这种方式,而EM是最终的方式,在一对合适的伴随仿函数中.他们是在1965年独立发现的.如果你想要细节,我强烈推荐Catsters视频.