为什么在列表列表上应用“序列”会导致计算其笛卡尔积？

发布于 2024-10-22 00:19:37 字数 395 浏览 8 评论 0原文

我的问题是关于 Prelude 中的 sequence 函数，其签名如下：

sequence :: Monad m => [m a] -> m [a]

我了解此函数如何用于 List of 也许。例如，对 [Just 3, Just 9] 应用 sequence 会得到 Just [3, 9]。

我注意到在 List 的 List 上应用 sequence 会给出其笛卡尔积。有人可以帮我理解这是如何/为什么会发生吗？

原文

My question is about the sequence function in Prelude, the signature of which is as follows:

sequence :: Monad m => [m a] -> m [a]

I understand how this function works for List of Maybes. For example, applying sequence on [Just 3, Just 9] gives Just [3, 9].

I noticed that applying sequence on List of Lists gives its Cartesian Product. Can someone please help me understand how/why this happens?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

逆流 2024-10-29 00:19:37

这是可行的，因为在 Haskell 中使用列表作为 monad 会使它们成为不确定性的模型。考虑一下：

sequence [[1,2],[3,4]]

根据定义，这与：

do x <- [1,2]
   y <- [3,4]
   return [x,y]

只需将其读作“首先在 1 和 2 之间进行选择，然后在 3 和 4 之间进行选择”。列表 monad 现在将累积所有可能的结果 - 因此答案[[1,3],[1,4],[2,3],[2,4]].

（有关更模糊的示例，请参阅此处）

This works because using lists as monads in Haskell makes them model indeterminism. Consider:

sequence [[1,2],[3,4]]

By definition this is the same as:

do x <- [1,2]
   y <- [3,4]
   return [x,y]

Just read it as "First a choice between 1 and 2, then a choice between 3 and 4". The list monad will now accumulate all possible outcomes - hence the answer [[1,3],[1,4],[2,3],[2,4]].

(for an even more obfuscated example, see here)

回复收藏 0 原文

<逆流佳人身旁 2024-10-29 00:19:37

sequence 的行为就好像它是这样定义的。

sequence [] = return []
sequence (m:ms) = do
    x <- m
    xs <- sequence ms
    return (x:xs)

（或者 sequence =foldr (liftM2 (:)) (return []) 但无论如何......）

只要想想当应用于列表列表时会发生什么。

sequence [] = [[]]
sequence (list : lists) =
    [ x : xs
    | x <- list
    , xs <- sequence lists
    ]

sequence acts as if it were defined like this.

sequence [] = return []
sequence (m:ms) = do
    x <- m
    xs <- sequence ms
    return (x:xs)

(Or sequence = foldr (liftM2 (:)) (return []) but anyhow…)

Just think about what happens when applied to a list of lists.

sequence [] = [[]]
sequence (list : lists) =
    [ x : xs
    | x <- list
    , xs <- sequence lists
    ]

回复收藏 0 原文

_失温 2024-10-29 00:19:37

只是为了解释一下，为什么将序列应用于列表列表与将序列应用于可能值列表如此不同：

当您将 sequence 应用于列表列表时，类型of sequence 在内部被专门化为 from

sequence :: Monad m => [m a] -> m [a]

to （类型构造函数 m 设置为 []）

sequence :: [[] a] -> [] [a]

（与 sequence :: [[a]] -> [[a]] 相同）

，sequence使用 (>>=)——即一元绑定函数。对于列表，此绑定函数的实现方式与 m 设置为 Maybe! 的方式完全不同。

Just to explain, why the application of sequence to a list of lists is so different from the application of sequence to a list of Maybe-values:

When you apply sequence to a list of lists, then the type of sequence is specialized from

sequence :: Monad m => [m a] -> m [a]

to (with the type constructor m set to [])

sequence :: [[] a] -> [] [a]

(which is the same as sequence :: [[a]] -> [[a]])

internally, sequence uses (>>=) -- i.e. the monadic bind function. For lists this bind function is implemented completly different than for m set to Maybe!

回复收藏 0 原文

~没有更多了~