应用程序组成，单子不

应用程序组成，单子不。

上面的陈述是什么意思? 什么时候一个比另一个更好？

14878 次浏览
小开

如果有应用程序 A1和 A2，那么类型 data A3 a = A3 (A1 (A2 a))也是应用程序(您可以以通用方式编写这样的实例)。

另一方面，如果有单子 M1和 M2，那么类型 data M3 a = M3 (M1 (M2 a))就不一定是单子(对于组合 >>=或 join没有合理的通用实现)。

One example can be the type [Int -> a] (here we compose a type constructor [] with (->) Int, both of which are monads). You can easily write

app :: [Int -> (a -> b)] -> [Int -> a] -> [Int -> b]
app f x = (<*>) <$> f <*> x

And that generalizes to any applicative:

app :: (Applicative f, Applicative f1) => f (f1 (a -> b)) -> f (f1 a) -> f (f1 b)

但是没有合理的定义

join :: [Int -> [Int -> a]] -> [Int -> a]

如果你不相信这一点，考虑一下这个表达:

join [\x -> replicate x (const ())]

返回的列表的长度必须在提供整数之前设置为一成不变，但是它的正确长度取决于提供的整数。因此，对于这种类型，不存在正确的 join函数。

小开

不幸的是，我们真正的目标，单子的组成，是相当多的 困难. . 事实上，我们 实际上可以证明，在某种意义上，没有办法 构造具有上述类型的连接函数 这两个单子的操作(见附录的概要 因此，我们可能希望形成一个 组合是否有一些额外的构造连接 两个部分。

构成单子，http://web.cecs.pdx.edu/~mpj/pubs/RR-1004.pdf

小开
最佳答案

如果我们比较一下

(<*>) :: Applicative a => a (s -> t) -> a s -> a t
(>>=) :: Monad m =>       m s -> (s -> m t) -> m t

我们得到了区分这两个概念的线索。(>>=)类型的 (s -> m t)表明，s中的一个值可以决定 m t中计算的行为。单子允许值和计算层之间的干涉。(<*>)操作符不允许这种干扰: 函数和参数计算不依赖于值。真的很疼。比较一下

miffy :: Monad m => m Bool -> m x -> m x -> m x
miffy mb mt mf = do
b <- mb
if b then mt else mf

使用一些效果的结果来决定两个 计算(例如发射导弹和签署停战协定) ，而

iffy :: Applicative a => a Bool -> a x -> a x -> a x
iffy ab at af = pure cond <*> ab <*> at <*> af where
cond b t f = if b then t else f

它利用 ab的值在 价值观中选择两个计算 at和 af，同时进行了这两个计算，可能产生了悲剧性的效果。

一进制版本基本上依赖于 (>>=)的额外功率来从值中选择计算，这一点很重要。然而，支持这种力量使单子难以组成。如果我们试图建立双重约束

(>>>>==) :: (Monad m, Monad n) => m (n s) -> (s -> m (n t)) -> m (n t)
mns >>>>== f = mns >>-{-m-} \ ns -> let nmnt = ns >>= (return . f) in ???

我们已经走到这一步了，但现在我们的层次都混在一起了。我们有一个 n (m (n t))，所以我们需要摆脱外部 n。正如亚历山大 C 所说，我们可以做到这一点，如果我们有一个合适的

swap :: n (m t) -> m (n t)

to permute the n inwards and join it to the other n.

较弱的双重适用更容易定义

(<<**>>) :: (Applicative a, Applicative b) => a (b (s -> t)) -> a (b s) -> a (b t)
abf <<**>> abs = pure (<*>) <*> abf <*> abs

因为层与层之间没有干扰。

相应地，当您真正需要 Monad的额外功率时，以及当您能够摆脱 Applicative所支持的严格计算结构时，最好能够认识到这一点。

顺便说一句，尽管编写单子很困难，但它可能比您需要的要多。类型 m (n v)表示使用 m效应计算，然后使用 n效应计算到 v值，其中 m效应在 n效应开始之前结束(因此需要 swap)。如果你只是想交错 m-效果和 n-效果，那么组成可能是太多的要求！

小开

应用程序组成，单子不。

单子 做组成，但结果可能不是单子。 相反，两个应用程序的组成必然是一个应用程序。 我怀疑最初声明的意图是“适用性构成，而单一性不构成。”换句话说，“ Applicative是封闭的，而 Monad不是。”

小开

分配律解 L: MN-> NM 就够了

to guarantee monadicity of NM. To see this you need a unit and a mult. i'll focus on the mult (the unit is unit_N unitM)

NMNM - l -> NNMM - mult_N mult_M -> NM

这保证了 MN 是一个单子。

然而，当你有分配定律的解时，关键的观察就会发挥作用

l1 : ML -> LM
l2 : NL -> LN
l3 : NM -> MN

thus, LM, LN and MN are monads. The question arises as to whether LMN is a monad (either by

(MN)L -> L(MN) 或者 N (LM)-> (LM) N

我们有足够的结构来制作这些地图。然而，作为 Eugenia Cheng 观察到，我们需要一个六边形条件(相当于 Yang-Baxter 方程的表示)来保证任一结构的一元性。事实上，在六边形条件下，两个不同的单子是一致的。

小开

这里是一些代码，使单子组成通过分配定律的工作。注意，从任意单子到单子 Maybe、 Either、 Writer和 []都有分配定律。另一方面，你不会在 Reader和 State中找到这样的(一般的)分配定律。对于这些，你将需要单子变压器。

 {-# LANGUAGE FlexibleInstances #-}
 

module ComposeMonads where
import Control.Monad
import Control.Monad.Writer.Lazy
 

newtype Compose m1 m2 a = Compose { run :: m1 (m2 a) }
 

instance (Functor f1, Functor f2) => Functor (Compose f1 f2) where
fmap f = Compose . fmap (fmap f) . run
 

class (Monad m1, Monad m2) => DistributiveLaw m1 m2 where
dist :: m2 (m1 a) -> m1 (m2 a)
 

instance (Monad m1,Monad m2, DistributiveLaw m1 m2)
=> Applicative (Compose m1 m2) where
pure = return
(<*>) = ap
 

instance (Monad m1, Monad m2, DistributiveLaw m1 m2)
=> Monad (Compose m1 m2) where
return = Compose . return . return
Compose m1m2a >>= g =
Compose $ do m2a <- m1m2a -- in monad m1
m2m2b <- dist $ do a <- m2a  -- in monad m2
let Compose m1m2b = g a
return m1m2b
-- do ... ::  m2 (m1 (m2 b))
-- dist ... :: m1 (m2 (m2 b))
return $ join m2m2b -- in monad m2
 

instance Monad m => DistributiveLaw m Maybe where
dist Nothing = return Nothing
dist (Just m) = fmap Just m
 

instance Monad m => DistributiveLaw m (Either s) where
dist (Left s) = return $ Left s
dist (Right m) = fmap Right m
 

instance Monad m => DistributiveLaw m [] where
dist = sequence
 

instance (Monad m, Monoid w) => DistributiveLaw m (Writer w) where
dist m = let (m1,w) = runWriter m
in do a <- m1
return $ writer (a,w)
 

liftOuter :: (Monad m1, Monad m2, DistributiveLaw m1 m2) =>
m1 a -> Compose m1 m2 a
liftOuter = Compose . fmap return
 

liftInner :: (Monad m1, Monad m2, DistributiveLaw m1 m2) =>
m2 a -> Compose m1 m2 a
liftInner = Compose . return
小开

Any two applicative functors can be composed and yield another applicative functor. But this does not work with monads. A composition of two monads is not always a monad. For example, a composition of State and List monads (in any order) is not a monad.

此外，一个人一般不能合并两个单子，无论是通过合成或任何其他方法。目前还没有已知的算法或程序将任何两个单子 M、 N组合成一个更大的、合法的单子 T，这样你就可以通过单子态注入 M ~> T和 N ~> T，并满足合理的非简并定律(例如，保证 T不仅仅是一个单位类型，抛弃来自 M和 N的所有效应)。

可以为特定的 M和 N定义一个合适的 T，例如 M = Maybe和 N = State s等等。但是如何定义在单子 M和 N中参数化工作的 T是未知的。函数复合和更复杂的构造都不能正常工作。

结合单子 M和 N的一种方法是首先定义副产物 C a = Either (M a) (N a)。这个 C将是一个函子，但通常不是单子。然后在函数 C上构造一个空单子(Free C)。结果是一个单子，能够代表的影响 M和 N结合。然而，它是一个大得多的单子，也可以代表其他效应; 它比仅仅 M和 N效应的组合大得多。此外，自由单子将需要“运行”或“解释”，以提取任何结果(并且单子定律只有在“运行”之后才能得到保证)。由于空闲单子可能会在“运行”之前在内存中构建非常大的结构，因此将会有运行时损失和内存大小损失。如果这些缺点不是很明显，那么免费单子就是一条出路。

组合单子的另一种方法是将一个单子的变换器应用到另一个单子上。但是没有一种算法可以定义单子(例如，哈斯克尔的类型和代码)并生成相应的转换器的类型和代码。

至少有4种不同类型的单子，其变压器构造完全不同，但有规律的方式(组成-内部，组成-外部，基于辅助单子，产品单子)。其他一些单子不属于这些“常规”类中的任何一个，并且以某种方式定义了转换器“ ad hoc”。

Distributive laws exist only for composed monads. It is misleading to think that any two monads M, N for which one can define some function M (N a) -> N (M a) will compose. In addition to defining a function with this type signature, one needs to prove that certain laws hold. In many cases, these laws do not hold.

有些单子甚至有两个不等效的变换器，一个定义为“常规”变换器，一个定义为“特别”变换器。一个简单的例子是单位单子 Id a = a; 它具有常规变压器 IdT m = m(“组合”)和不规则的“特别”变压器: IdT2 m a = forall r. (a -> m r) -> m r(m上的共密度单子)。

一个更复杂的例子是“ selector monad”: Sel q a = (a -> q) -> a。这里 q是一个固定的类型，而 a是单子 Sel q的主要类型参数。这个单子有两个变压器: SelT1 m a = (m a -> q) -> m a(内部组合)和 SelT2 m a = (a -> m q) -> m a(特别)。

完整的细节在《函数式编程的科学》一书的第14章中有所阐述


提交答案