Haskell中常见单子对应的伴随函子对是什么？ [英] What are the adjoint functor pairs corresponding to common monads in Haskell?

问题描述

在分类理论中，monad可以由两个伴随函数构成。特别是，如果 C 和 D 是类别并且 F：C - > D 和 G：D - > C 是伴随函数，在某种意义上是双射投影b / b
$ b

hom（FX，Y）= hom（X ，GY） 中的每个 X 和 中的 D 中的 Y ，则组合 G o F：C - > C 是一个单子。

---

通过修改类型 b 并取 F 和 G 为

 数据F ba = F（a，b）
 data G ba = G（b-> a）
 
实例Functor（F b）其中
 fmap f（F a，b））= F（fa，b）
 
实例Functor（G b）其中
 fmap f（G g）= G（f。g）
  

并且hom-sets之间的双映射通过柯里格给出（模构造函数）：



  iso1 ::（F ba  - > 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）） - >在这种情况下，相应的monad是 $ b  

p>



  data M ba = M {unM :: b  - > （a，b）} 
 
实例Monad（M b）其中
返回a = M（\ b  - >（a，b））
（M f） （g r'）a）
  

= g（M，r'）= fr >



我不知道这个monad的名字应该是什么，除了它看起来像是一个读写器monad，它带有一些超写信息（编辑： dbaupp在评论中指出这是 State monad。）

State monad可以被分解为伴随函数对 F 和 G ，我们可以写出

  State = G。 F 
  

到目前为止，这么好。

---

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

唯一的简单的情况似乎是 Identity monad，它可以分解为任何一对函子 F 和 G ，使得 F 与 G 相反（特别是，您可以以 F =身份和 G =身份）。

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

wikipedia.org/wiki/Kleisli_category\">克莱斯利类别。它最初是为了显示每个monad可以由两个伴随函数构造而成。

问题在于Haskell Functor 不是泛型函数，它是Haskell类中的内函子。所以我们需要一些不同的东西（AFAIK）来表示其他类别之间的函数：

$ $ p $ { - ＃LANGUAGE FunctionalDependencies，KindSignatures＃ - }
导入Control.Arrow
导入Control.Category隐藏（（。））
将限定的Control.Category导入为C
导入Control.Monad

class类别c，类别d）=> CFunctor f c d | f - > c d其中
cfmap :: c a b - > d（fa）（fb）


注意，如果我们将 - > 对于 c 和 d ，我们得到了Haskell类的内函数，它只是 fmap 类型：



  cfmap ::（a  - > b） - > （fa  - > fb）
  

现在我们有显式类型类来表示两个给定类别之间的函子 c 和 d ，我们可以表示给定单子的两个伴随函子。左侧将一个对象 a 映射为 a ，并映射一个态射 f 到（return。）f ：

   - m是幻影，因此显式类型是必需的
 newtype LeftAdj（m :: *  - > *）a = LeftAdj {unLeftAdj :: a} 
实例Monad m => CFunctor（LeftAdj m）（ - >）（Kleisli m）其中
 cfmap f = Kleisli $ liftM LeftAdj。返回。 F 。 unLeftAdj 
  - 我们也可以将它表示为liftM LeftAdj。 （回报）f。 unLeftAdj 
  

正确的映射一个对象 a 将 g 映射到 join，以映射 g 。 liftM g 或等同于（= <）g ：



  newtype RightAdj ma = RightAdj {unRightAdj :: ma} 
 instance Monad m => CFunctor（RightAdj m）（Kleisli m）（ - >）其中
 cfmap（Kleisli g）= RightAdj。加入。 liftM g。 unRightAdj 
  - 这可以缩短为RightAdj。 （=<）g。 unRightAdj 
  

（如果有人知道如何在Haskell中表达这一点，请告诉我。）


In category theory, a monad can be constructed from two adjoint functors. In particular, if C and D are categories and F : C --> D and G : D --> C are adjoint functors, in the sense that there is a bijection

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

for each X in C and Y in D then the composition G o F : C --> C is a monad.

---

One such pair of adjoint functors can be given by fixing a type b and taking F and G to be

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)

and the bijection between hom-sets is given (modulo constructors) by 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

in which case the corresponding monad is

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)

I don't know what the name for this monad should be, except that it seems to be something like a reader monad that carries around a piece of over-writeable information (edit: dbaupp points out in the comments that this is the State monad.)

So the State monad can be "decomposed" as the pair of adjoint functors F and G, and we could write

State = G . F

So far, so good.

---

I'm now trying to figure out how to decompose other common monads into pairs of adjoint functors - for example Maybe, [], Reader, Writer, Cont - but I can't figure out what the pairs of adjoint functors that we can "decompose" them into are.

The only simple case seems to be the Identity monad, which can be decomposed into any pair of functors F and G such that F is inverse to G (in particularly, you could just take F = Identity and G = Identity).

Can anyone shed some light?

解决方案

What you're looking for is Kleisli category. It was originally developed to show that every monad can be constructed from two adjoint functors.

The problem is that Haskell Functor is not a generic functor, it's an endo-functor in the Haskell category. So we need something different (AFAIK) to represent functors between other categories:

{-# 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)

Notice that if we take -> for both c and d we get an endo-functor of the Haskell category, which is just the type of fmap:

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

Now we have explicit type class that represents functors between two given categories c and d and we can express the two adjoint functors for a given monad. The left one maps an object a to just a and maps a morphism f to (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

The right one maps an object a to object m a and maps a morphism g to join . liftM g, or equivalently to (=<<) 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

(If anybody know a better way how to express this in Haskell, please let me know.)

这篇关于Haskell中常见单子对应的伴随函子对是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！