如何为两个参数具有相同类型的对编写 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

正确吗?如果是这样，那么在 Pair b 中在哪里指定 b-type 是半群?

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)

事实证明，对于每个可表示的函子 (>>=) 等价于以下 bindRep 函数.

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