单子函子是应用函子，但在应用函子的定义中，单子类型类在哪里？

Question

应用函子是一个幺半范畴：

mappend :: f         -> f   -> f
$       ::  (a -> b) ->   a ->   b
<*>     :: f(a -> b) -> f a -> f b

但是我在Applicative类型类的定义中没有看到有关Monoid的参考，你能告诉我为什么吗？

定义：

定义：

class Functor f => Applicative (f :: * -> *) where
  pure :: a -> f a
  (<*>) :: f (a -> b) -> f a -> f b
  GHC.Base.liftA2 :: (a -> b -> c) -> f a -> f b -> f c
  (*>) :: f a -> f b -> f b
  (<*) :: f a -> f b -> f a
  {-# MINIMAL pure, ((<*>) | liftA2) #-}

尽管在这个定义中没有提到结构单子（structural Monoid），但当你进行操作时

> ("ab",(+1)) <*> ("cd", 5) 
>("abcd", 6)

在实现 Applicative 的这个实例时，可以清楚地看到使用了结构单子“(,) String”的用法。

另一个示例展示了使用“结构单子（Structural Monoid）”：

Prelude Data.Monoid> (2::Integer,(+1)) <*> (1::Integer,5)

<interactive>:35:1: error:
    • Could not deduce (Monoid Integer) arising from a use of ‘<*>’
      from the context: Num b
        bound by the inferred type of it :: Num b => (Integer, b)
        at <interactive>:35:1-36
    • In the expression: (2 :: Integer, (+ 1)) <*> (1 :: Integer, 5)
      In an equation for ‘it’:
          it = (2 :: Integer, (+ 1)) <*> (1 :: Integer, 5)

- Nicolas Henin

---

f 的类型不正确，无法成为 Monoid。 - Lee

“单范畴函子”一词不能分为“一个幺半群和一个函子”的两个部分解释。它指的是作用于单范畴并保持该范畴的单性结构的函子；同样，“单范畴”也是一个不可分割的术语。 - Daniel Wagner

参见：单子函子的定义、应用函子作为单子函子和具有不同单子结构的松弛单子函子。可能应该是后两者之一的重复，但不确定哪一个更有帮助？ - Daniel Wagner

“Monoid” 并不能涵盖所有可以在 Haskell 中表达的单子，而只能涵盖普通类型（也就是那些具有 * 种类的东西，正如 Lee 所暗示的那样）。 - duplode

它表达在特定的Applicative实例声明中，即instance Monoid a => Applicative ((,) a)；而该实例声明中的Monoid约束与Applicative作为概念中的"monoidal-functor-ness"没有关系。 - Daniel Wagner

Answer 1

“Monoidal functor”所指的单子并不是值级单子，即Monoid单子。而是一种类型级单子。具体来说，它是一个乏味的积单子。

type Mempty = ()
type a <> b = (a,b)

你可能会注意到这不是严格意义上的单子，只有在你将((a,b),c)和(a,(b,c))视为相同类型时才是。它们确实是同构的。

要理解这与Applicative或单子函子有什么关系，我们需要用其他术语来描述这个类。

class Functor f => Monoidal f where
  pureUnit :: f Mempty
  fzip :: f a -> f b -> f (a<>b)

-- an even more “general nonsense”, equivalent formulation is
-- upure :: Mempty -> f Mempty
-- fzipt :: (f a<>f b) -> f (a<>b)
-- i.e. the functor maps a monoid to a monoid (in this case the same monoid).
-- That's really the mathematical idea behind this all.

IOW

class Functor f => Monoidal f where
  pureUnit :: f ()
  fzip :: f a -> f b -> f (a,b)

使用 Monoidal 定义标准的通用实例 , 定义一个 Applicative 类也同样简单。

---

关于 ("ab",(+1)) <*> ("cd", 5)：这与一般的 Applicative 没有太大关系，只与特定的 writer applicative 相关。该实例如下：

instance Monoid a => Monoidal ((,) a) where
  pureUnit = (mempty, ())
  fzip (p,a) (q,b) = (p<>q, (a,b))

- leftaroundabout

---

分类单子群只在同构意义下是可交换的，所以这没问题。 - n. m.

我经常发现很难为f a -> f b -> f(a,b)组合子（或其非柯里化版本）选择一个名称（或运算符符号）进行讨论。 fzip并不太糟糕--实际上，我最终可能会采用它。 - duplode

@duplode 嗯，当我编写受限制的Applicative类时，我对这些名称进行了很多思考。（在那里，我实际上必须使用非柯里化和类别不可知的签名，这使得它变得更加尴尬。） - leftaroundabout

这实际上是一种乘法概念，其中您对 f 进行因式分解，这可能是 <*> 中 * 的来源...实际上，该因式分解操作是我之前提到的函子结构上单子群的应用...“这与 Applicative 没有太多关系”，@leftaroundabout，我不同意这种说法，在那个上下文中的函子是（a，_），然后您需要提供一种使用（，）和 a 进行因式分解的方法...这就是为什么当您为元组实现应用程序时，a 需要成为一个单子群的原因。 - Nicolas Henin

请翻译以下有关编程的内容，从英语到中文。只返回翻译后的文本：并查看这个问题：https://dev59.com/5lcO5IYBdhLWcg3w-V30 - Nicolas Henin

Answer 2

也许你要找的是这个幺半群。

newtype AppM f m = AppM (f m) deriving Show

instance (Applicative f, Monoid m) => Monoid (AppM f m) where
  mempty                      = AppM (pure mempty)
  mappend (AppM fx) (AppM fy) = AppM (pure mappend <*> fx <*> fy)

如下评论所述，可以在reducers库中找到它，并以Ap的名称呈现。 它对于Applicative非常重要，因此让我们来详细了解一下。

特别注意，由于()是一个微不足道的Monoid，AppM f ()也是一个Monoid。这就是潜在在Applicative f后面潜藏的Monoid。

我们本可以坚持要将Monoid（f（））作为Applicative的超类，但那样会使事情变得混乱。

> mappend (AppM [(),()]) (AppM [(),(),()])
AppM [(),(),(),(),(),()]

Applicative []的底层单子结构是自然数的乘法，而列表的“显而易见”的单子结构是连接，它专门用于自然数的加法。 为了理解发生了什么，可以考虑那些在 Abbott、Altenkirch 和 Ghani 的依赖类型意义下恰好是容器的 Applicatives。我们很快就能在 Haskell 中使用这些了，我假装未来已经到来。

data (<|) (s :: *)(p :: s -> *) (x :: *) where
  (:<|:) :: pi (a :: s) -> (p a -> x) -> (s <| p) x

数据结构 (s <| p) 的特征是：

• 形状 s 描述容器的外观。
• 位置 p 告诉你对于给定的形状，在哪里可以放置数据。

上述类型表明，为这样的结构提供数据意味着选择一个形状，然后用数据填充所有位置。

[] 的容器表示是 Nat <| Fin，其中

data Nat = Z | S Nat
data Fin (n :: Nat) where
  FZ :: Fin (S n)
  FS :: Fin n -> Fin (S n)

为了使 Fin n 拥有恰好 n 个值。也就是说，列表的形状是它的 长度，这告诉你需要多少元素来填充列表。

你可以通过取 f () 来查找 Haskell Functor f 的形状。通过使数据变得微不足道，位置就不重要了。在 Haskell 中通用地构建位置的 GADT 实际上更加困难。

参数性告诉我们，容器之间的多态函数是

forall x. (s <| p) x -> (s' <| p') x

必须提供：

• 一个函数 f :: s -> s'，将输入形状映射到输出形状
• 一个函数 g :: pi (a :: s) -> p' (f a) -> p a，将（对于给定的输入形状）输出位置映射回将来自哪个输入位置的输出元素。

morph f g (a :<|: d) = f a :<|: (d . g a)

(私下里，我们这些接受了基本Hancock培训的人也认为“形状”就是“命令”，“位置”就是“有效响应”。那么，容器之间的同态就恰好是“设备驱动程序”。但我离题了。)

沿着类似的思路，使一个容器成为Applicative需要什么？首先，

pure :: x -> (s <| p) x

这等同于

pure :: (() <| Const ()) x -> (s <| p) x

必须由此提供

f :: () -> s   -- a constant in s
g :: pi (a :: ()) -> p (f ()) -> Const () a  -- trivial

其中f = const neutral对一些内容保持不变。

neutral :: s

现在，关于什么呢？

(<*>) :: (s <| p) (x -> y) -> (s <| p) x -> (s <| p) y

再次强调，参数化告诉我们两件事。首先，计算输出形状的唯一有用数据是两个输入形状。我们必须有一个函数

outShape :: s -> s -> s

其次，我们唯一的方法将输出位置填充为 y 是从第一个输入中选择一个位置找到函数 `x -> y'，然后在第二个输入中选择一个位置获取其参数。

inPos :: pi (a :: s)(b :: s) -> p (outShape a b) -> (p a, p b)

也就是说，我们总是能够确定一对输入位置，它们决定了输出位置。

应用规律告诉我们，neutral 和 outShape 必须遵守幺半群律，并且，我们可以按如下方式提升幺半群：

mappend (a :<|: f) (b :<|: g) = outShape a b :<|: \ z ->
  let (x, y) = inPos a b z
  in  mappend (f x) (g y)

这里还有更多要说的，但为此我需要对容器上的两个操作进行对比。

组合

(s <| p) . (s' <| p')  =  ((s <| p) s') <| \ (a :<|: f) -> Sigma (p a) (p' . f)

其中Sigma是依赖对的类型。

data Sigma (p :: *)(q :: p -> *) where
  Pair :: pi (a :: p) -> q a -> Sigma p q

这究竟是什么意思？

• 您选择外部形状
• 您为每个外部位置选择内部形状
• 复合位置是一个外部位置和一个适合于该位置的内部形状的组合

或者，用汉考克语说：

• 您选择外部命令
• 在选择内部命令之前，您可以等待看到外部响应
• 复合响应是对外部命令的响应，后跟由您的策略选择的内部命令的响应

或者更直白地说：

• 当您创建列表的列表时，内部列表可以具有不同的长度

Monad的join将组合展开。它背后潜藏着的不仅是形状上的单子，还有一个积分运算符。

join :: ((s <| p) . (s <| p)) x -> (s <| p) x

需要的

integrate :: (s <| p) s -> s

使用自由单子可以得到策略树，您可以使用一个命令的结果来选择剩余的策略，就好像您正在与1970年代的电传打字机进行交互。

同时...

张量

两个容器的张量（也是由汉考克提出的）由以下公式给出：

(s <| p) >< (s' <| p')  =  (s, s') <| \ (a, b) -> (p a, p' b)

这是选取两个形状的概念，一个位置由一对位置组成，每个形状有一个位置。

• 或者
• 选择两个命令，而不看任何响应
• 那么，响应就是一对响应

或者

• [] >< [] 是矩形矩阵的类型：‘内部’列表必须具有相同的长度

后面的例子是为什么在Haskell中很难使用 ><，但在依赖类型设置中很容易理解的线索。

像组合一样，张量是一个带有恒等函子作为中性元素的幺半群。 如果我们用张量替换Monad下的组合，我们会得到什么？

pure :: Id x -> (s <| p) x
mystery :: ((s <| p) >< (s <| p)) x -> (s <| p) x

但到底什么是mystery呢？它并不是一个谜，因为我们知道在容器之间制作多态函数有一种相当严格的方式。必须有

f :: (s, s) -> s
g :: pi ((a, b) :: (s, s)) -> p (f (a, b)) -> (p a, p b)

这些正是我们之前所说的决定 <*> 的原因。

Applicative 是张量生成的有副作用编程概念，而Monad则是由组合生成的。在应用程序中，你不需要等待外部响应来选择内部命令，这正是为什么 Applicative 程序更容易并行化的原因。

将 [] >< [] 视为矩形矩阵可以告诉我们为什么列表的 <*> 是建立在乘法基础之上的。

自由应用函子是带旋钮的自由幺半群。对于容器来说，

Free (s <| p) = [s] <| All p

在哪里

All p [] = ()
All p (x : xs) = (p x, All p xs)

因此，“命令”是一长串命令，就像 punch 卡片的一叠牌，您在选择卡片堆之前不会看到任何输出。 "响应" 是您的行式打印机输出。这是上世纪六十年代。

所以，这就是了。 应用程序（Applicative）的本质是张量而不是组合，需要一个底层的幺半群，以及与幺半群兼容的元素重新组合。

- pigworker

---

你所提到的汉考克是谁？ - Max New

这让我想起了Edward Kmett在Hask自函子范畴中将Applicative作为幺半对象的演讲。https://youtu.be/cB8DapKQz-I - dfeuer

稍后会检查，但听起来很有可能。不过我希望人们不要称它为“Hask”，因为这可能会限制想象力。 - pigworker

我希望今天在这个专门的问题中会讨论有关Hask的主题。但是，我越想越觉得你很虚伪，特别是当你想推翻Hask，但另一方面又说“单子...Ap...对于Applicative是基本的”。我认为这没有什么基础，相反，这是Hask特定属性的结果，即它是笛卡尔闭合的。这也是允许这种容器的东西。 - leftaroundabout

Ap现在已经加入了base。 - Iceland_jack

Answer 3

我想要在 Conor McBride (pigworker) 的教学回答中，增加一些关于Applicatives中发现的更多Monoid的例子。 有人注意到，一些functor的Applicative实例类似于对应的Monoid实例; 例如，我们有以下类比:

Applicative → Monoid
---------------------
List        → Product
Maybe       → All
Either a    → First a
State s     → Endo s

在Conor的评论之后，我们可以理解为什么会有这些对应关系。我们使用以下观察结果：

1. 在应用操作 <*> 下，一个 Applicative 容器的形状形成了一个 Monoid。
2. 一个函子 F 的形状由 F 1 给出（其中 1 表示单位 ()）。

对于上面列出的每个 Applicative 函子，我们通过使用单位元素实例化函子来计算它们的形状。我们得到...

List 具有 Nat 的形状：

List a = μ r . 1 + a × r
List 1 = μ r . 1 + 1 × r
       ≅ μ r . 1 + r
       ≅ Nat

Maybe 可能具有 Bool 的形式：

Maybe a = 1 + a
Maybe 1 = 1 + 1
        ≅ Bool

Either 的形式与 Maybe 相同：

Either a b = a + b
Either a 1 = a + 1
           ≅ Maybe a

State 的形状为 Endo：

State s a = (a × s) ^ s
State s 1 = (1 × s) ^ s
          ≅ s ^ s
          ≅ Endo s

---

这些形状的类型与开头列出的Monoid类型完全匹配。 仍有一件事让我感到困惑：其中一些类型允许多个Monoid实例（例如，Bool可以作为All或Any的Monoid）。我不确定为什么我们得到其中一个实例而不是另一个实例。我猜想这与应用定律以及它们与容器的其他组件 - 位置的交互方式有关。

- Dan Oneață

---

要获得其中的一个Any形状，您还必须考虑位置。 All False没有任何位置和All True有一个位置是可以的，因为All False <> All True会给出All False，因此当您一开始只有一个位置时，您不必强制生成一对位置。 使Any起作用的一种方法是交换True和False。 另一种方法是在两种情况下都有一个位置-- a + a，它相当于Sum Identity Identity，或者Writer Any等。 - duplode

如果您只需要一个简单的例子，那么可以使用 Monoid m => Applicative (Const m)。但是我个人认为这并不能保证得到非平凡的结果——例如，我无法想象出如何从 Sum Monoid 中得到其他合理的 Applicative 的方法。 - duplode

没错 - 只要 m 是一个 Monoid，我们总是可以为 Const m 获取一个 Applicative！ - Dan Oneață

我怀疑谜题中的某些实例可能由于效果的顺序不同而有所不同。（另外，我想知道这对康纳在这里给出的答案的视角会产生什么影响。） - duplode

我相信在/r/haskell的主题帖中出现了两个额外的谜题实例：一个和另一个。 - duplode