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

问题描述

如此问题/答案所述， Functor 实例为唯一确定的，如果它们存在的话。

对于列表，有两个众所周知的应用实例： [] 和< a href =https://hackage.haskell.org/package/base-4.8.1.0/docs/Control-Applicative.html#v:ZipList =nofollow noreferrer> ZipList code> 。因此，应用程序不是唯一的（另请参阅 GHC是否可以为单变量变体派生Functor和Applicative实例？ a>和为什么没有 -XDeriveApplicative 扩展？）。但是， ZipList 需要无限列表，因为它的 pure 无限期地重复给定的元素。





• 是否有其他更好的数据结构示例，它们至少有两个 Applicative 实例


• 有没有这样的例子只涉及有限的数据结构？也就是说，就像假设Haskell的类型系统区分归纳和 coinductive 数据类型一样，是否有可能如果我们可以扩展 [] 来确定Applicative？
>和 ZipList 给Monad，我们会举一个例子，monad不是由数据类型和它的Functor唯一确定的。唉， ZipList 有一个Monad实例只有当我们限制自己的无限列表（流）。
并且 return 用于 [] 创建一个单元素列表，所以它需要有限列表。因此：




• Monad实例是否由数据类型唯一确定？还是有一个数据类型的例子可以有两个不同的Monad实例？
  
  
  

  在这种情况下，更明显的例子，如果它们必须/可以具有相同的Applicative实例，则会出现明显的问题：
  
  

  
  
  • Monad实例由Applicative唯一确定实例，还是有一个应用程序的例子，可以有两个不同的Monad实例？
    
  • 是否有一个数据类型的例子包含两个不同的Monad实例，每个实例具有不同的Applicative超级实例，实例？
  
  
  
  
  

  最后，我们可以为Alternative / MonadPlus询问同样的问题。这很复杂，因为有两套截然不同的 MonadPlus法律。假设我们接受其中一套法律（对于Applicative，我们接受右/左分配/吸收，另请参阅这个问题），
  
  

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

  如果上述任何一项都是唯一的，我'有兴趣知道为什么，有一点证明。首先，既然 Monoid s不是唯一的，也不是 Writer Monad s或 Applicative 秒。考虑
  
  

    data M a = M Int a 
    

  然后你可以给它 Applicative 和 Monad 实例同构于任何一个：
  
  

    Writer（Sum Int）
   Writer（Product Int）
    

  给定一个 s Monoid 另一个与应用程序 / Monad 实例不同的同构对是：
  
  

    ReaderT s（Writer s）
   State s 
    

  至于让一个 Applicative 实例延伸到两个不同的 Monad s，我记不得任何例子。但是，当我试图完全说服自己 ZipList 真的不能成为 Monad 时，我发现以下对于任何 Monad ：

    join（fmap（ \ x  - > fmap（\ y  - > fxy）ys）xs）= f< $> xs * ys 
    

  这不会给加入尽管如此，在列表的情况下，限制值是所有元素具有相同长度的值，即具有矩形形状的列表的列表。

  
  
  

  （对于 Reader monad，其中monadic值的形状不变，这些实际上都是 m（ mx）值，所以这些确实具有唯一的扩展名。编辑：来想一想，或者，可能 code>和 Writer 也只有矩形 m（mx）值，所以它们的扩展名 Applicative 到 Monad 也是唯一的。）



  我wouldn不过，如果 Applicative 与两个 Monad s存在，不会感到惊讶。

  
  
  

  对于替代 / MonadPlus ，我无法回忆任何法则 for使用Left Distribution法则而不是Left Catch的例子，我没有看到任何阻止你的事情从（< |>）与翻转（< |>）>交换。

  
  
  

  附加信息：我突然想起我有一个<$ c $的例子，它找到了一个<$ c $的例子c>应用，两个 Monad s。即有限清单。有通常的 Monad [] 实例，但是你可以用下面的函数替换它的 join 传染性）：
  
  

    ljoin xs 
   |任何空xs = [] 
   |否则= concat xs 
    

  （唉，列表需要是有限的，否则 null check将永远不会结束，并且会破坏 join。fmap return == id monad law。）

  
  
  

  这与列表的矩形列表中的 join / concat 具有相同的值，所以将给出相同的 Applicative 。据我记得，事实证明，前两个单子定律是自动的，你只需要检查 ljoin。 ljoin == ljoin。 fmap ljoin 。

  
  

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

  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.

  • 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?

  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:

  • Are Monad instances uniquely determined by the data type? Or is there an example of a data type that can have two distinct Monad instances?

  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:

  • Are Monad instances uniquely determined by the Applicative instance, or is there an example of an Applicative that can have two distinct Monad instances?
  • Is there an example of a data type with two distinct Monad instances, each having a different Applicative super-instance?

  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),

  • is Alternative uniquely determined by Applicative, and MonadPlus by Monad, or are there any counter-examples?

  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.

  解决方案

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

  data M a = M Int a
  

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

  Writer (Sum Int)
  Writer (Product Int)
  

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

  ReaderT s (Writer s)
  State s
  

  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
  

  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.

  (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. EDIT: 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.)

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

  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.

  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
  

  (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.)

  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屋！