除了IO之外,是否存在没有对应的monad transformer的monad?

70
到目前为止,我遇到的每个可以表示为数据类型的单子(Monad)都有一个相应的单子变换器(Monad Transformer),或者可以有一个。是否存在不能有单子变换器的单子?或者所有的单子都有对应的变换器呢?
通过“对应于单子m的变换器t”,我的意思是“t Identity”同构于“m”。当然,它还满足单子变换器定律和“tn是任何单子n的单子”。
我想看到每个单子都有一个证明(最好是建设性的证明),或者一个特定单子的例子没有一个(带有证明)。我对更多面向Haskell的答案以及(范畴)理论方面的答案都很感兴趣。
作为后续问题,是否存在一个单子m,它具有两个不同的变换器t1和t2?也就是说,“t1 Identity”同构于“t2 Identity”和“m”,但是存在一个单子n,使得“t1 n”不同构于“t2 n”。
(IO和ST具有特殊语义,因此我在这里不考虑它们,并完全忽略它们。让我们只关注可以使用数据类型构造的“纯”单子。)

5
“ST”是另一个明显的例子,但它也违反了“纯”单子限制。 - GS - Apologise to Monica
2
@bennofs 是的,但不仅仅是单子变换器定律,可能是 T 满足它们,但对于某些单子 n,类型 T n 无法成为一个单子。例如 ListT 只对一些单子(非交换单子)不满足单子定律,然而,还有另一个正确的 [] 变换器 - Petr
4
“这显然是IO”的异常列表基本上是无限的。比如,有STM。但是还有每个在IO内部工作的自定义monad。许多库都提供了这样的功能。 - Carl
2
我觉得需要一个精确的定义来解释类型“拥有单子”的含义。为什么列表既“拥有”ListT又拥有ListTDoneRight?这可以通过引用自由单子变换器来回答吗?例如,T具有Monad T,使得T' Identity ~ T,但存在一个n,使得T' n不再实例化Monad,或者T'不是MonadTrans。虽然可能会有许多这样的T'(正如ListT所指出的那样),但对于任何给定的T,所有这些都在考虑之中。 - J. Abrahamson
9
几乎所有的单子(Monad)都可以表示为某个函子(Functor)的自由单子(Free monad),因此它们也应该拥有自由单子变换器(Free monad transformer)。参考 https://dev59.com/SmUq5IYBdhLWcg3wQ-Xk。 - Cirdec
显示剩余18条评论
4个回答

21

我赞同 @Rhymoid 的观点,我认为所有的单子都有两个(!!)变换器。我的构造方法有些不同,也远没有那么完整。我想把这个草图带到证明中去,但我认为我要么缺乏技能/直觉,要么它可能相当复杂。

由于Kleisli,每个单子(m)可以分解成两个函子F_kG_k,使得F_k是左伴随于G_k,并且m同构于G_k * F_k(这里*是函子组合)。此外,由于伴随,F_k * G_k形成一个余单子。

我声称,定义为t_mk n = G_k * n * F_kt_mk是一个单子变换器。显然,t_mk Id = G_k * Id * F_k = G_k * F_k = m。为这个函子定义return并不难,因为F_k是一个“指针”函子,而定义join应该是可能的,因为来自余单子F_k * G_kextract可以用于将类型(t_mk n * t_mk n) a = (G_k * n * F_k * G_k * n * F_k) a的值约简为类型G_k * n * n * F_k,然后通过joinn进一步约简。

我们必须要小心一些,因为F_kG_k不是Hask上的Endofunctor。因此,它们不是标准Functor类型类的实例,也不能像上面展示的那样直接与n组合。相反,在组合之前,我们必须将n“投影”到Kleisli范畴中,但我认为m中的return提供了这种“投影”。

我认为您也可以使用Eilenberg-Moore单子分解来进行此操作,得到m = G_em * F_emtm_em n = G_em * n * F_em,并且对于liftreturnjoin也有类似的构造,但是它们与来自余共范畴F_em * G_emextract有类似的依赖关系。


1
一个非常好的想法。你能否添加一个例子,用这种方式推导出一些著名的单子变换器? - Petr
1
https://dev59.com/T2445IYBdhLWcg3wytIU#4702513 从一个伴随构建了State monad。如果你想从该伴随构建StateT,至少有三种可能的方法来组合函子,并对应不同的StateT s IO定义:StateT s IO a ~ s -> (IO a, s)(r * w * m),StateT s IO a ~ IO (s -> (a, s))(m * r * w)和StateT s IO a ~ s -> IO (a, s)(r * m * w)。最后一种正确的构造方式是我提议从伴随中构建转换器的方式。 - Boyd Stephen Smith Jr.
2
授予此答案赏金,因为它是唯一一个没有被证明错误的严谨答案。不过,更详细的阐述会更棒 :) - user824425
1
我有一些时间来尝试详细说明你的答案。所有看起来都很好,但有趣的是到目前为止我还没有能够实现MonadTrans中的lift。有什么想法吗? - Petr
1
看到 EM 和 K 结构,我的印象是我们没有单子变换器的存在证明。EM 和 K 结构给出了生成给定单子的伴随范畴中的初始和最终对象 - 没问题。当转换为 Haskell 代码时,它们对应于“内部”或“外部”的单子变换器。例如,ReaderT 是“外部”的,因为 ReaderT z m a = Reader z (m a),而 EitherT 是“内部”的,因为 EitherT z m a = m (Either z a)。只有“内部”和“外部”变换器中的一个是有效的。理论并没有说出哪一个! - winitzki
显示剩余17条评论

3
这是一个模糊的、不太确定的回答。
可以把Monad看作命令式语言的接口。通过return将纯值注入该语言,通过>>=将语言片段拼合起来。Monad法则确保“重构”语言的各个部分按预期工作。Monad提供的任何额外操作都可以被视为其“操作”。
Monad Transformer是解决“可扩展效果”问题的一种方法。如果我们有一个将Monad m转换为Monad Transformer t,那么我们可以说,通过t语言m被扩展了,具有额外的操作。Identity monad是没有效果/操作的语言,因此将t应用于Identity只会得到一个仅包含t提供的操作的语言。
因此,如果我们从“注入、拼接和其他操作”模型的角度来看Monad,那么我们可以使用Free Monad Transformer重新制定它们。即使IO monad也可以用这种方式转换成transformer。唯一的问题是你可能需要一些方法在某个点上剥掉transformer堆栈中的层,唯一明智的做法是将IO置于堆栈底部,以便可以在那里执行操作。

2

之前,我认为找到了一些明确定义的单子示例,没有转换器,但是这些示例是不正确的。

Either a (z -> a) 的转换器是 m (Either a (z -> m a)),其中m是任意的外部单子。 (a -> n p) -> n a 的转换器是 (a -> t m p) -> t m a,其中t m是单子n的转换器。

  1. 自由指向单子。

此示例的单子类型构造器 L 定义如下:

  type L z a  = Either a (z -> a)

这个monad的意图是通过显式的pure值(Left x)来丰富普通的reader monad z -> a。普通reader monad的pure值是一个常数函数pure x = _ -> x。但是,如果我们给定一个类型为z -> a的值,我们将无法确定这个值是否是一个常数函数。用L z a,pure值可以明确地表示为Left x。用户现在可以在L z a上进行模式匹配,并确定给定的单调值是纯净的还是有影响的。除此之外,monad L z与reader monad完全相同。
Monad实例:
  instance Monad (L z) where
     return x = Left x
     (Left x) >>= f = f x
     (Right q) >>= f = Right(join merged) where
        join :: (z -> z -> r) -> z -> r
        join f x = f x x -- the standard `join` for Reader monad
        merged :: z -> z -> r
        merged = merge . f . q -- `f . q` is the `fmap` of the Reader monad
        merge :: Either a (z -> a) -> z -> a 
        merge (Left x) _ = x
        merge (Right p) z = p z

这个单子是更一般的构造的一个特定案例,(Monad m) => Monad (L m),其中L m a = Either a (m a)。这个构造通过添加显式的值(Left x)来装饰给定的单子,以便用户现在可以在L m>上进行模式匹配,以决定该值是否为纯值。在所有其他方面,L m表示与单子相同的计算效果。

L m的单子实例与上面的示例几乎相同,除了需要使用单子的joinfmap,并定义了辅助函数merge

    merge :: Either a (m a) -> m a
    merge (Left x) = return @m x
    merge (Right p) = p

我检查了单子的法则,发现对于任意单子m,都适用于L m

这个构造方法给出了给定单子m上的自由指向函子。这种构造方法保证了单子的自由指向函子也是一个单子。

自由指向单子的转换器定义如下:

  type LT m n a = n (Either a (mT n a))

其中mT是monad m的monad transformer(需要知道m的类型)。

  1. 另一个例子:

type S a = (a -> Bool) -> Maybe a

这个monad出现在“搜索monads”的背景下(链接)。Jules Hedges的论文也提到了搜索monad,更一般地,形式为

 type Sq n q a = (a -> n q) -> n a

对于给定的单子n和固定类型q。上面的搜索monad是选择monad的一个特例,其中n a = Maybe a并且q = ()。Hedges的论文声称(没有证明,但他后来使用Coq证明了它),Sq是monad变换器,适用于monad (a -> q) -> a。
然而,monad (a -> q) -> a还有另一个monad变换器(m a -> q) -> m a,属于“外部组成”的类型。这与在问题Is this property of a functor stronger than a monad?中探讨的“刚性”属性有关。即(a -> q) -> a是一个刚性monad,并且所有刚性monad都有“组成外部”的monad变换器。
一般来说,转换后的monad本身不会自动具有monad变换器。也就是说,一旦我们取一些外来的monad m并将某些monad变换器t应用于它,我们就获得了一个新的monad tm,这个monad没有变换器:给定一个新的外来monad n,我们不知道如何用monad tm转换n。如果我们知道monad m的变换器mT,我们可以先用mT转换n,然后用t转换结果。但是如果我们没有monad m的变换器,我们就卡住了:没有构造可以仅凭t的知识为任意外来monad m创建monad tm的变换器。
然而,在实践中,所有明确定义的monad都有明确定义的变换器,因此不会出现这个问题。
JamesCandy的答案表明,对于任何monad(包括IO?!),都可以编写表示相应monad变换器的(通用但复杂的)类型表达式。即,您首先需要Church编码您的monad类型,使该类型看起来像一个continuation monad,然后定义其monad变换器,就好像是针对continuation monad一样。但我认为这是不正确的-它并没有给出一个通用的产生monad变换器的方法。
将类型a的Church编码意味着写下类型
 type ca = forall r. (a -> r) -> r

根据Yoneda引理,类型caa完全同构。到目前为止,我们所做的只是通过引入量化的类型参数forall r使类型变得更加复杂。

现在让我们Church-编码一个基本的单子L

 type CL a = forall r. (L a -> r) -> r

到目前为止,我们还没有取得任何成果,因为CL aL a完全等价。

现在假设CL a是一个连续的单子(实际上并不是!),并通过用m r替换结果类型r来编写单子变换器,就像它是一个连续的单子变换器一样:

 type TCL m a = forall r. (L a -> m r) -> m r

这被称为L的“Church编码单子变换器”。但这似乎是不正确的。我们需要检查以下属性:
  • TCL m对于任何外部单子m和任何基本单子L都是合法的单子
  • m a -> TCL m a是合法的单子态射
第二个属性成立,但我认为第一个属性失败了,换句话说,TCL m不是任意单子m的单子。也许有些单子m可以实现这一点,而其他单子则不能。我无法找到一个普遍的单子实例,使其对应于任意基本单子L
另一种证明TCL m通常不是单子的方法是注意到对于任何类型构造器mforall r. (a -> m r) -> m r确实是一个单子。用CM表示此单子。现在,TCL m a = CM (L a)。如果TCL m是一个单子,它将意味着CM可以与任何单子L组合,并产生一个合法的单子CM (L a)。然而,一个非平凡的单子CM(特别是一个不等价于Reader的单子)与所有单子L组合的可能性极小。单子通常不会在没有严格的进一步限制的情况下组合。
这不起作用的一个具体例子是读取器单子。考虑L a = r -> am a = s -> a,其中rs是一些固定类型。现在,我们想要考虑“Church编码单子变换器”forall t. (L a -> m t) -> m t。我们可以使用Yoneda引理简化此类型表达式。
 forall t. (x -> t) -> Q t  = Q x

(对于任何函子)并获得
 forall t. (L a -> s -> t) -> s -> t
 = forall t. ((L a, s) -> t) -> s -> t
 = s -> (L a, s)
 = s -> (r -> a, s)

所以这是TCL m a的类型表达式。如果TCL是一个单子变换器,那么P a = s -> (r -> a, s)将是一个单子。但是可以明确地检查到这个P实际上不是一个单子(无法实现满足定律的returnbind)。
即使这样做有用(即假设我在声称TCL m通常不是单子方面犯了错误的情况下),这种构造仍然存在某些缺点:
  • 它在外部单子m方面不是函子(即不是协变的),因此我们不能像解释转换后的自由单子到另一个单子或合并两个单子变换器一样做事情,如此处所述Is there a principled way to compose two monad transformers if they are of different type, but their underlying monad is of the same type?
  • forall r的存在使得该类型相当复杂,难以推理,并可能导致性能下降(请参见“Church编码被认为是有害的”论文)和堆栈溢出(因为Church编码通常不是安全的)
  • 用于身份基础单子(L = Id)的Church编码单子变换器不能产生未修改的外部单子:T m a = forall r. (a -> m r) -> m r,这与m a不同。实际上,鉴于单子m,很难弄清楚那个单子是什么。
例如,考虑外部单子m a = Maybe a并尝试理解类型forall r. (a -> Maybe r) -> Maybe r实际上意味着什么。我无法简化此类型或找到关于此类型执行的操作(因为它是一个单子,所以必须表示某种“效果”)以及如何使用这种类型的好的解释。
  • Church编码的单子变换器与标准已知的单子变换器(例如ReaderTWriterTEitherTStateT等)不等价。
不清楚还有多少其他单子变换器存在,在什么情况下会使用一个或另一个变换器。
我相信Search单子提供了这样一个例子。在帖子中的一个问题是找到一个明确的例子,其中单子m有两个变换器t1t2,使得对于一些外来单子n,单子t1 nt2 n不等价。
 type Search a = (a -> p) -> a

其中p是一个固定类型。

变压器是

 type SearchT1 n a = (a -> n p) -> n a
 type SearchT2 n a = (n a -> p) -> n a

我检查了SearchT1 nSearchT2 n对于任何单子n都是合法的。我们有lifting n a -> SearchT1 n an a -> SearchT2 n a,它们通过返回常函数(只返回给定的n a,忽略参数)来工作。显然,SearchT1 IdentitySearchT2 Identity等价于Search

SearchT1SearchT2之间的主要区别在于,SearchT1n方面不具器,而SearchT2则具有器。这可能会对“运行”(“解释”)转换的单子产生影响,因为通常我们希望能够将一个解释程序n a -> n' a提升为一个“运行程序”SearchT n a -> SearchT n' a。 这只有用SearchT2可能实现。

在续延单子和余密度单子的标准单子变换器中也存在类似的不足:它们在外部单子中不具备函子性。


我写的是否正确并不是重点。我确信我的答案来源于这个问题,它比那个问题早发布了https://math.stackexchange.com/questions/1560793/can-every-monad-give-rise-to-a-monad-transformer,而且我没有资格理解它。也许我不应该插手这个讨论。 - James Candy

1

我的解决方案利用了Haskell术语的逻辑结构等。

我将右Kan扩展视为monad transformer的可能表示形式。众所周知,右Kan扩展是极限,因此它们应该作为任何感兴趣的对象的通用编码。对于monadic functors F和M,我查看了MF沿F的right Kan扩展。

首先,我证明了一个引理,“rolling lemma:” 一个procomposed functor到Right kan extension可以被卷入其中,为任何functors F、G和H提供映射F(Ran G H)-> Ran G(FH)。

利用这个引理,我计算了Ran F(MF)的monadic join,需要distributive law FM -> MF。如下所示:

Ran F(MF) . Ran F(MF) [rolling lemma] =>
  Ran F(Ran F(MF)MF) [insert eta] =>
  Ran F(Ran F(MF)FMF) [gran] =>
  Ran F(MFMF) [apply distributive law] =>
  Ran F(MMFF) [join Ms and Fs] =>
  Ran F(MF).

这个构造看起来很有趣的一点是,它可以同时适用于函子 F 和 M 的提升,具体如下:
(1) F [lift into codensity monad] =>
  Ran F F [procompose with eta] =>
  Ran F(MF).

(2) M [Yoneda lemma specialized upon F-] =>
  Ran F(MF).

我还调查了正确的Kan扩展Ran F(FM)。它似乎比较好,可以在不使用分配律的情况下实现单子性,但对其提升的函子要求更高。我确定只有在以下条件下它才能提升单子函子:
1) F是单子的。
2) F |- U,此时它允许提升F ~> Ran U(UM)。这可用于状态单子的上下文中来“设置”状态。
3) 在某些条件下M,例如当M具有分配律时。

“monadified”的确切定义是什么?拥有严格列表单子的目的是什么?你能否给出一个例子,比如拥有实例Monad []如何导致相应单子变换器的定义和实例?删减消除又如何帮助到达这个目标? - Petr
@JamesCandy 看了你的 pastebin 代码一会儿,我仍然不清楚它到底是做什么的。Lift g f 似乎需要一个 Functor f,而不是我所期望的 Monad f。因此,实际上,您正在使用现有的单子 g 和任意函子 f 构建一个新的单子 Lift g f?另外,请问您能解释一下 f ((:.) f g) 是什么意思吗?我无法理解这个语法。 - winitzki
@JamesCandy 我再次查看了你的 Church 编码单子变换器公式。你所声称的是,对于任何单子 L a,类型构造函数 (forall b. L a -> m b) -> m b) 表示 L 变换单子 m。确实,它是一个单子,而且 L am a 都可以被提升到它上面。这非常有趣,因为它为任意单子 L 的单子变换器提供了一般的类型公式。然而,当我设置 L = Maybem a = r -> a 并简化时,我没有得到标准的单子变换器 MaybeT 应用于 Reader 单子。这是一个不同的单子变换器吗? - winitzki
通过我提出的形式 x:: Ran f(f:.g),可以通过运行Ran x return来计算组合f:.g中的一个项。在您最近的评论中提出的形式也是如此,因为可以进行变量实例化b = L a,并再次应用return以获得m(L a)中的一个术语,在这种情况下等于r->Maybe a。经过进一步的挖掘,我发现形式(forall b. (L a -> f b) -> f b)与Church编码的自由单子变换器非常密切相关;如果是这样,这就可以解释为什么可以获得一个变换器。 - James Candy
@JamesCandy,你对于 Ran F (M F) 的单子 join 构建似乎需要一个关键步骤,即使用分配律 F M -> M F 将 M F M F 替换为 M F。然而,你没有检查单子的法则是否成立。我认为一旦你要求结合律法则,你会发现你需要 M F 本身就是一个单子。分配律 F M -> M F 并不能自动保证 M F 的结合律法则。我认为如果我们假设足够的法则来从 M F M F -> M F 中得到一个合法的 join,我们将发现 M F 已经是一个单子变换器了;不需要 Ran。 - winitzki
显示剩余6条评论

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接