我们需要查看enumFromTo
for Integer 的实例,最后:
last [] = errorEmptyList "last"
last (x:xs) = last' x xs
where last' y [] = y
last' _ (y:ys) = last' y ys
它在 GHC.Enum 中定义为:
enumFrom x = enumDeltaInteger x 1
enumFromThen x y = enumDeltaInteger x (y-x)
enumFromTo x lim = enumDeltaToInteger x 1 lim
在哪里
enumDeltaInteger :: Integer -> Integer -> [Integer]
enumDeltaInteger x d = x `seq` (x : enumDeltaInteger (x+d) d)
-- strict accumulator, so
-- head (drop 1000000 [1 .. ]
-- works
和
enumDeltaToInteger :: Integer -> Integer -> Integer -> [Integer]
enumDeltaToInteger x delta lim
| delta >= 0 = up_list x delta lim
| otherwise = dn_list x delta lim
up_list :: Integer -> Integer -> Integer -> [Integer]
up_list x0 delta lim = go (x0 :: Integer)
where
go x | x > lim = []
| otherwise = x : go (x+delta)
last
正如预期的那样,完全懒惰。
对于 Integer Enum 类,我们有一个严格的累加器(明确地)用于enumFrom
. 在有界情况下(例如[1..n]
),它调用enumDeltaToInteger
然后 into up_list
,它使用工作人员展开列表,直到达到其限制。
但是在助手up_list
中是严格的(参见与 的比较)。x
go
lim
当在 GHCi 中运行时,这些都没有被优化,在返回之前产生对 enumFromTo 的天真的调用()
。
let
it_ax6 :: ()
it_ax6 =
case last
@ GHC.Integer.Type.Integer
(GHC.Enum.enumFromTo
@ GHC.Integer.Type.Integer
GHC.Num.$fEnumInteger
(GHC.Integer.smallInteger 1)
(GHC.Real.^
@ GHC.Integer.Type.Integer
@ GHC.Integer.Type.Integer
GHC.Num.$fNumInteger
GHC.Real.$fIntegralInteger
(GHC.Integer.smallInteger 10)
(GHC.Integer.smallInteger 7)))
of _ -> GHC.Unit.()
in
GHC.Base.thenIO
@ ()
@ [()]
(System.IO.print @ () GHC.Show.$fShow() it_ax6)
(GHC.Base.returnIO
@ [()] (GHC.Types.: @ () it_ax6 (GHC.Types.[] @ ())))
那么,为什么我们在seq
案例中保留列表,而不是在常规案例中?依靠enumFromTo
forInteger
和 for的惰性,常规案例在恒定空间中运行良好last
。该案例的 GHCi 核心如下所示:
let {
it_aKj :: GHC.Integer.Type.Integer
[LclId,
Unf=Unf{Src=<vanilla>, TopLvl=False, Arity=0, Value=False,
ConLike=False, Cheap=False, Expandable=False,
Guidance=IF_ARGS [] 170 0}]
it_aKj =
GHC.List.last
@ GHC.Integer.Type.Integer
(GHC.Enum.enumFromTo
@ GHC.Integer.Type.Integer
GHC.Num.$fEnumInteger
(GHC.Integer.smallInteger 1)
(GHC.Real.^
@ GHC.Integer.Type.Integer
@ GHC.Integer.Type.Integer
GHC.Num.$fNumInteger
GHC.Real.$fIntegralInteger
(GHC.Integer.smallInteger 10)
(GHC.Integer.smallInteger 7))) } in
GHC.Base.thenIO
@ ()
@ [()]
(System.IO.print
@ GHC.Integer.Type.Integer GHC.Num.$fShowInteger it_aKj)
(GHC.Base.returnIO
@ [()]
(GHC.Types.:
@ ()
(it_aKj
`cast` (UnsafeCo GHC.Integer.Type.Integer ()
:: GHC.Integer.Type.Integer ~ ()))
(GHC.Types.[] @ ())))
所以这些几乎是相同的,不同之处在于:
- 在
seq
版本中,last (enumFromTo ..)
被强制在case
.
- 在普通版本中,它是一个懒惰的
let
.
- 在该
seq
版本中,该值被计算然后丢弃,产生一个()
-- 什么都不看结果
- 在正常情况下,它会被检查并显示。
奇怪的是,没有什么神奇的:
let x = case last (enumFromTo 1 n) of _ -> ()
这使它保留了价值。
正如我们所看到的,up_list
它的累加器中的实现是严格的(因为它与 比较lim
,并且列表是延迟展开的——所以last
应该能够在恒定空间中使用它)。手写表达式证实了这一点。
对 ghci 执行进行堆分析会显示整个列表被保留:
这至少告诉我们它不是一连串的 thunk,而是整个列表正在严格构建并保留,直到被丢弃。
所以谜团在于:last
在 ghci 中,而不是在 ghc 中,是什么保留了 list 参数?
我现在怀疑 ghci 的一些内部(或微妙)细节——我认为这值得一张 ghci 票。