Monoidal Functor 是 Applicative 但 Monoid typeclass 在 Applicative 的定义中在哪里？
Monoidal Functor is Applicative but where is the Monoid typeclass in the definition of Applicative?
Applicative 是一个幺半群函子：
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) #-}
此定义中未提及结构性幺半群，但当您这样做时
> ("ab",(+1)) <*> ("cd", 5)
>("abcd", 6)
在实现这个Applicative实例时，可以清楚的看到Structural Monoid "(,) 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)
被称为“幺半群仿函数”的幺半群不是 Monoid 幺半群，即值级幺半群。它是 类型级别的幺半群 。即，无聊的乘积幺半群
type Mempty = ()
type a <> b = (a,b)
（您可能会注意到，这并不是严格意义上的幺半群；只有当您将 ((a,b),c) 和 (a,(b,c)) 视为同一类型时才会出现这种情况。它们确实是同构的。）
看看这与 Applicative 有什么关系。幺半群函子，我们需要用其他术语写 class。
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 class 的通用实例是一个简单的练习，反之亦然。
关于("ab",(+1)) <*> ("cd", 5)：一般而言，这与Applicative没有太大关系，但仅与特定的作家应用程序有关。实例是
instance Monoid a => Monoidal ((,) a) where
pureUnit = (mempty, ())
fzip (p,a) (q,b) = (p<>q, (a,b))
也许您要找的幺半群就是这个。
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)
作为评论，在下面，观察到，它可以在名称 Ap 下的 reducers 库中找到。它是 Applicative 的基础，所以让我们解压它。
请特别注意，因为 () 是平凡的 Monoid，所以 AppM f () 也是 Monoid。这就是潜伏在 Applicative f.
后面的幺半群
我们本可以坚持将 Monoid (f ()) 作为 Applicative 的超类，但这会把事情搞得一团糟。
> mappend (AppM [(),()]) (AppM [(),(),()])
AppM [(),(),(),(),(),()]
Applicative [] 下的幺半群是自然数的 乘法 ，而列表的“明显”幺半群结构是串联，专门用于 加法 个自然数。
数学警告。依赖类型警告。假 Haskell 警告。
查看正在发生的事情的一种方法是考虑那些恰好是 容器 的应用程序，在 Abbott、Altenkirch 和 Ghani 的依赖类型意义上。我们很快就会在 Haskell 中提供这些内容。我就假装未来已经到来。
data (<|) (s :: *)(p :: s -> *) (x :: *) where
(:<|:) :: pi (a :: s) -> (p a -> x) -> (s <| p) x
数据结构(s <| p)的特点是
- Shapes
s 告诉你容器的样子。
- Positions
p 告诉你对于给定的形状 你可以在哪里放置数据。
上面的type说给这样的结构赋数据就是挑一个形状，然后把所有的位置都填上数据。
[] 的容器表示是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)
（秘密地，我们这些受过基本汉考克训练的人也认为 "shapes" 是 "commands"，"positions" 是 "valid responses"。容器之间的态射是然后正好是 "device driver"。但我离题了。）
沿着类似的思路思考，制作一个容器需要什么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 使构图变平。潜伏在它后面的不仅仅是形状上的幺半群，还有一个 integration 运算符。也就是说，
join :: ((s <| p) . (s <| p)) x -> (s <| p) x
需要
integrate :: (s <| p) s -> s
您的免费 monad 为您提供策略树，您可以在其中使用一个命令的结果来选择其余的策略。就像您在使用 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是tensor产生的有效编程的概念，其中Monad是composition产生的。您没有 to/need 等待外部响应来选择内部命令的事实是 Applicative 程序更容易并行化的原因。
将 [] >< [] 视为矩形矩阵告诉我们为什么列表的 <*> 建立在乘法之上。
自由应用函子是带有旋钮的自由幺半群。对于容器，
Free (s <| p) = [s] <| All p
哪里
All p [] = ()
All p (x : xs) = (p x, All p xs)
所以 "command" 是一个很大的命令列表，就像一副穿孔卡片。在选择卡片组之前，您看不到任何输出。 "response" 是您的行式打印机输出。这是 1960 年代。
好了。 Applicative 的本质，张量而不是组合，需要一个潜在的幺半群，以及与幺半群兼容的元素的重组。
我想用 Applicative 中发现的 Monoid 的更多示例来补充 Conor McBride（养猪工）。
It has been observed 某些函子的 Applicative 实例类似于对应的 Monoid 实例；
例如，我们有以下类比：
Applicative → Monoid
---------------------
List → Product
Maybe → All
Either a → First a
State s → Endo s
根据 Conor 的评论，我们可以理解为什么我们有这些对应关系。
我们使用以下观察结果：
- 一个
Applicative容器的形状在应用操作<*>下形成一个Monoid。
- 函子
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 可以制成 Monoid 作为 All 或 Any) 而且我不完全确定为什么我们得到其中一个实例而不是另一个实例。我的猜测是，这与适用法则以及它们如何与容器的其他组件（其位置）相互作用有关。
Applicative 是一个幺半群函子：
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) #-}
此定义中未提及结构性幺半群，但当您这样做时
> ("ab",(+1)) <*> ("cd", 5)
>("abcd", 6)
在实现这个Applicative实例时，可以清楚的看到Structural Monoid "(,) 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)
被称为“幺半群仿函数”的幺半群不是 Monoid 幺半群，即值级幺半群。它是 类型级别的幺半群 。即，无聊的乘积幺半群
type Mempty = ()
type a <> b = (a,b)
（您可能会注意到，这并不是严格意义上的幺半群；只有当您将 ((a,b),c) 和 (a,(b,c)) 视为同一类型时才会出现这种情况。它们确实是同构的。）
看看这与 Applicative 有什么关系。幺半群函子，我们需要用其他术语写 class。
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 class 的通用实例是一个简单的练习，反之亦然。
关于("ab",(+1)) <*> ("cd", 5)：一般而言，这与Applicative没有太大关系，但仅与特定的作家应用程序有关。实例是
instance Monoid a => Monoidal ((,) a) where
pureUnit = (mempty, ())
fzip (p,a) (q,b) = (p<>q, (a,b))
也许您要找的幺半群就是这个。
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)
作为评论，在下面，观察到，它可以在名称 Ap 下的 reducers 库中找到。它是 Applicative 的基础，所以让我们解压它。
请特别注意，因为 () 是平凡的 Monoid，所以 AppM f () 也是 Monoid。这就是潜伏在 Applicative f.
我们本可以坚持将 Monoid (f ()) 作为 Applicative 的超类，但这会把事情搞得一团糟。
> mappend (AppM [(),()]) (AppM [(),(),()])
AppM [(),(),(),(),(),()]
Applicative [] 下的幺半群是自然数的 乘法 ，而列表的“明显”幺半群结构是串联，专门用于 加法 个自然数。
数学警告。依赖类型警告。假 Haskell 警告。
查看正在发生的事情的一种方法是考虑那些恰好是 容器 的应用程序，在 Abbott、Altenkirch 和 Ghani 的依赖类型意义上。我们很快就会在 Haskell 中提供这些内容。我就假装未来已经到来。
data (<|) (s :: *)(p :: s -> *) (x :: *) where
(:<|:) :: pi (a :: s) -> (p a -> x) -> (s <| p) x
数据结构(s <| p)的特点是
- Shapes
s告诉你容器的样子。 - Positions
p告诉你对于给定的形状 你可以在哪里放置数据。
上面的type说给这样的结构赋数据就是挑一个形状，然后把所有的位置都填上数据。
[] 的容器表示是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)
（秘密地，我们这些受过基本汉考克训练的人也认为 "shapes" 是 "commands"，"positions" 是 "valid responses"。容器之间的态射是然后正好是 "device driver"。但我离题了。）
沿着类似的思路思考，制作一个容器需要什么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 使构图变平。潜伏在它后面的不仅仅是形状上的幺半群，还有一个 integration 运算符。也就是说，
join :: ((s <| p) . (s <| p)) x -> (s <| p) x
需要
integrate :: (s <| p) s -> s
您的免费 monad 为您提供策略树，您可以在其中使用一个命令的结果来选择其余的策略。就像您在使用 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是tensor产生的有效编程的概念，其中Monad是composition产生的。您没有 to/need 等待外部响应来选择内部命令的事实是 Applicative 程序更容易并行化的原因。
将 [] >< [] 视为矩形矩阵告诉我们为什么列表的 <*> 建立在乘法之上。
自由应用函子是带有旋钮的自由幺半群。对于容器，
Free (s <| p) = [s] <| All p
哪里
All p [] = ()
All p (x : xs) = (p x, All p xs)
所以 "command" 是一个很大的命令列表，就像一副穿孔卡片。在选择卡片组之前，您看不到任何输出。 "response" 是您的行式打印机输出。这是 1960 年代。
好了。 Applicative 的本质，张量而不是组合，需要一个潜在的幺半群，以及与幺半群兼容的元素的重组。
我想用 Applicative 中发现的 Monoid 的更多示例来补充 Conor McBride（养猪工）Applicative 实例类似于对应的 Monoid 实例；
例如，我们有以下类比：
Applicative → Monoid
---------------------
List → Product
Maybe → All
Either a → First a
State s → Endo s
根据 Conor 的评论，我们可以理解为什么我们有这些对应关系。 我们使用以下观察结果：
- 一个
Applicative容器的形状在应用操作<*>下形成一个Monoid。 - 函子
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 可以制成 Monoid 作为 All 或 Any) 而且我不完全确定为什么我们得到其中一个实例而不是另一个实例。我的猜测是，这与适用法则以及它们如何与容器的其他组件（其位置）相互作用有关。