fromJust定义中的模式匹配

Question

函数fromJustin Data.Maybe以这种方式定义:

fromJust          :: Maybe a -> a
fromJust Nothing  = error "Maybe.fromJust: Nothing"
fromJust (Just x) = x

根据我对模式匹配的理解(匹配从上到下的进行),我将改变两个定义的顺序.由于Nothing-part通常在it-is-sure-a-Just情况下不匹配,但在达到第二个定义之前总是检查它.

你能否在推理中澄清我的错误？谢谢.

编辑:

示例:假设我有一个Int每行数百万个类型的文件,并且在我的程序中y需要这个数字(因为Int,不是String)用于其他内容.

import qualified Data.ByteString.Lazy.Char8 as L

readInt = fst . fromJust . L.readInt
-- more stuff

有了上面的定义,fromJust我需要更多的时间来阅读数字,不是吗？

Answer 1

我认为这个问题与性能有关.虽然从上到下对语义模式匹配进行了测试,但大多数Haskell编译器会将ADT构造函数上的匹配优化为C switch语句的等价物.

你可以认为ADT的数据表示有一个"标记",它表示它的构造函数,以及每个参数的指针.例如,Nothing可以表示为0 (null)和Just 42表示为1 (pointer to 42).

然后在这样的函数中:

squash :: Maybe (Maybe Int) -> Int
squash (Just Nothing) = 0
squash Nothing = 0
squash (Just (Just x)) = x

编译器将设置决策树:

squash x = 
   check tag of x:
       0 -> 0
       1 y -> check tag of y:
           0 -> 0
           1 z -> z

每个标签由跳转表或计算的东西,所以它是没有对证更贵0的1.请注意,无论我们的定义中的模式的原始顺序如何,都将制作相同的决策树.

但是,当使用保护而不是在构造函数上进行匹配时,模式最有可能从上到下进行检查(编译器必须非常聪明才能对其进行优化).所以,如果我们fromJust以这种神秘的方式写作:

fromJust x
    | isNothing x = error "fromJust: Nothing"
    | isJust x = case x of { Just y -> y }

然后,这可能会轮流检查每个构造函数,我们可以通过切换案例的顺序进行优化.幸运的是,以一种重要的方式写作很麻烦:-).

Answer 2

这里要实现两个重要的事情:首先,Haskell编译器完全清楚任何值都只能是Nothing或者Just x.因此,它只会测试其中一个.其次,GHC使用指针标记,允许它非常快速地区分指向各种构造函数的指针(细节).

因此,GHC为模式匹配生成了非常好的代码.以下是fromJust返回代码的外观,直接从程序集转储中获取:

        andq $7,%rax
        cmpq $2,%rax
        jae .LcO4

这将获取返回值,然后使用位掩码操作(7 = 111二进制)提取标记.如果此标记为2,则代码知道它指向Just x构造函数.因此它跳转到适当的代码.否则,它只是继续处理代码Nothing.

我认为甚至可以使用Nothing程序中只有一个闭包的知识进一步优化.因此,您可以使用单个地址比较替换它,从而在实际代码中保存位掩码操作甚至寄存器.不确定为什么GHC不会这样做.