应用程序组成，单子不组成

如果我们比较类型

(<*>) :: 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 的值之间进行选择，同时执行了这两个计算，可能会产生悲剧性的效果。

monadic 版本本质上依赖于 (>>=) 的额外功能来从值中选择计算，这可能很重要。然而，支持这种权力使得单子难以组合。如果我们尝试构建“双重绑定”

(>>>>==) :: (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。正如 Alexandre C 所说，如果我们有合适的

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

将 n 向内排列并将 join 排列到另一个 n。

较弱的“双重应用”更容易定义

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

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

相应地，当您真正需要 Monad 的额外功能以及何时可以摆脱 Applicative 支持的刚性计算结构时，这很好。

顺便提一下，尽管编写 monad 很困难，但它可能比你需要的要多。 m (n v) 类型表示使用 m-effects 计算，然后使用 n-effects 计算 v-value，其中 m-effects 在 n-effects 开始之前完成（因此需要swap)。如果您只想将 m-效果与 n-效果交错，那么组合可能太难了！

---

应用程序组成，单子不组成。

单子做组合，但结果可能不是单子。相反，两个应用程序的组合必然是一个应用程序。我怀疑原始陈述的意图是“应用性构成，而单子性不构成”。改写为“Applicative 在作文下是封闭的，而 Monad 不是。”

---

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

另一方面，如果您有 monad M1 和 M2，则类型 data M3 a = M3 (M1 (M2 a)) 不一定是 monad（组合的 >>= 或 join 没有合理的通用实现）。

一个例子可以是类型 [Int -> a]（这里我们用 (->) Int 组成一个类型构造函数 []，它们都是单子）。您可以轻松编写

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

这可以推广到任何应用程序：

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 函数。

---

不幸的是，我们真正的目标，单子的组合，是相当困难的。 .. 事实上，我们实际上可以证明，在某种意义上，仅使用两个 monad 的操作是无法构造具有上述类型的连接函数的（参见附录中的证明大纲）。因此，我们可能希望形成一个组合的唯一方法是，如果有一些额外的结构连接这两个组件。

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

---

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

以保证 NM 的一元性。要看到这一点，您需要一个单元和一个 mult。我将专注于 mult（单位是 unit_N unitM）

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

这并不能保证 MN 是一个单子。

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

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

因此，LM、LN 和 MN 是单子。问题在于 LMN 是否是一个单子（通过

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

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

---

任何两个应用函子都可以组合并产生另一个应用函子。但这不适用于单子。两个单子的组合并不总是单子。例如，State 和 List 单子的组合（以任何顺序）不是单子。

此外，一般来说，无论是通过组合还是通过任何其他方法，都不能组合两个单子。没有已知的算法或程序可以将任意两个单子 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 将是一个函子，但通常不是一个 monad。然后在仿函数 C 上构造一个自由单子 (Free C)。结果是一个能够表示 M 和 N 组合效果的 monad。然而，它是一个更大的单子，也可以代表其他效果；它远大于 M 和 N 的效果组合。此外，为了提取任何结果，需要“运行”或“解释”免费的 monad（并且只有在“运行”之后才能保证 monad 法则）。会有运行时损失和内存大小损失，因为自由单子在“运行”之前可能会在内存中构建非常大的结构。如果这些缺点不显着，那么免费的单子就是要走的路。

组合 monad 的另一种方法是获取一个 monad 的转换器并将其应用于另一个 monad。但是没有算法方法来定义一个 monad（例如，Haskell 中的类型和代码）并产生相应转换器的类型和代码。

至少有 4 种不同类别的 monad，它们的转换器以完全不同但规则的方式构造（内部组合、外部组合、基于附加的 monad、product monad）。其他一些 monad 不属于这些“常规”类中的任何一个，并且以某种方式将转换器定义为“临时”。

分配律只存在于组合的单子中。认为可以定义某个函数 M (N a) -> N (M a) 的任何两个单子 M、N 将组成是一种误导。除了使用这种类型签名定义函数外，还需要证明某些定律成立。在许多情况下，这些法律并不成立。

甚至有些单子有两个不等价的转换器；一个以“常规”方式定义，一个以“临时”方式定义。一个简单的例子是身份单子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 是 monad Sel q 的主要类型参数。这个 monad 有两个转换器：SelT1 m a = (m a -> q) -> m a (composed-inside) 和 SelT2 m a = (a -> m q) -> m a (ad hoc)。

完整的细节在“函数式编程的科学”一书的第 14 章中制定。 https://github.com/winitzki/sofp 或 https://leanpub.com/sofp/

---

这是一些通过分配律工作的代码制作单子组合。请注意，从任何单子到单子 Maybe、Either、Writer 和 [] 都有分配律。另一方面，您不会在 Reader 和 State 中找到这样的（一般）分配律。对于这些，您将需要 monad 转换器。

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

---