在模式匹配前添加 a~
使该匹配无可辩驳。您可以将其视为为模式添加了额外的惰性,因此它永远不会匹配失败,除非该匹配是绝对需要的评估。这是一个简单的例子:
Prelude> (\ (_:_) -> "non-empty") []
"*** Exception: <interactive>:2:2-23: Non-exhaustive patterns in lambda
Prelude> (\ ~(_:_) -> "oops") []
"oops"
使用无可辩驳的模式匹配,即使模式匹配在空列表上失败,由于没有评估绑定变量,因此没有错误。本质上,无可辩驳的模式匹配将函数转换为:
\ xs -> let (_:_) = xs in "oops"
正是这种额外的懒惰包装减慢了你的长度函数。如果你应用相同的 let-binding 变换,lengthwtilde
你会得到
lengthwtilde [] = 0
lengthwtilde xs' = let (_:xs) = xs' in 1 + lengthwtilde xs
想想这是如何评估的。在顶层,你得到1+lengthwtilde xs
. 但是 xs 甚至没有被评估,因为它是一个 let-bound 变量。因此,在下一步中,对 firstxs
进行评估以确定它与 的第二种情况匹配lengthwtilde
,然后重复该过程。
将此与lengthwotilde
. 在此函数中,对函数的第二种情况进行匹配的行为也会强制对参数进行评估。最终结果是相同的,但是能够更快地打开它而不是让另一个 thunk 被强制执行更有效。
从技术上讲lengthwtilde
稍微复杂一些:参数已经在第二个分支中进行了评估,因为这是我们确定我们所在的分支的方式,但是当传递给递归调用时它会被重新包装。
能够看到生产的核心很有用。这是lengthwotilde
(产生于ghc -O0
:
Foo.lengthwotilde =
\ (@ t_afD)
(@ a_afE)
($dNum_afF :: GHC.Num.Num a_afE)
(eta_B1 :: [t_afD]) ->
letrec {
lengthwotilde1_af2 [Occ=LoopBreaker] :: [t_afD] -> a_afE
[LclId, Arity=1]
lengthwotilde1_af2 =
\ (ds_dgd :: [t_afD]) ->
case ds_dgd of _ {
[] -> GHC.Num.fromInteger @ a_afE $dNum_afF (__integer 0);
: ds1_dge xs_af1 ->
GHC.Num.+
@ a_afE
$dNum_afF
(GHC.Num.fromInteger @ a_afE $dNum_afF (__integer 1))
(lengthwotilde1_af2 xs_af1)
}; } in
lengthwotilde1_af2 eta_B1
请注意,该函数lengthwotilde1_af2
立即case
对参数执行 a ds_dgd
(这是输入列表),然后在 case 内部递归,形成一个 thunk(带有一些扩展):
1 + len [2..]
1 + (1 + len [3..])
1 + (1 + (1 + len [4..])
这最终需要评估 1 + (1 + (1 + (1 + ..)))
这里是lengthwtilde
Foo.lengthwtilde =
\ (@ t_afW)
(@ a_afX)
($dNum_afY :: GHC.Num.Num a_afX)
(eta_B1 :: [t_afW]) ->
letrec {
lengthwtilde1_afM [Occ=LoopBreaker] :: [t_afW] -> a_afX
[LclId, Arity=1]
lengthwtilde1_afM =
\ (ds_dgh :: [t_afW]) ->
case ds_dgh of wild_X9 {
[] -> GHC.Num.fromInteger @ a_afX $dNum_afY (__integer 0);
: ipv_sgv ipv1_sgw ->
GHC.Num.+
@ a_afX
$dNum_afY
(GHC.Num.fromInteger @ a_afX $dNum_afY (__integer 1))
(lengthwtilde1_afM
(case wild_X9 of _ {
[] ->
(Control.Exception.Base.irrefutPatError
@ () "foo.hs:(3,1)-(4,42)|(_ : xs)")
`cast` (UnsafeCo () [t_afW] :: () ~# [t_afW]);
: ds1_dgk xs_aeH -> xs_aeH
}))
}; } in
lengthwtilde1_afM eta_B1
对此的评估形成了不同的声音:
len [1..]
1 + (len (if null [1..] then error else [2..]))
1 + (len [2..])
1 + (1 + len (if null [2..] then error else [3..]))
这最终会导致您第一次得到相同的添加链,但有一些额外的逻辑来处理无可辩驳的模式失败。
现在,如果您正在运行带有任何优化的编译代码,ghc 几乎肯定会发现参数不可能为空,因为(:)
此时它们已经被评估并知道使用构造函数。当我编译ghc -O2
并运行代码时,两个函数的执行时间相同。它们都很糟糕,因为任何一种方式都会导致一连串的重击。的标准定义length
要好得多,因为这将是一个很好的foldl'
定义。