具有类约束的类型的值实际上是否在运行时是一个函数？

Question

考虑着名的

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

假设,为了避免单态性限制,这用以下注释:

fibs :: Num a => [a]

这似乎意味着在运行时,列表值fibs实际上并不存在,而是每次选择一个元素时重新计算列表的函数fibs？

问题是如何在您知道的不同Haskell实现中实际处理此类情况.

--- ADDED ----我觉得我必须详细说明一下.考虑:

fibsInteger :: [Integer]
fibsInteger = 0: 1: zipWith (+) fibsInteger (tail fibsInteger)

并假设在程序执行期间的值

(fibsInteger !! 42)

需要评估.在那种情况下,我希望像这样的后续评估会发现fibsInteger已经评估了前43个元素.这也意味着它fibsInteger本身及其前42个尾部已经在WHNF中.

然而,就fibs我所知,多态性是不可能的.FUZxxl的评论

因为类型类通常会引入一个包含具有该类型类功能的字典的新参数

似乎支持我的观点,即fibs有效的值在运行时有效地显示为函数？

如果是这样的话,那么像((maximum . map (fibs!!)) [100000 .. 101000] :: Integer)非多态变体那样的应用程序需要显着更长时间才能进行评估,((maximum . map (fibsInteger!!)) [100000 .. 101000] :: Integer)因为每次都必须重新计算前100000个数字.(不幸的是,我现在不能尝试这个)

Answer 1

这取决于实施.在GHC中,类型类是使用字典实现的.假设Num类是这样定义的(本例简化):

class Num a where
    fromInteger :: Integer -> a
    (+) :: a -> a -> a

然后它将被编译为"字典"数据类型:

data Num a = Num { fromInteger :: Integer -> a, plus :: a -> a -> a }

任何带Num约束的东西都会为字典获得额外的参数,例如foo x = x + 1将成为:

foo :: Num a -> a -> a
foo num x = plus num x (fromInteger num 1)

那么让我们看看GHC如何编译fibs,我们呢？

$ cat Fibs.hs
module Fibs where
fibs :: Num a => [a]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
$ ghc -c Fibs.hs -ddump-simpl

==================== Tidy Core ====================
Rec {
Fibs.fibs [Occ=LoopBreaker]
  :: forall a_abu. GHC.Num.Num a_abu => [a_abu]
[GblId, Arity=1]
Fibs.fibs =
  \ (@ a_akv) ($dNum_akw :: GHC.Num.Num a_akv) ->
    GHC.Types.:
      @ a_akv
      (GHC.Num.fromInteger
         @ a_akv $dNum_akw (GHC.Integer.smallInteger 0))
      (GHC.Types.:
         @ a_akv
         (GHC.Num.fromInteger
            @ a_akv $dNum_akw (GHC.Integer.smallInteger 1))
         (GHC.List.zipWith
            @ a_akv
            @ a_akv
            @ a_akv
            (GHC.Num.+ @ a_akv $dNum_akw)
            (Fibs.fibs @ a_akv $dNum_akw)
            (GHC.List.tail @ a_akv (Fibs.fibs @ a_akv $dNum_akw))))
end Rec }

如果你眯一点,这基本上就是这样

fibs :: Num a -> [a]
fibs num = fromInteger num 0
         : fromInteger num 1
         : zipWith (plus num) (fibs num) (tail (fibs num))

所以对于GHC来说,答案是肯定的.正如您所怀疑的那样,这可能会对性能产生严重影响,因为这会破坏fibs此定义所依赖的共享,从而达到指数运行时而不是线性¹.

Prelude Fibs> :set +s
Prelude Fibs> fibs !! 30
832040
(3.78 secs, 912789096 bytes)

我们可以通过引入共享来解决这个问题:

module SharedFibs where
fibs :: Num a => [a]
fibs = let f = 0 : 1 : zipWith (+) f (tail f) in f

这要好得多.

Prelude SharedFibs> :set +s
Prelude SharedFibs> fibs !! 30
832040
(0.06 secs, 18432472 bytes)
Prelude SharedFibs> fibs !! 100000
<huge number>
(2.19 secs, 688490584 bytes)

但它仍然有相同的问题,fibs不能在单独的调用之间共享.如果你想要这个,你必须专注fibs于你想要的数字类型let或where.

这些性能惊喜是可怕的单态性限制存在的部分原因.

_{¹忽略Integer添加不是恒定时间的事实.}