Applicative/Monad 个实例在多大程度上是唯一确定的？
To what extent are Applicative/Monad instances uniquely determined?
如 this question/answers 所述，Functor 个实例是唯一确定的，如果它们存在的话。
对于列表，有两个众所周知的 Applicative 实例：[] 和 ZipList. So Applicative isn't unique (see also and Why is there no -XDeriveApplicative extension?). However, ZipList needs infinite lists, as its pure 无限期地重复给定的元素。
- 是否有其他更好的数据结构示例，至少有两个
Applicative 个实例？
- 有没有这样的只涉及有限数据结构的例子？也就是说，如果假设 Haskell 的类型系统区分归纳和 coinductive 数据类型，是否有可能唯一确定 Applicative?
更进一步，如果我们可以将 [] 和 ZipList 都扩展到 Monad，我们将有一个示例，其中 monad 不是由数据类型及其 Functor 唯一确定的。 las，ZipList 有一个 Monad 实例 only if we restrict ourselves to infinite lists (streams)。
return for [] 创建一个单元素列表，因此它需要有限列表。因此：
- Monad实例是否由数据类型唯一确定？或者是否有可以具有两个不同 Monad 实例的数据类型的示例？
如果有一个例子有两个或更多不同的实例，一个明显的问题出现了，如果它们 must/can 有相同的应用实例：
- Monad 实例是由 Applicative 实例唯一确定的，还是有一个 Applicative 可以有两个不同的 Monad 实例的例子？
- 是否有具有两个不同 Monad 实例的数据类型示例，每个实例都有不同的 Applicative 超级实例？
最后我们可以为 Alternative/MonadPlus 提出同样的问题。由于有两组不同的 MonadPlus laws. Assuming we accept one of the set of laws (and for Applicative we accept , see also this question),
，所以这很复杂
- Alternative是Applicative唯一决定的，MonadPlus是Monad唯一决定的，还是有反例？
如果以上任何一个是独一无二的，我很想知道为什么，想得到一点证据。如果不是，一个反例。
首先，由于 Monoid 不是唯一的，因此 Writer Monad 或 Applicative 也不是唯一的。考虑
data M a = M Int a
然后你可以给它 Applicative 和 Monad 同构的实例：
Writer (Sum Int)
Writer (Product Int)
给定类型 s 的 Monoid 实例，另一个具有不同 Applicative/Monad 实例的同构对是：
ReaderT s (Writer s)
State s
至于将一个 Applicative 实例扩展到两个不同的 Monad 实例，我记不起任何例子了。然而，当我试图完全说服自己 ZipList 是否真的不能成为 Monad 时，我发现以下非常严格的限制适用于任何 Monad：
join (fmap (\x -> fmap (\y -> f x y) ys) xs) = f <$> xs <*> ys
虽然 all 值没有给出 join：在列表的情况下，限制值是所有元素具有相同长度的值，即"rectangular" 形状的列表列表。
（对于 Reader 单子，单子值的 "shape" 没有变化，这些实际上是所有 m (m x) 值，因此它们确实具有独特的扩展。编辑: 想想看，Either、Maybe 和 Writer 也只有 "rectangular" m (m x) 值，所以它们从 Applicative 扩展到 Monad也是独一无二的。）
不过，如果存在带有两个 Monad 的 Applicative，我不会感到惊讶。
对于 Alternative/MonadPlus，我想不起任何定律 对于使用左分布定律而不是左捕获定律的实例，我看不出有什么能阻止你从仅仅交换 (<|>) 到 flip (<|>)。我不知道是否有更简单的变化。
附录：我突然想起我曾找到一个Applicative有两个Monad的例子。即，有限列表。有通常的 Monad [] 实例，但您可以用以下函数替换它的 join （本质上是制作空列表 "infectious"）：
ljoin xs
| any null xs = []
| otherwise = concat xs
（唉，列表必须是有限的，否则 null 检查将永远无法完成，这会破坏 join . fmap return == id monad 法则。）
这与列表的矩形列表中的 join/concat 具有相同的值，因此将给出相同的 Applicative。我记得，事实证明前两个单子定律是自动的，你只需要检查 ljoin . ljoin == ljoin . fmap ljoin.
鉴于每个 Applicative 都有一个 Backwards 对应，
newtype Backwards f x = Backwards {backwards :: f x}
instance Applicative f => Applicative (Backwards f) where
pure x = Backwards (pure x)
Backwards ff <*> Backwards fs = Backwards (flip ($) <$> fs <*> ff)
不寻常 Applicative 被唯一确定，就像（这远非无关）许多集合以多种方式扩展到幺半群。
在 中，我设置了为非空列表查找至少四个不同的有效 Applicative 实例的练习：我不会在这里破坏它，但我会给出一个重要的提示打猎。
同时，在最近的一些精彩工作中（我几个月前在暑期学校看到的），Tarmo Uustalu 展示了一个相当巧妙的方法来处理这个问题，至少当底层函子是 容器，在雅培、Altenkirch 和 Ghani 的意义上。
警告：前方依赖类型！
什么是容器？如果手边有依赖类型，可以统一呈现类似容器的函子 F，由两个组件决定
- 一组形状，S : Set
- 一组 S 索引位置，P : S -> 集合
直到同构，F X 中的容器数据结构由一些形状 s : S 和一些函数 e : P s -> X 的依赖对给出，它告诉你位于每个位置的元素。即我们定义一个容器的扩展
(S <| P) X = (s : S) * (P s -> X)
（顺便说一句，如果您将 -> 读作反向求幂，它看起来很像广义幂级数）。三角形应该让你想起侧面的树节点，元素 s : S 标记顶点，基线表示位置集 P s。如果某个函子同构于某些S <| P.
，我们就说它是一个容器
在 Haskell 中，您可以轻松地使用 S = F ()，但是构造 P 可能需要相当多的类型黑客。但是 是 您可以在家尝试的东西。你会发现容器在所有常见的多项式类型形成操作下都是封闭的，以及恒等式，
Id ~= () <| \ _ -> ()
组合，其中整个形状仅由一个外部形状和每个外部位置的内部形状构成，
(S0 <| P0) . (S1 <| P1) ~= ((S0 <| P0) S1) <| \ (s0, e0) -> (p0 : P0, P1 (e0 p0))
和其他一些东西，特别是 张量 ，其中有一种外部形状和一种内部形状（因此 "outer" 和 "inner" 可以互换）
(S0 <| P0) (X) (S1 <| P1) = ((S0, S1) <| \ (s0, s1) -> (P0 s0, P1 s1))
所以 F (X) G 表示“F-G-结构-所有相同形状的结构”，例如，[] (X) [] 表示 矩形 列表列表。但是我跑题了
容器之间的多态函数每个多态函数
m : forall X. (S0 <| P0) X -> (S1 <| P1) X
可以通过 容器态射 实现，以非常特殊的方式由两个组件构成。
- 函数
f : S0 -> S1将输入形状映射到输出形状；
- 函数
g : (s0 : S0) -> P1 (f s0) -> P0 s0 将输出位置映射到输入位置。
那么我们的多态函数就是
\ (s0, e0) -> (f s0, e0 . g s0)
根据输入形状计算输出形状，然后通过从输入位置拾取元素来填充输出位置。
（如果你是彼得汉考克，你对正在发生的事情有一个完全不同的比喻。形状是命令；位置是响应；容器态射是 设备驱动程序，以一种方式翻译命令，然后以另一种方式响应。）
每个容器态射都给你一个多态函数，但反之亦然。给定这样一个 m，我们可以取
(f s, g s) = m (s, id)
也就是我们有一个表示定理，说两个容器之间的每一个多态函数都是由这样一个f，g-pair给出的.
那 Applicative 呢？ 我们在构建所有这些机器的过程中有点迷路了。但已经值得。当 monads 和 applicatives 的底层仿函数是容器时，多态函数 pure 和 <*>、return 和 join 必须可以用容器态射的相关概念表示。
让我们先来看应用程序，使用它们的幺半群表示。我们需要
unit : () -> (S <| P) ()
mult : forall X, Y. ((S <| P) X, (S <| P) Y) -> (S <| P) (X, Y)
形状的从左到右的地图需要我们提供
unitS : () -> S
multS : (S, S) -> S
所以看起来我们可能需要一个幺半群。当您检查应用定律时，您会发现我们 恰好 一个幺半群。为容器配备应用结构 完全 通过适当的位置相关操作在其形状上改进幺半群结构。对于 unit 没有什么可做的（因为没有源位置的选择），但是对于 mult，我们需要 whenenver
multS (s0, s1) = s
我们有
multP (s0, s1) : P s -> (P s0, P s1)
满足适当的身份和关联条件。如果我们切换到 Hancock 的解释，我们正在为命令定义一个幺半群（跳过，分号），在选择第二个命令之前无法查看对第一个命令的响应，就像命令是一副穿孔卡片一样。我们必须能够将对组合命令的响应分解为对单个命令的单独响应。
所以，形状上的每个幺半群都给了我们一个潜在的应用结构。对于列表，形状是数字（长度），并且有大量的幺半群可供选择。即使形状存在于 Bool，我们也有相当多的选择。
Monad呢？ 同时，对于单子 M 和 M ~= S <| P。我们需要
return : Id -> M
join : M . M -> M
首先看形状，这意味着我们需要一种不平衡的幺半群。
return_f : () -> S
join_f : (S <| P) S -> S -- (s : S, P s -> S) -> S
这是不平衡的，因为我们在右边得到了一堆形状，而不是一个。如果我们切换到 Hancock 的解释，我们正在为命令定义一种顺序组合，我们确实让第二个命令根据第一个响应来选择，就像我们在电传打字机上进行交互一样。更几何地，我们正在解释如何将一棵树的两层合并为一层。如果这样的作品是独一无二的，那将是非常令人惊讶的。
同样，对于位置，我们必须以连贯的方式将单个输出位置映射到对。这对于 monad 来说更棘手：我们首先选择一个外部位置（响应），然后我们必须选择一个适合在第一个位置（在第一个响应之后选择）处找到的形状（命令）的内部位置（响应）。
我很想 link 了解 Tarmo 的作品以了解详细信息，但它似乎还没有走上街头。他实际上已经使用这种分析来为底层容器的多种选择枚举所有可能的 monad 结构。我很期待论文！
编辑。 为了对其他答案表示敬意，我应该观察到当到处都是 P s = ()，然后是 (S <| P) X ~= (S, X) 和 monad/applicative 结构彼此完全一致，并且与 S 上的幺半群结构完全一致。也就是说，对于 writer monads，我们只需要选择形状级别的操作，因为在每种情况下，值都有一个位置。
如 this question/answers 所述，Functor 个实例是唯一确定的，如果它们存在的话。
对于列表，有两个众所周知的 Applicative 实例：[] 和 ZipList. So Applicative isn't unique (see also -XDeriveApplicative extension?). However, ZipList needs infinite lists, as its pure 无限期地重复给定的元素。
- 是否有其他更好的数据结构示例，至少有两个
Applicative个实例？ - 有没有这样的只涉及有限数据结构的例子？也就是说，如果假设 Haskell 的类型系统区分归纳和 coinductive 数据类型，是否有可能唯一确定 Applicative?
更进一步，如果我们可以将 [] 和 ZipList 都扩展到 Monad，我们将有一个示例，其中 monad 不是由数据类型及其 Functor 唯一确定的。 las，ZipList 有一个 Monad 实例 only if we restrict ourselves to infinite lists (streams)。
return for [] 创建一个单元素列表，因此它需要有限列表。因此：
- Monad实例是否由数据类型唯一确定？或者是否有可以具有两个不同 Monad 实例的数据类型的示例？
如果有一个例子有两个或更多不同的实例，一个明显的问题出现了，如果它们 must/can 有相同的应用实例：
- Monad 实例是由 Applicative 实例唯一确定的，还是有一个 Applicative 可以有两个不同的 Monad 实例的例子？
- 是否有具有两个不同 Monad 实例的数据类型示例，每个实例都有不同的 Applicative 超级实例？
最后我们可以为 Alternative/MonadPlus 提出同样的问题。由于有两组不同的 MonadPlus laws. Assuming we accept one of the set of laws (and for Applicative we accept
- Alternative是Applicative唯一决定的，MonadPlus是Monad唯一决定的，还是有反例？
如果以上任何一个是独一无二的，我很想知道为什么，想得到一点证据。如果不是，一个反例。
首先，由于 Monoid 不是唯一的，因此 Writer Monad 或 Applicative 也不是唯一的。考虑
data M a = M Int a
然后你可以给它 Applicative 和 Monad 同构的实例：
Writer (Sum Int)
Writer (Product Int)
给定类型 s 的 Monoid 实例，另一个具有不同 Applicative/Monad 实例的同构对是：
ReaderT s (Writer s)
State s
至于将一个 Applicative 实例扩展到两个不同的 Monad 实例，我记不起任何例子了。然而，当我试图完全说服自己 ZipList 是否真的不能成为 Monad 时，我发现以下非常严格的限制适用于任何 Monad：
join (fmap (\x -> fmap (\y -> f x y) ys) xs) = f <$> xs <*> ys
虽然 all 值没有给出 join：在列表的情况下，限制值是所有元素具有相同长度的值，即"rectangular" 形状的列表列表。
（对于 Reader 单子，单子值的 "shape" 没有变化，这些实际上是所有 m (m x) 值，因此它们确实具有独特的扩展。编辑: 想想看，Either、Maybe 和 Writer 也只有 "rectangular" m (m x) 值，所以它们从 Applicative 扩展到 Monad也是独一无二的。）
不过，如果存在带有两个 Monad 的 Applicative，我不会感到惊讶。
对于 Alternative/MonadPlus，我想不起任何定律 对于使用左分布定律而不是左捕获定律的实例，我看不出有什么能阻止你从仅仅交换 (<|>) 到 flip (<|>)。我不知道是否有更简单的变化。
附录：我突然想起我曾找到一个Applicative有两个Monad的例子。即，有限列表。有通常的 Monad [] 实例，但您可以用以下函数替换它的 join （本质上是制作空列表 "infectious"）：
ljoin xs
| any null xs = []
| otherwise = concat xs
（唉，列表必须是有限的，否则 null 检查将永远无法完成，这会破坏 join . fmap return == id monad 法则。）
这与列表的矩形列表中的 join/concat 具有相同的值，因此将给出相同的 Applicative。我记得，事实证明前两个单子定律是自动的，你只需要检查 ljoin . ljoin == ljoin . fmap ljoin.
鉴于每个 Applicative 都有一个 Backwards 对应，
newtype Backwards f x = Backwards {backwards :: f x}
instance Applicative f => Applicative (Backwards f) where
pure x = Backwards (pure x)
Backwards ff <*> Backwards fs = Backwards (flip ($) <$> fs <*> ff)
不寻常 Applicative 被唯一确定，就像（这远非无关）许多集合以多种方式扩展到幺半群。
在 Applicative 实例的练习：我不会在这里破坏它，但我会给出一个重要的提示打猎。
同时，在最近的一些精彩工作中（我几个月前在暑期学校看到的），Tarmo Uustalu 展示了一个相当巧妙的方法来处理这个问题，至少当底层函子是 容器，在雅培、Altenkirch 和 Ghani 的意义上。
警告：前方依赖类型！
什么是容器？如果手边有依赖类型，可以统一呈现类似容器的函子 F，由两个组件决定
- 一组形状，S : Set
- 一组 S 索引位置，P : S -> 集合
直到同构，F X 中的容器数据结构由一些形状 s : S 和一些函数 e : P s -> X 的依赖对给出，它告诉你位于每个位置的元素。即我们定义一个容器的扩展
(S <| P) X = (s : S) * (P s -> X)
（顺便说一句，如果您将 -> 读作反向求幂，它看起来很像广义幂级数）。三角形应该让你想起侧面的树节点，元素 s : S 标记顶点，基线表示位置集 P s。如果某个函子同构于某些S <| P.
在 Haskell 中，您可以轻松地使用 S = F ()，但是构造 P 可能需要相当多的类型黑客。但是 是 您可以在家尝试的东西。你会发现容器在所有常见的多项式类型形成操作下都是封闭的，以及恒等式，
Id ~= () <| \ _ -> ()
组合，其中整个形状仅由一个外部形状和每个外部位置的内部形状构成，
(S0 <| P0) . (S1 <| P1) ~= ((S0 <| P0) S1) <| \ (s0, e0) -> (p0 : P0, P1 (e0 p0))
和其他一些东西，特别是 张量 ，其中有一种外部形状和一种内部形状（因此 "outer" 和 "inner" 可以互换）
(S0 <| P0) (X) (S1 <| P1) = ((S0, S1) <| \ (s0, s1) -> (P0 s0, P1 s1))
所以 F (X) G 表示“F-G-结构-所有相同形状的结构”，例如，[] (X) [] 表示 矩形 列表列表。但是我跑题了
容器之间的多态函数每个多态函数
m : forall X. (S0 <| P0) X -> (S1 <| P1) X
可以通过 容器态射 实现，以非常特殊的方式由两个组件构成。
- 函数
f : S0 -> S1将输入形状映射到输出形状； - 函数
g : (s0 : S0) -> P1 (f s0) -> P0 s0将输出位置映射到输入位置。
那么我们的多态函数就是
\ (s0, e0) -> (f s0, e0 . g s0)
根据输入形状计算输出形状，然后通过从输入位置拾取元素来填充输出位置。
（如果你是彼得汉考克，你对正在发生的事情有一个完全不同的比喻。形状是命令；位置是响应；容器态射是 设备驱动程序，以一种方式翻译命令，然后以另一种方式响应。）
每个容器态射都给你一个多态函数，但反之亦然。给定这样一个 m，我们可以取
(f s, g s) = m (s, id)
也就是我们有一个表示定理，说两个容器之间的每一个多态函数都是由这样一个f，g-pair给出的.
那 Applicative 呢？ 我们在构建所有这些机器的过程中有点迷路了。但已经值得。当 monads 和 applicatives 的底层仿函数是容器时，多态函数 pure 和 <*>、return 和 join 必须可以用容器态射的相关概念表示。
让我们先来看应用程序，使用它们的幺半群表示。我们需要
unit : () -> (S <| P) ()
mult : forall X, Y. ((S <| P) X, (S <| P) Y) -> (S <| P) (X, Y)
形状的从左到右的地图需要我们提供
unitS : () -> S
multS : (S, S) -> S
所以看起来我们可能需要一个幺半群。当您检查应用定律时，您会发现我们 恰好 一个幺半群。为容器配备应用结构 完全 通过适当的位置相关操作在其形状上改进幺半群结构。对于 unit 没有什么可做的（因为没有源位置的选择），但是对于 mult，我们需要 whenenver
multS (s0, s1) = s
我们有
multP (s0, s1) : P s -> (P s0, P s1)
满足适当的身份和关联条件。如果我们切换到 Hancock 的解释，我们正在为命令定义一个幺半群（跳过，分号），在选择第二个命令之前无法查看对第一个命令的响应，就像命令是一副穿孔卡片一样。我们必须能够将对组合命令的响应分解为对单个命令的单独响应。
所以，形状上的每个幺半群都给了我们一个潜在的应用结构。对于列表，形状是数字（长度），并且有大量的幺半群可供选择。即使形状存在于 Bool，我们也有相当多的选择。
Monad呢？ 同时，对于单子 M 和 M ~= S <| P。我们需要
return : Id -> M
join : M . M -> M
首先看形状，这意味着我们需要一种不平衡的幺半群。
return_f : () -> S
join_f : (S <| P) S -> S -- (s : S, P s -> S) -> S
这是不平衡的，因为我们在右边得到了一堆形状，而不是一个。如果我们切换到 Hancock 的解释，我们正在为命令定义一种顺序组合，我们确实让第二个命令根据第一个响应来选择，就像我们在电传打字机上进行交互一样。更几何地，我们正在解释如何将一棵树的两层合并为一层。如果这样的作品是独一无二的，那将是非常令人惊讶的。
同样，对于位置，我们必须以连贯的方式将单个输出位置映射到对。这对于 monad 来说更棘手：我们首先选择一个外部位置（响应），然后我们必须选择一个适合在第一个位置（在第一个响应之后选择）处找到的形状（命令）的内部位置（响应）。
我很想 link 了解 Tarmo 的作品以了解详细信息，但它似乎还没有走上街头。他实际上已经使用这种分析来为底层容器的多种选择枚举所有可能的 monad 结构。我很期待论文！
编辑。 为了对其他答案表示敬意，我应该观察到当到处都是 P s = ()，然后是 (S <| P) X ~= (S, X) 和 monad/applicative 结构彼此完全一致，并且与 S 上的幺半群结构完全一致。也就是说，对于 writer monads，我们只需要选择形状级别的操作，因为在每种情况下，值都有一个位置。