证明 Applicative 和 Monad 中序列定义的等价性

Question

我怎样才能正确证明

sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a)
sequenceA []     = pure []
sequenceA (x:xs) = pure (:) <*> x <*> sequenceA xs

与 monad 输入基本相同

sequenceA' :: Monad m => [m a] -> m [a]
sequenceA' [] = return [] 
sequenceA' (x:xs) = do 
                    x'  <- x 
                    xs' <- sequenceA' xs 
                    return (x':xs')

当然有 Applicative 和 Monad 的限制。

Answer 1

这是一个证明草图：

表明

do
    x'  <- x
    xs' <- sequenceA' xs
    return (x' : xs')

相当于

do
    f1  <- do
        cons <- return (:)
        x'  <- x
        return (cons x')
    xs' <- sequenceA' xs
    return (f1 xs')

这涉及脱糖（和重新加糖）do 符号并应用 Monad laws.

使用definition of ap:

ap m1 m2 = do { x1 <- m1; x2 <- m2; return (x1 x2) }

把上面的代码变成

do
    f1  <- return (:) `ap` x
    xs' <- sequenceA' xs
    return (f1 xs')

然后

return (:) `ap` x `ap` sequenceA' xs

现在你有
```
sequenceA' [] = return [] 
sequenceA' (x:xs) = return (:) `ap` x `ap` sequenceA' xs
```
假设 pure 和 <*> 分别与 return 和 `ap` 基本相同，您就完成了。

后者属性在Applicative documentation中也有说明：
If f is also a Monad, it should satisfy
- pure = return
- (<*>) = ap

Answer 2

自从 Functor-Applicative-Monad proposal 在 GHC 7.10 中实现以来，Applicative 是 Monad 的超类。所以即使你的两个函数不能严格等价，因为 sequenceA 的域包含 sequenceA' 的域，我们可以看看在这个公共域中发生了什么（Monad 类型类).

This paper 展示了一个有趣的演示，将 do 符号去糖化为应用和函子操作（<$>、pure 和 <*>）。如果向左箭头 (<-) 右侧的表达式不相互依赖，就像您问题中的情况一样，您始终可以使用应用操作，因此表明您的假设是正确的（对于 Monad 域）。

另请查看 ApplicativeDo 语言扩展提案，其中包含一个与您的示例类似的示例：

do
  x <- a
  y <- b
  return (f x y)

转换为：

(\x y -> f x y) <$> a <*> b

用 f 代替 (:)，我们得到：

do
  x <- a
  y <- b
  return (x : y)

... 转化为...

(\x y -> x : y) <$> a <*> b
--And by eta reduction
(:) <$> a <*> b
--Which is equivalent to the code in your question (albeit more general):
pure (:) <*> a <*> b

或者，您可以使用 ApplicativeDo 语言扩展并遵循 this answer SO 问题 "haskell - Desugaring do-notation for Monads" 让 GHC 的脱糖器为您工作。我将把这个练习留给你（老实说，它超出了我的能力范围！）。

Answer 3

My own two cents

Haskell 中没有应用程序的 do 表示法。具体可以看this segment.

return 和 pure 做的完全一样，但是有不同的约束，对吧？所以这部分 pure (:) 和这部分 return (x:xs) 本质上是一样的。

然后，在这里 x <- act 你得到了 act 的值，然后是递归的值 xs <- seqn acts，最后用 return.[=20= 包装它]

这就是 pure (:) <*> x <*> sequenceA xs 本质上正在做的事情。

证明 Applicative 和 Monad 中序列定义的等价性

Proving equivalence of sequence definitions from Applicative and Monad

monads

haskell

list

equivalent

applicative