关于哈斯克尔序列函数的问题

Question

我一直在学习宾夕法尼亚大学的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)

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

1. return []的类型是：return [] :: Monad m => m [t]。在同一课的前面部分，[] 的 Monad 实例将 return 定义为：return x = [x] 。 这如何导致return []的类型签名m [t]？

2. a <- ma .假设我用[Just 5, Just 9]调用序列，这里的a类型是什么？ 通过Maybe的Monad实例定义：

   Just x  >>= k = k x
   

   我认为x，或者在sequence的情况下a将是一个Num。但这必须真的是Num的Monad.当Just x从Maybe的实例定义中拉出Just x时，x是如何成为Num的monad的？

Answer 1

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

一般而言，return的类型是 Monad m => t -> m t .如果您专门研究列表，则会得到t -> [t]，因此列表类型取代了m。列表的特殊语法使这更加混乱;如果你改用 may monad，专用返回的类型是 t -> Maybe t ，所以你可以清楚地看到m是如何被 Maybe 替换的。在 may monad 中，return []的类型是 Maybe [t] ：monad 现在包装了一些列表。

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

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

在评论中澄清后编辑

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

现在，在第二种情况的执行块中，我们有一堆变量，它有助于找出每个变量的类型。我将针对Maybe的具体情况这样做，并为数字Int;获取泛型类型归结为在所有这些情况下，只需将Maybe替换为m，Int替换为a，并添加约束。

整个输入的类型为 [Maybe Int] 。第二种情况模式与(ma:mas)匹配，从列表中选择第一个元素。所以ma具有列表元素的类型，Maybe Int ，而mas是列表的其余部分，因此具有类型 [Maybe Int] 。

在 do-block 中，ma 用箭头符号解开包装，结果是 a ，因此其类型是剥离 monad 的 ma，即 Int .

然后，sequence与其余输入 mas 一起递归调用，其类型为 [Maybe Int] 。代入sequence类型表明结果类型为 Maybe [Int] 。此值再次解开包装，因此目标as的类型为 [Int] 。

在最后一行中，a（类型 Int）被附加到 as（类型 [Int]），产生更长的列表 （[Int] ）。结果被给出给return，它用一个Just（Maybe [Int]）包装以匹配sequence的结果类型。

顺便说一下，如果你想通过do-block详细跟踪类型，你应该首先用lambda将它们脱糖到正常的组成。