Haskell的sequence函数的问题

Question

Haskell的sequence函数的问题

3

我一直在学习宾夕法尼亚大学的CS194，目前正在学习第七课单子(Monads)。我以为我对单子有了一个不错的理解，直到我看到序列(sequence)函数的实现并开始探究。

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

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

The type of return [] is : return [] :: Monad m => m [t] . Earlier in the same lesson, the Monad instance for [] defines return as: return x = [x]. How did this lead to the type signature m [t] for return []?
a <- ma . What is type of a here, assuming I called sequence with [Just 5, Just 9] ? By the Monad instance definition of Maybe:
```
Just x  >>= k = k x
```
I would think x, or a in the case of sequence would be a Num. But it must really be a Monad of Num. How did x become a monad of Num here when Just x from the instance definition of Maybe seems to be pulling x out of Just?

- Tachy

1

在这里，return [] 不是像 [] 的 monad 实例中的 \x -> [x] 函数 - 它是来自 m monad 的 return 函数（因此结果将取决于 m 的实际情况）- 如果有帮助，请考虑 m = Maybe - 因此 return [] 将是 Just []。 - Random Dev

如果你调用 sequence [Just 5, Just 9]，那么 a 的类型将是一些 Num（a 将是 5 和 9） - 在 Num/5 中没有 "Monad" - 你可以说它在 Just 中 ;) - Random Dev

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Sebastian Redl · Accepted Answer

return []的类型是Monad m => m [t] - 在这里，[]是[t]的一个实例，即某种任意类型的列表（由于是空列表，所以该类型是任意的，因此根本没有该类型的实例）。如果你替换为列表单子，return的类型是t -> [t]，return []得到[[]]。令人困惑的是，单子和包含值都是列表。

一般情况下，return的类型是Monad m => t -> m t。如果你专门针对列表，则得到t -> [t]，因此列表类型取代了m的位置。列表的特殊语法使这更加混乱；如果你使用maybe单子，专用的return的类型是t -> Maybe t，因此你可以清楚地看到m被Maybe替换了。在maybe单子中，return []的类型是Maybe [t]：现在单子包装了一些列表。 return []的类型是Monad m => m [t]，一个被单子包装的列表。如果你使用列表单子，替换m为列表构造函数，得到[[t]]，这是正确的类型。

至于第二个问题，你为什么认为a必须是单子？ 在评论澄清后进行编辑 在你给出的例子调用sequence [Just 5, Just 9]中，单子是maybe，而不是列表；该列表是符合sequence类型要求的普通列表。请记住，它需要一个[m a]作为输入。由于你提供了一个Num a => [Maybe a]作为输入，这使得单子成为Maybe，结果类型为Num a => Maybe [a]。sequence将可选值的列表转换为可选列表。这意味着在sequence的第一种情况中，return []应用于Maybe的return，表示Just []。这是有道理的，因为在maybe单子中调用sequence []应返回Just []。

现在，在第二种情况的do-block中，我们有一堆变量，弄清每个变量的类型会有所帮助。我将针对Maybe和Int（用于数字）的具体情况进行操作；获取通用类型只需在所有这些情况下将Maybe替换为m，将Int替换为a，并添加约束即可。

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

在do-block中，使用箭头符号展开ma，结果为a，因此其类型为剥离了单子的ma的类型，即Int。

然后，使用剩余的输入mas（类型为[Maybe Int]）递归调用sequence。将其代入sequence的类型中，可以得到结果类型为Maybe [Int]。再次展开此值，因此目标as的类型为[Int]。

在最后一行，将a（类型为Int）添加到as（类型为[Int]）之前，得到一个更长的列表（[Int]）。将结果给出给return，它将其包装在Just（Maybe [Int]）中以匹配sequence的结果类型。

顺便说一下，如果要详细跟踪do-block中的类型，请先将其解糖为带有lambda的正常组合。