haskell - Haskell 的序列函数问题

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 x = [x] .这如何导致类型签名m [t]为 return [] ?

a <- ma . a的类型是什么在这里，假设我用 [Just 5, Just 9] 调用序列?由 Monad Maybe 的实例定义:

Just x  >>= k = k x

我想x , 或 a在 sequence 的情况下将是 Num .但它一定是一个Monad的 Num .怎么样x成为Num的monad在这里当 Just x来自 Maybe 的实例定义好像在拉x出Just ?

Answer 1

return []的类型是 Monad m => m [t] - 在这里，[]是 [t] 的一个实例，即某个任意类型的列表(该类型是任意的，因为它是空列表，因此无论如何都没有该类型的实例)。如果替换列表 monad，则类型为 return是 t -> [t] , 和 return [] yield [[]] .令人困惑的是，monad 和包含的值都是列表。
return的类型一般是Monad m => t -> m t .如果你专门研究列表，你会得到 t -> [t] ，所以列表类型代替了 m .列表的特殊语法使这更令人困惑；如果你使用maybe monad，专门的返回类型为t -> Maybe t ，因此您可以清楚地看到 m被 Maybe 取代.在maybemonad中，return []的类型是 Maybe [t] : monad 现在包装了一些列表。
return []的类型是 Monad m => m [t] ，由 monad 包装的列表。如果你使用 list monad，你可以替换 m使用列表构造函数并获得 [[t]] ，这是正确的类型。

至于第二个问题，你为什么认为a必须是单子(monad)？

在评论中澄清后编辑

在示例中调用 sequence [Just 5, Just 9]你给了，单子(monad)可能是，而不是列表；该列表是 sequence 类型要求的普通列表.请记住，它需要一个 [m a]作为输入。为您提供 Num a => [Maybe a]作为输入，这使得 monad Maybe ，结果类型为 Num a => Maybe [a] . sequence将可选值列表转换为可选列表。这意味着在 sequence 的第一种情况下, return []适用于Maybe的 return并表示 Just [] .这是有道理的，因为调用 sequence []也许 monad 应该返回 Just [] .

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

整个输入的类型为 [Maybe Int] .第二种情况与 (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-blocks 详细跟踪类型，您应该首先使用 lambda 将它们脱糖为正常组合。