haskell - 为什么更通用的类型会影响 Haskell 中的运行时？

Question

考虑无限斐波那契数列的以下两种实现:

fibsA :: Num a => [a]
fibsA = 0:1:(zipWith (+) fibsA (tail fibsA))

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

在 GHCI 中，执行 fibsB !! k比执行 fibsA !! k 快得多。特别是，似乎 fibsA 的值不断重新计算(不内存/存储)。

此外，当省略类型签名时，GHCI 的 :t显示它是 [Integer] ，并且该函数会相应地执行。

此行为也会出现在编译代码 ( ghc -O3 Fibs.hs ) 中。

为什么会是Integer比 Num a => a 快得多？

Answer 1

当您编写 fibsA::Num a => [a] 时，编译器会构造本质上的内容

fibsA :: NumDict a -> [a]

哪里

data NumDict a = NumDict
    { (+)         :: a -> a -> a
    , (-)         :: a -> a -> a
    , (*)         :: a -> a -> a
    , negate      :: a -> a
    , abs         :: a -> a
    , signum      :: a -> a
    , fromInteger :: Integer -> a
    }

请注意，Num a 已从约束变为函数的参数。 A typeclass is essentially just a lookup table for each type that implements the class 。因此，对于 Num，默认情况下您会拥有

mkInteger_NumDict :: NumDict Integer
mkInteger_NumDict = NumDict
    { (+) = integer_plus
    , (-) = integer_minus
    , (*) = integer_mult
    , ...
    }

mkInt_NumDict     :: NumDict Int

mkFloat_NumDict   :: NumDict Float

mkDouble_NumDict  :: NumDict Double

当实例被解析时，这些会自动传递给使用类型类的函数。这意味着我们的函数 fibsA 本质上带有一个参数。当您从 GHCi 调用它时，默认规则会启动并选择 Integer，但由于它是这样调用的，所以内部看起来更像是这样的:

{-# RecordWildCards #-}  -- To reduce typing

fibsA :: NumDict a -> [a]
fibsA nd@(NumDict{..}) = fromInteger 0 : fromInteger 1 : zipWith (+) (fibsA nd) (tail $ fibsA nd)

你看出这个问题了吗？它仍然是递归的，但现在它必须在每一步中进行函数调用，从而降低了性能。如果你想让它变得非常快，聪明的程序员就可以做到

fibsA nd@(NumDict{..}) = fromInteger 0 : fromInteger 1 : zipWith (+) fibsA' (tail fibsA')
    where fibsA' = fibsA nd

这至少允许内存。然而，haskell 二进制文件无法在运行时真正执行此优化，这是在编译时发生的。所以你最终得到的是一个较慢的递归函数。使用 fibsB，您可以具体指定类型，其类型签名没有多态约束。值 fibsB 没有隐式或显式参数，因此当引用它时，它是指向内存中同一对象的指针。 fibsA 是一个指向函数的指针，因此当递归使用时，它会返回内存中的新对象，并且没有内存。这就是为什么 fibsB 比 fibsA 更快，只有 fibsB 得到优化，因为编译器不必让它适用于所有 Num，仅限Integer。