如何为两个参数都具有相同类型的对编写monad实例? [英] How to write a monad instance for a pair where both arguments have the same type?

问题描述

假设我的类型为Pair:

Suppose I have a type Pair:

data Pair a = Pair a a

为它编写monad实例的正确方法是什么?我的想法大致是这样:

What is the right way to write a monad instance for it? My idea is roughly this:

instance Semigroup a => Semigroup (Pair a) where
  Pair a1 a2 <> Pair b1 b2 = Pair (a1 <> b1)(a2 <> b2)

instance Monad Pair where
  return = pure
  (Pair a b) >>= f = f a <> f b

对吗?如果是这样，那么在对b中将b类型指定为半群的地方是什么?

Is it correct? If so then where to specify that b-type in the Pair b is a semigroup?

推荐答案

实际上，Pair的唯一正确的monad实例如下.

Actually, the only correct monad instance of Pair is as follows.

instance Monad Pair where
    m >>= f = joinPair (f <$> m)

joinPair :: Pair (Pair a) -> Pair a
joinPair (Pair (Pair x _) (Pair _ y)) = Pair x y

这是正确的monad实例的原因是因为Pair是可表示的函子.

The reason this is the correct monad instance is because Pair is a representable functor.

instance Representable Pair where
    type Rep Pair = Bool

    index (Pair x _) False = x
    index (Pair _ y) True  = y

    tabulate f = Pair (f False) (f True)

结果证明，对于每个可表示的函子(>>=)均等效于以下

Turns out, for every representable functor (>>=) is equivalent to the following bindRep function.

bindRep :: Representable f => f a -> (a -> f b) -> f b
bindRep m f = tabulate (\a -> index (f (index m a)) a)

如果我们将bindRep函数专门用于Pair，我们将得到以下信息.

If we specialize the bindRep function to Pair we get the following.

bindRep :: Pair a -> (a -> Pair b) -> Pair b
bindRep (Pair x y) f = tabulate (\a -> index (f (index (Pair x y) a)) a)
                     = Pair (index (f x) False) (index (f y) True)
--                          |_________________| |________________|
--                                   |                   |
--                           (1st elem of f x)   (2nd elem of f y)

以下Adelbert Chang的博客文章对此进行了更好的解释. 与可表示的函子相符.

The following blog post by Adelbert Chang explains it better. Reasoning with representable functors.

这是证明独特性的另一种方法.考虑左右身份monad实例法则.

Here's another way to prove uniqueness. Consider the left and right identity monad instance laws.

return a >>= k = k a -- left identity law

m >>= return = m     -- right identity law

现在，对于Pair数据类型return x = Pair x x.因此，我们可以专门研究这些法律.

Now, for the Pair data type return x = Pair x x. Hence, we can specialize these laws.

Pair a a >>= k = k a     -- left identity law

m >>= \x -> Pair x x = m -- right identity law

那么，为了满足这两个定律，>>=的定义应该是什么?

So, what should the definition of >>= be in order to satisfy these two laws?

Pair x y >>= f = Pair (oneOf [x1, x2, y1, y2]) (oneOf [x1, x2, y1, y2])
    where Pair x1 y1 = f x
          Pair x2 y2 = f y

oneOf函数不确定地返回列表的元素之一.

The oneOf function returns one of the elements of the list non-deterministically.

现在，如果我们的>>=函数要满足左身定律，那么当x = y时，则x1 = x2和y1 = y2且结果必须为Pair (oneOf [x1, x2]) (oneOf [y1, y2]).

Now, if our >>= function is to satisfy the left identity law then when x = y then x1 = x2 and y1 = y2 and the result must be Pair (oneOf [x1, x2]) (oneOf [y1, y2]).

类似地，如果我们的>>=功能是要满足正确的身份法则，那么x1 = y1 = x和x2 = y2 = y的结果必须是Pair (oneOf [x1, y1]) (oneOf [x2, y2]).

Similarly, if our >>= function is to satisfy the right identity law then x1 = y1 = x and x2 = y2 = y and the result must be Pair (oneOf [x1, y1]) (oneOf [x2, y2]).

因此，如果您要同时满足这两个定律，则唯一有效的结果是Pair x1 y2.

Hence, if you want to satisfy both laws then the only valid result is Pair x1 y2.

这篇关于如何为两个参数都具有相同类型的对编写monad实例?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！