伴随函子确定monad变换器，但是在哪里提升？ [英] Adjoint functors determine monad transformers, but where's lift?

问题描述

我对这里描述的构造感兴趣，以从伴随函子中确定monad变换器。以下是一些总结基本思想的代码：

  { - ＃LANGUAGE MultiParamTypeClasses＃ - } 
 
 import Control.Monad 
 
 newtype Three gfma = Three {getThree :: g（m（fa））} 
 
 class（Functor f，Functor g）=>伴随f g，其中
 counit :: f（g a） - > a 
 unit :: a  - > g（f a）
 
实例（伴随f g，Monad m）=> Monad（三g f m）其中
返回=三。 fmap返回。单元
m>> = f =三$ fmap（>> = counit.fmap（getThree.f））（getThree m）
 
实例（伴随fg，Monad m） =>应用（三g f m）其中
 pure =返回
（*）= ap 
 
实例（伴随f g，Monad m）=> Functor（Three g f m）其中
 fmap =（*）。假设 Adjoint（（，）s）（（ - > b） ）s），三个（（ - >）s）（（，）s）相当于 StateT s 。
 
 
 
非常酷，但我对一些事情感到困惑： 
 
 
 
 
 
我们如何将monadic  ma 升级为monadic  Three gfma ？对于三（（ - >）s）（（，，s））的具体情况，当然显而易见的是如何做到这一点，但似乎希望有一个配方适用于任何三gf ，前提是 Adjoint fg 。换句话说，似乎应该有一个类似的 lift ，其定义只需要 unit ， counit ，并且返回和>> =  。但我似乎无法找到一个（我见过使用 sequence  的定义，但这看起来有点像作弊，因为它需要 f 为 Traversable ）。
 
 
 
 
对于这个问题，我们如何升级 ga 转换为三个gfma （提供 Adjoint fg ）？同样，对于三（（ - >）s）（（，）s）的具体情况，很明显如何做到这一点，但我想知道是否有只有 unit ， counit 的模拟获得，以及输入monad的返回和>> = 。
 
 
 
 
解决方案 
  lift ， Benjamin Hodgson的答案，设置为： 
 
 
 
 
  lift mx = let mgfx = fmap单位mx 
 gmfx = distributeR mgfx 
 in三个gmfx 
  - 或
 lift =三个。 distributeR。 fmap单元
  
 
 
众所周知，这不是唯一可行的策略我们可以在这里使用：
 
 $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ in三gmfx 
  - 或
 lift =三。 fmap sequenceL。单位
  

因此 Traversable href =https://hackage.haskell.org/package/adjunctions-4.4/docs/Control-Monad-Trans-Adjoint.html#t:AdjointT =nofollow noreferrer> Edward Kmett对应的 MonadTrans 实例来源。那么，这个问题就变成了否定，就像你说的那样，欺骗。我可以认为它不是。

我们可以调整本杰明关于分配的游戏计划，并尝试找到左边的伴奏是否是 Traversable 。查看 Data.Functor .Adjunction 显示我们有一个相当不错的工具箱可用：

  unabsurdL： ：连接fu => f Void  - > Void 
 cozipL :: Adjunction f u => f（或者b） - > （f a）（f b）
 splitL :: Adjunction f u => f a  - > （a，f（））
 unsplitL :: Functor f => a  - > f（） - > fa 
  

爱德华告诉我们 unabsurdL 和 cozipL 见证了[a]左伴随必须有人居住，[而且]左伴随必须恰好有一个元素居住。然而，这意味着 splitL 恰好对应于表征 Traversable 函子的形状和内容分解。如果我们再添加一个事实： splitL 和 unsplitL 是相反的，则执行序列立即出现：



  sequenceL ::（Adjunction fu，Functor m）=> f（m a） - > m（f a）
 sequenceL =（\（mx，fu） - > fmap（\ x  - > unsplitL x fu）mx）。 splitL 
  

（请注意，不能超过 Functor 被要求为 m ，正如对于只能容纳一个值的可遍历容器所预期的那样。）

所缺少的这一点验证了 lift 的两个实现是等价的。这并不难，只是有点费劲。简而言之，这里的 distributeR 和 sequenceR 定义可以简化为：

  distributeR = \mgx  - > 
 leftAdjunct（\ fa  - > fmap（\ gx  - > rightAdjunct（const gx）fa）mgx）（）
 sequenceL = 
 rightAdjunct（\ mx  - > leftAdjunct （\fu-> fmap（\ x  - > fmap（const x）fu）mx）（））
  

我们想要显示 distributeR。 fmap unit = fmap sequenceL。单元。经过几轮简化后，我们得到：

  distributeR。 fmap unit = \mgx  - > 
 leftAdjunct（\ fa  - > fmap（\ gx  - > rightAdjunct（const（unit gx））fa）mgx）（）
 fmap sequenceL。 unit = \mx  - > 
 leftAdjunct（\fu-> fmap（\ x  - > fmap（const x）fu）mx）（）
  

我们可以通过选择 \fu - >来显示这些内容。 fmap（\ x - > fmap（const x）fu）mx - 第二个右手边的 leftAdjunct - 并滑动 rightAdjunct unit = counit。 fmap unit = id 进入它：

  \fu  - > fmap（\ x  - > fmap（const x）fu）mx 
 \fu  - > fmap（\ x  - > fmap（const x）fu）mx 
 \fu  - > fmap（\ x  - >（counte。fmap unit。fmap（const x））fu）mx 
 \fu  - > fmap（\ x  - > rightAdjunct（unit。const x）fu）mx 
 \fu  - > fmap（\ x  - > rightAdjunct（const（unit x））fu）mx 
  -  Sans变量重命名，与
  -  \ fa  - > fmap（\ gx  - > rightAdjunct（const（unit gx））fa）mgx 
  

是 Traversable 通往您的 MonadTrans 的路线与 Distributive one，并且担心它 - 包括 Control.Monad.Trans.Adjoint 文档中提到的那些 - 不应再让任何人感到困扰。

PS：值得注意的是，这里提出的 lift 的定义可以拼写为：

  lift =三。 leftAdjunct sequenceL 
  

也就是说， lift 是 sequenceL 通过连接同构发送。此外，从...

  leftAdjunct sequenceL = distributeR。 fmap单元
  

...如果我们应用 rightAdjunct 双方，我们得到...

$ p $ sequenceL = rightAdjunct（distributeR。fmap unit）


...如果我们在左边编写 fmap（fmap counit）我们最终得到：

  distributeR = leftAdjunct（fmap counit。sequenceL）
  

因此 distributeR 和 sequenceL 可以相互确定。

I'm intrigued by the construction described here for determining a monad transformer from adjoint functors. Here's some code that summarizes the basic idea:

{-# LANGUAGE MultiParamTypeClasses #-}

import           Control.Monad

newtype Three g f m a = Three { getThree :: g (m (f a)) }

class (Functor f, Functor g) => Adjoint f g where
  counit :: f (g a) -> a
  unit   :: a -> g (f a)

instance (Adjoint f g, Monad m) => Monad (Three g f m) where
  return  = Three . fmap return . unit
  m >>= f = Three $ fmap (>>= counit . fmap (getThree . f)) (getThree m)

instance (Adjoint f g, Monad m) => Applicative (Three g f m) where
  pure  = return
  (<*>) = ap

instance (Adjoint f g, Monad m) => Functor (Three g f m) where
  fmap = (<*>) . pure

Given that Adjoint ((,) s) ((->) s), Three ((->) s) ((,) s) appears equivalent to StateT s.

Very cool, but I am puzzled by a couple things:

• How can we upgrade a monadic m a into a monadic Three g f m a? For the specific case of Three ((->) s) ((,) s), it's of course obvious how to do this, but it seems desirable to have a recipe that works for any Three g f provided that Adjoint f g. In other words, it seems like there should be an analog of lift whose definition only requires unit, counit, and the return and >>= of the input monad. But I cannot seem to find one (I have seen a definition using sequence, but this seems a bit like cheating since it requires f to be Traversable).

• For that matter, how can we upgrade g a into a Three g f m a (provided Adjoint f g)? Again, for the specific case of Three ((->) s) ((,) s) it's obvious how to do this, but I'm wondering if there's an analog of gets that only requires unit, counit, and the return and >>= of the input monad.

解决方案

lift, in Benjamin Hodgson's answer, is set up as:

lift mx = let mgfx = fmap unit mx
              gmfx = distributeR mgfx
          in Three gmfx
-- or
lift = Three . distributeR . fmap unit

As you know, that is not the only plausible strategy we might use there:

lift mx = let gfmx = unit mx
              gmfx = fmap sequenceL gfmx
          in Three gmfx
-- or
lift = Three . fmap sequenceL . unit

Whence the Traversable requirement for Edward Kmett's corresponding MonadTrans instance originates. The question, then, becomes whether relying on that is, as you put it, "cheating". I am going to argue it is not.

We can adapt Benjamin's game plan concerning Distributive and right adjoints and try to find whether left adjoints are Traversable. A look at Data.Functor.Adjunction shows we have a quite good toolbox to work with:

unabsurdL :: Adjunction f u => f Void -> Void
cozipL :: Adjunction f u => f (Either a b) -> Either (f a) (f b)
splitL :: Adjunction f u => f a -> (a, f ())
unsplitL :: Functor f => a -> f () -> f a

Edward helpfully tells us that unabsurdL and cozipL witness that "[a] left adjoint must be inhabited, [and that] a left adjoint must be inhabited by exactly one element", respectively. That, however, means splitL corresponds precisely to the shape-and-contents decomposition that characterises Traversable functors. If we add to that the fact that splitL and unsplitL are inverses, an implementation of sequence follows immediately:

sequenceL :: (Adjunction f u, Functor m) => f (m a) -> m (f a)
sequenceL = (\(mx, fu) -> fmap (\x -> unsplitL x fu) mx) . splitL

(Note that no more than Functor is demanded of m, as expected for traversable containers that hold exactly one value.)

All that is missing at this point is verifying that both implementations of lift are equivalent. That is not difficult, only a bit laborious. In a nutshell, the distributeR and sequenceR definitions here can be simplified to:

distributeR = \mgx ->
    leftAdjunct (\fa -> fmap (\gx -> rightAdjunct (const gx) fa) mgx) ()   
sequenceL =
    rightAdjunct (\mx -> leftAdjunct (\fu -> fmap (\x -> fmap (const x) fu) mx) ())

We want to show that distributeR . fmap unit = fmap sequenceL . unit. After a few more rounds of simplification, we get:

distributeR . fmap unit = \mgx ->
    leftAdjunct (\fa -> fmap (\gx -> rightAdjunct (const (unit gx)) fa) mgx) ()
fmap sequenceL . unit = \mx ->
    leftAdjunct (\fu -> fmap (\x -> fmap (const x) fu) mx) ()

We can show those are really the same thing by picking \fu -> fmap (\x -> fmap (const x) fu) mx -- the argument to leftAdjunct in the second right-hand side -- and slipping rightAdjunct unit = counit . fmap unit = id into it:

\fu -> fmap (\x -> fmap (const x) fu) mx
\fu -> fmap (\x -> fmap (const x) fu) mx
\fu -> fmap (\x -> (counit . fmap unit . fmap (const x)) fu) mx
\fu -> fmap (\x -> rightAdjunct (unit . const x) fu) mx
\fu -> fmap (\x -> rightAdjunct (const (unit x)) fu) mx
-- Sans variable renaming, the same as
-- \fa -> fmap (\gx -> rightAdjunct (const (unit gx)) fa) mgx

The takeaway is that the Traversable route towards your MonadTrans is just as secure as the Distributive one, and concerns about it -- including the ones mentioned by the Control.Monad.Trans.Adjoint documentation -- should no longer trouble anyone.

P.S.: It is worth noting that the definition of lift put forward here can be spelled as:

lift = Three . leftAdjunct sequenceL

That is, lift is sequenceL sent through the adjunction isomorphism. Additionally, from...

leftAdjunct sequenceL = distributeR . fmap unit

... if we apply rightAdjunct on both sides, we get...

sequenceL = rightAdjunct (distributeR . fmap unit)

... and if we compose fmap (fmap counit) on the left of both sides, we eventually end up with:

distributeR = leftAdjunct (fmap counit . sequenceL)

So distributeR and sequenceL are interdefinable.

这篇关于伴随函子确定monad变换器，但是在哪里提升？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！