当模式匹配失败时,为什么Haskell列表推导不会导致错误？

Question

我试图理解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是一个monad,定义为(源自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"之前,[]用作占位符.这就解释了为什么"Nothing"似乎被忽略了.

我不明白的是,Haskell如何知道称之为"失败"功能？它是"编译魔术",还是你可以在Haskell中自己编写的功能？是否可以编写以下"select"函数以与列表推导相同的方式工作？

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

Answer 1

虽然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 "..."

因此,每次在可能失败的monadic上下文中进行模式匹配时,Haskell都会插入一个调用fail.尝试使用IO:

main = do
    (1,x) <- return (0,2)
    print x -- x would be 2, but the pattern match fails

Answer 2

消除列表理解的规则要求表单的表达式[ e | p <- l ](e表达式,p模式和l列表表达式)表现得像

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

以前版本的Haskell具有monad理解,这些理解从语言中删除,因为它们难以阅读并且与do-notation重复.(列表理解也是多余的,但它们并不那么难以阅读.)我认为[ e | p <- l ]作为一个monad(或者,确切地说,作为一个零的monad)的desugaring 会产生像

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

这里mzero是从MonadPlus类.这非常接近

do { p <- l; return e }

这desugars到

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

当我们采用List Monad时,我们有

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

即,3种方法(列表推导,monad理解,do表达式)对于列表是等价的.

Answer 3

我不认为列表理解语法与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内部使用这个功能:-)

此外,new select现在具有列表的monadic绑定运算符的类型(其参数被翻转):

(>>=) :: [a] -> (a -> [b]) -> [b]
xs >>= f = concatMap f xs -- 'or as you said: concat (map f xs)