关于Haskell的sequence函数的问题

Question

我一直在学习 UPenn 的 CS194，目前正在学习第 7 课，Monads。在我看到序列函数的实现并开始四处探索之前，我认为我对 Monads 的掌握还不错。

sequence :: Monad m => [m a] -> m [a]
sequence [] = return []
sequence (ma:mas) = do
  a  <- ma
  as <- sequence mas
  return (a:as)

乍一看这似乎很直观，但当我深入研究它时，我遇到了一堆问题：

return [] 的类型是：return [] :: Monad m => m [t]。在同一课的前面，[] 的 Monad 实例将 return 定义为：return x = [x]。这如何导致类型签名 m [t] for return []?
a <- ma。假设我用 [Just 5, Just 9] 调用序列，这里 a 的类型是什么？通过 Maybe 的 Monad 实例定义：
```
Just x  >>= k = k x
```
我认为 x，或者 a 在 sequence 的情况下将是 Num。但它必须确实是 Num 的 Monad。当 Maybe 的实例定义中的 x 似乎从 Just 中拉出 x 时，x 如何成为 Num 的单子？

Answer 1

return [] 的类型是 Monad m => m [t] - 这里，[] 是 [t] 的实例，即一些任意类型的列表（类型是任意的因为它是空列表，所以无论如何都没有该类型的实例）。如果替换列表 monad，return 的类型是 t -> [t]，而 return [] 产生 [[]]。令人困惑的是，monad 和包含的值都是列表。

return的类型一般是Monad m => t -> m t。如果专门针对列表，则会得到 t -> [t]，因此列表类型会取代 m。列表的特殊语法使这更令人困惑；如果你改用 maybe monad，specialized return 的类型是 t -> Maybe t，所以你可以清楚地看到 m 是如何被 Maybe 替换的。在 maybe monad 中，return [] 的类型是 Maybe [t]：monad 现在包装了一些列表。

return []的类型是Monad m => m [t]，一个被monad包装的列表。如果您使用列表 monad，则将 m 替换为列表构造函数并得到 [[t]]，这是正确的类型。

关于第二个问题，你为什么认为a一定是monad？

在评论中澄清后编辑

在您给出的示例调用 sequence [Just 5, Just 9] 中，monad 是 maybe，而不是 list；该列表是 sequence 类型所要求的普通列表。请记住，它需要 [m a] 作为输入。当您提供 Num a => [Maybe a] 作为输入时，这使得 monad Maybe，结果类型为 Num a => Maybe [a]。 sequence 将可选值列表变成可选列表。这意味着在 sequence 的第一种情况下，return [] 适用于 Maybe 的 return 并且意味着 Just []。这是有道理的，因为在 maybe monad 中调用 sequence [] 应该 return Just [].

现在，在第二种情况的 do-block 中，我们有一堆变量，这有助于找出每个变量的类型。对于 Maybe 和 Int 的具体情况，我会这样做；在所有这些情况下，获取通用类型归结为简单地将 Maybe 替换为 m 并将 Int 替换为 a，并添加约束。

整个输入的类型为 [Maybe Int]。第二种情况 pattern-matches this with (ma:mas)，从列表中选择第一个元素。因此 ma 具有列表元素的类型 Maybe Int，而 mas 是列表的其余部分，因此具有类型 [Maybe Int].

在do-block中，ma用箭头符号解包，结果是a，因此其类型是ma的类型，去掉了monad , 即 Int.

然后，sequence 与输入的其余部分 mas 递归调用，其类型为 [Maybe Int]。代入sequence类型，结果类型为Maybe [Int]。该值再次展开，因此目标 as 的类型为 [Int].

在最后一行中，a（类型 Int）被添加到 as（类型 [Int]）之前，产生了一个更长的列表（[Int] ).结果被提供给 return，它将它包装在 Just (Maybe [Int]) 中以匹配 sequence.

的结果类型

顺便说一句，如果您想通过 do-block 详细跟踪类型，您应该首先使用 lambda 将它们脱糖为正常组合。

关于Haskell的sequence函数的问题

Questions on Haskell's sequence function

monads

haskell