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

18 浏览
0 Comments

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

考虑这个著名的

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

假设为了避免单态限制，这个被注释为：

fibs :: Num a => [a]

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

问题是确定你知道的不同Haskell实现实际上如何处理这样的情况。

--- 添加 ----

我觉得我必须再详细解释一下。考虑：

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个数字将必须每次重新计算。

（不幸的是，我此时无法尝试此操作）

admin 更改状态以发布 2023年5月24日
0

2 答案

0 Comments

多态性可能会带来额外的性能负担（我认为这就是你要问的问题）。在Thomas回答这个问题时，将类型设为非多态性可以将运行时间从36秒减少到11秒。

你的陈述：

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

我不太确定你的意思-你似乎已经意识到它是惰性的。你可能想知道Haskell是否认为这是“函数声明”还是“值声明”-你可以尝试使用模板Haskell：

> runQ [d| fib = 0 : 1 : zipWith (+) fib (tail fib) |]
[ValD (VarP fib) ...

所以它是一个值声明（ValD）。

0
0 Comments

这取决于具体的实现。在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的共享，因此运行时间呈指数增长，而不是线性增长1。

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

(2.19 secs, 688490584 bytes)

但它仍然有相同的问题，即fibs在不同的调用间没有共享。如果你想要这个功能，你必须在let或where中将fibs专门化为你想要的数字类型。

这种性能上的惊喜是为什么可怕的单态限制存在的一部分。

1 忽略Integer加法不是常数时间的事实。

0