之前,我认为找到了一些明确定义的单子示例,没有转换器,但是这些示例是不正确的。
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
的转换器。
- 自由指向单子。
此示例的单子类型构造器 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
merged :: z -> z -> r
merged = merge . f . q
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
的单子实例与上面的示例几乎相同,除了需要使用单子的join
和fmap
,并定义了辅助函数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的类型)。
- 另一个例子:
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引理,类型ca
与a
完全同构。到目前为止,我们所做的只是通过引入量化的类型参数forall r
使类型变得更加复杂。
现在让我们Church-编码一个基本的单子L
:
type CL a = forall r. (L a -> r) -> r
到目前为止,我们还没有取得任何成果,因为CL a
与L 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
通常不是单子的方法是注意到对于任何类型构造器
m
,
forall 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 -> a
和
m a = s -> a
,其中
r
和
s
是一些固定类型。现在,我们想要考虑“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
实际上不是一个单子(无法实现满足定律的return
和bind
)。
即使这样做有用(即假设我在声称TCL m
通常不是单子方面犯了错误的情况下),这种构造仍然存在某些缺点:
例如,考虑外部单子m a = Maybe a
并尝试理解类型forall r. (a -> Maybe r) -> Maybe r
实际上意味着什么。我无法简化此类型或找到关于此类型执行的操作(因为它是一个单子,所以必须表示某种“效果”)以及如何使用这种类型的好的解释。
- Church编码的单子变换器与标准已知的单子变换器(例如
ReaderT
、WriterT
、EitherT
、StateT
等)不等价。
不清楚还有多少其他单子变换器存在,在什么情况下会使用一个或另一个变换器。
我相信Search
单子提供了这样一个例子。在帖子中的一个问题是找到一个明确的例子,其中单子m
有两个变换器t1
和t2
,使得对于一些外来单子n
,单子t1 n
和t2 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 n
和SearchT2 n
对于任何单子n
都是合法的。我们有lifting n a -> SearchT1 n a
和n a -> SearchT2 n a
,它们通过返回常函数(只返回给定的n a
,忽略参数)来工作。显然,SearchT1 Identity
和SearchT2 Identity
等价于Search
。
SearchT1
和SearchT2
之间的主要区别在于,SearchT1
在n
方面不具器,而SearchT2
则具有器。这可能会对“运行”(“解释”)转换的单子产生影响,因为通常我们希望能够将一个解释程序n a -> n' a
提升为一个“运行程序”SearchT n a -> SearchT n' a
。 这只有用SearchT2
可能实现。
在续延单子和余密度单子的标准单子变换器中也存在类似的不足:它们在外部单子中不具备函子性。
T
满足它们,但对于某些单子n
,类型T n
无法成为一个单子。例如ListT
只对一些单子(非交换单子)不满足单子定律,然而,还有另一个正确的[]
变换器。 - PetrSTM
。但是还有每个在IO内部工作的自定义monad。许多库都提供了这样的功能。 - CarlT
具有Monad T
,使得T' Identity ~ T
,但存在一个n
,使得T' n
不再实例化Monad
,或者T'
不是MonadTrans
。虽然可能会有许多这样的T'
(正如ListT所指出的那样),但对于任何给定的T
,所有这些都在考虑之中。 - J. Abrahamson