Applicative/Monad 实例在多大程度上是唯一确定的? [英] To what extent are Applicative/Monad instances uniquely determined?

问题描述

如这个问题/答案所述，Functor 实例是唯一确定的(如果它们存在).

As described this question/answers, Functor instances are uniquely determined, if they exists.

对于列表，有两个众所周知的 Applicative 实例:[] 和 ZipList.所以Applicative 不是唯一的(另请参阅GHC 能否为 monad 转换器派生 Functor 和 Applicative 实例?a> 和 为什么没有 -XDeriveApplicative 扩展?).但是，ZipList 需要无限列表，因为它的 pure 无限重复给定的元素.

For lists, there are two well know Applicative instances: [] and ZipList. So Applicative isn't unique (see also Can GHC derive Functor and Applicative instances for a monad transformer? and Why is there no -XDeriveApplicative extension?). However, ZipList needs infinite lists, as its pure repeats a given element indefinitely.

• 是否还有其他更好的数据结构示例，其中至少有两个 Applicative 实例?
• 有没有这样的例子只涉及有限的数据结构?也就是说，如果假设 Haskell 的类型系统区分归纳和 coinductive 数据类型，是否有可能唯一确定 Applicative?

• Are there other, perhaps better examples of data structures that have at least two Applicative instances?
• Are there any such examples that only involve finite data structures? That is, like if hypothetically Haskell's type system distinguished inductive and coinductive data types, would it be possible to uniquely determine Applicative?

更进一步，如果我们可以将 [] 和 ZipList 扩展到一个 Monad，我们将有一个示例，其中一个 monad 不是由数据唯一确定的类型及其函子.唉，ZipList 只有一个 Monad 实例 如果我们将自己限制在无限列表(streams).并且 [] 的 return 创建了一个单元素列表，因此它需要有限列表.因此:

Going further, if we could extend both [] and ZipList to a Monad, we'd have an example where a monad isn't uniquely determined by the data type and its Functor. Alas, ZipList has a Monad instance only if we restrict ourselves to infinite lists (streams). And return for [] creates a single-element list, so it requires finite lists. Therefore:

• Monad 实例是否由数据类型唯一确定?或者是否有一个数据类型可以有两个不同的 Monad 实例的示例?

如果有两个或更多不同实例的示例，则出现一个明显的问题，如果它们必须/可以具有相同的 Applicative 实例:

In the case there is an example with two or more distinct instances, an obvious question arises, if they must/can have the same Applicative instance:

• Monad 实例是由 Applicative 实例唯一确定的，还是有一个 Applicative 实例可以有两个不同的 Monad 实例?
• 是否有一个数据类型的示例，其中包含两个不同的 Monad 实例，每个实例都有一个不同的 Applicative 超级实例?

最后我们可以对 Alternative/MonadPlus 提出同样的问题.由于有两套不同的MonadPlus 法律，这一点很复杂.假设我们接受一组法律之一(对于 Applicative，我们接受右/左分配/吸收，另见这个问题),

And finally we can ask the same question for Alternative/MonadPlus. This is complicated by the fact that there are two distinct set of MonadPlus laws. Assuming we accept one of the set of laws (and for Applicative we accept right/left distributivity/absorption, see also this question),

• Alternative 是由 Applicative 唯一确定的，MonadPlus 是由 Monad 唯一确定的，还是有任何反例?

如果上述任何一项是独一无二的，我很想知道原因，以提供证据提示.如果不是，反例.

If any of the above are unique, I'd be interested in knowing why, to have a hint of a proof. If not, an counter-example.

推荐答案

首先，由于 Monoid 不是唯一的，Writer Monad 也不是唯一的>s 或 Applicatives.考虑

First, since Monoids are not unique, neither are Writer Monads or Applicatives. Consider

data M a = M Int a

然后你可以给它 Applicative 和 Monad 同构的实例:

then you can give it Applicative and Monad instances isomorphic to either of:

Writer (Sum Int)
Writer (Product Int)

给定类型 s 的 Monoid 实例，另一个具有不同 Applicative/Monad 实例的同构对是:

Given a Monoid instance for a type s, another isomorphic pair with different Applicative/Monad instances is:

ReaderT s (Writer s)
State s

至于让一个 Applicative 实例扩展到两个不同的 Monad ，我不记得任何例子.然而，当我试图完全说服自己 ZipList 是否真的不能成为 Monad 时，我发现以下非常强大的限制适用于任何 Monad:

As for having one Applicative instance extend to two different Monads, I cannot remember any example. However, back when I tried to convince myself completely about whether ZipList really cannot be made a Monad, I found the following pretty strong restriction that holds for any Monad:

join (fmap (x -> fmap (y -> f x y) ys) xs) = f <$> xs <*> ys

这并没有为 all 值提供 join :在列表的情况下，受限值是所有元素具有相同长度的值，即列表具有矩形"形状的列表.

That doesn't give join for all values though: in the case of lists the restricted values are the ones where all elements have the same length, i.e. lists of lists with "rectangular" shape.

(对于 Reader monads，monadic 值的形状"没有变化，这些实际上都是 m (mx) 值，所以那些有独特的扩展名.想想看，Either、Maybe 和 Writer 也只有矩形"m (mx) 值，所以它们从 Applicative 到 Monad 的扩展也是唯一的.)

(For Reader monads, where the "shape" of monadic values doesn't vary, these are in fact all the m (m x) values, so those do have unique extension. Come to think of it, Either, Maybe and Writer also have only "rectangular" m (m x) values, so their extension from Applicative to Monad is also unique.)

不过，如果存在带有两个 Monad 的 Applicative，我不会感到惊讶.

I wouldn't be surprised if an Applicative with two Monads exists, though.

对于Alternative/MonadPlus，我不记得任何法律，例如使用左分布定律而不是左捕捉，我看不出任何阻止您只需将 (<|>) 与 flip (<|>) 交换即可.我不知道是否有更不重要的变化.

For Alternative/MonadPlus, I cannot recall any law for instances using the Left Distribution law instead of Left Catch, I see nothing preventing you from just swapping (<|>) with flip (<|>). I don't know if there's a less trivial variation.

附录:我突然想起我曾经发现了一个带有两个 Monad 的 Applicative 示例.即，有限列表.有通常的 Monad [] 实例，但你可以用下面的函数替换它的 join(本质上是使空列表具有感染力"):

ADDENDUM: I suddenly remembered I had found an example of an Applicative with two Monads. Namely, finite lists. There's the usual Monad [] instance, but you can then replace its join by the following function (essentially making empty lists "infectious"):

ljoin xs
  | any null xs = []
  | otherwise   = concat xs

(唉，列表必须是有限的，否则 null 检查将永远不会完成，这将破坏 join . fmap return == id monad 法则.)

(Alas, the lists need to be finite because otherwise the null check will never finish, and that would ruin the join . fmap return == id monad law.)

这与列表的矩形列表上的 join/concat 具有相同的值，因此将给出相同的 Applicative.我记得，事实证明前两个 monad 定律是自动的，你只需要检查 ljoin .ljoin == ljoin .fmap ljoin.

This has the same value as join/concat on rectangular lists of lists, so will give the same Applicative. As I recall, it turns out that the first two monad laws are automatic from that, and you just need to check ljoin . ljoin == ljoin . fmap ljoin.

这篇关于Applicative/Monad 实例在多大程度上是唯一确定的?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！