20

我试图了解 Haskell 列表理解在模式匹配方面是如何“在幕后”工作的。以下 ghci 输出说明了我的观点：

Prelude> let myList = [Just 1, Just 2, Nothing, Just 3]
Prelude> let xs = [x | Just x <- myList]
Prelude> xs
[1,2,3]
Prelude>

如您所见，它能够跳过“Nothing”并仅选择“Just”值。我知道 List 是一个单子，定义为（来自 Real World Haskell，第 14 章）：

instance Monad [] where
    return x = [x]
    xs >>= f = concat (map f xs)
    xs >> f = concat (map (\_ -> f) xs)
    fail _ = []

因此，列表推导基本上为列表推导中选择的每个元素构建一个单例列表并将它们连接起来。如果模式匹配在某个步骤失败，则使用“失败”函数的结果。换句话说，“Just x”模式不匹配，因此 [] 用作占位符，直到调用 'concat'。这就解释了为什么“无”似乎被跳过了。

我不明白的是，Haskell 怎么知道调用“失败”函数？它是“编译器魔法”，还是您可以在 Haskell 中自己编写的功能？是否可以编写以下“选择”函数以与列表理解相同的方式工作？

select :: (a -> b) -> [a] -> [b]
select (Just x -> x) myList       -- how to prevent the lambda from raising an error?
[1,2,3]
4

3 回答 3

33

虽然 Haskell 的实现可能不会在内部直接这样做，但以这种方式考虑它是有帮助的 :)

[x | Just x <- myList]

...变成：

do
    Just x <- myList
    return x

...这是：

myList >>= \(Just x) -> return x

至于你的问题：

我不明白的是，Haskell 怎么知道调用“失败”函数？

在 do-notation 中，如果模式绑定失败（即Just x），则调用 fail 方法。对于上面的示例，它看起来像这样：

myList >>= \temp -> case temp of
    (Just x) -> return x
    _        -> fail "..."

因此，每次您在可能失败的一元上下文中进行模式匹配时，Haskell 都会插入对fail. 用 IO 试试看：

main = do
    (1,x) <- return (0,2)
    print x -- x would be 2, but the pattern match fails
于 2009-03-17T06:27:24.470 回答
10

对列表推导进行脱糖的规则需要以下形式的表达式[ e | p <- l ]（其中e是表达式、p模式和l列表表达式）的行为类似于

let ok p = [e]
    ok _ = []
in concatMap ok l

以前版本的 Haskell 有monad comprehensions，它们从语言中被删除，因为它们难以阅读并且与do-notation 冗余。（列表推导也是多余的，但它们并不难阅读。）我认为脱糖[ e | p <- l ]作为一个单子（或者，准确地说，作为一个带有零的单子）会产生类似的东西

let ok p = return e
    ok _ = mzero
in l >>= ok

从哪里来。mzero_ MonadPlus这非常接近

do { p <- l; return e }

哪个脱糖

let ok p = return e
    ok _ = fail "..."
in l >>= ok

当我们取 List Monad 时，我们有

return e = [e]
mzero = fail _ = []
(>>=) = flip concatMap

即，这 3 种方法（列表推导、单子推导、do表达式）对于列表是等价的。

于 2009-03-16T14:30:46.720 回答
6

我认为列表理解语法与 List ( []) 或Maybe就此而言恰好是Monad类型类的一个实例这一事实没有太大关系。

列表推导确实是编译器的魔法或语法糖，但这是可能的，因为编译器知道[]数据类型的结构。

以下是列表理解的编译结果：（好吧，我想，我实际上并没有根据 GHC 检查它）

xs = let f = \xs -> case xs of
                      Just x -> [x]
                      _      -> []
     in concatMap f myList

如您所见，编译器不必调用该fail函数，它可以简单地内联一个空列表，因为它知道列表是什么。

有趣的是，列表推导语法“跳过”模式匹配失败这一事实在一些库中用于进行泛型编程。请参见Uniplate 库中的示例。

编辑：哦，为了回答你的问题，你不能select用你给它的 lambda 调用你的函数。Nothing如果你用一个值调用它，它确实会在模式匹配失败时失败。

您可以将f上面代码中的函数传递给它，但select类型如下：

select :: (a -> [b]) -> [a] -> [b]

很好，您可以在concatMap内部使用该功能:-)

此外，该 newselect现在具有列表的一元绑定运算符的类型（其参数翻转）：

(>>=) :: [a] -> (a -> [b]) -> [b]
xs >>= f = concatMap f xs -- 'or as you said: concat (map f xs)
于 2009-03-16T08:35:27.557 回答